In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. As notation we say that a subset X of ω is Σ_n if there is a Σ_n formula with free variable n which is true if and only if n is in X.

Formally Post's theorem states:

• For every , if and only if B is a recursively enumerable set with an oracle of some Π_n set or, equivalently, some Σ_n set.

• , i.e. the n-th Turing jump of the empty set is Σ_n complete for every n > 0.

The first result says that the Σ_n sets represent sets which are computably enumerable with an oracle in a one lower set. The second result says that the Turing jumps form complete sets of the Σ_n (X complete for Σ_n means that every other set in Σ_n is Turing reducible from X).

As immediate corollaries we get:

• if and only if B is a recursively enumerable set with an oracle of .

• if and only if , i.e. B is Turing reducible to .