Post's Theorem - Post's Theorem and Corollaries

Post's Theorem and Corollaries

Post's theorem establishes a close connection between the arithmetical hierarchy and the Turing degrees of the form, that is, finitely iterated Turing jumps of the empty set. (The empty set could be replaced with any other computable set without changing the truth of the theorem.)

Post's theorem states:

1. A set B is if and only if is recursively enumerable by an oracle Turing machine with an oracle for, that is, if and only if B is .
2. The set is complete for every . This means that every set is many-one reducible to .

Post's theorem has many corollaries that expose additional relationships between the arithmetical hierarchy and the Turing degrees. These include:

1. Fix a set C. A set B is if and only if B is . This is the relativization of the first part of Post's theorem to the oracle C.
2. A set B is if and only if . More generally, B is if and only if .
3. A set is defined to be arithmetical if it is for some n. Post's theorem shows that, equivalently, a set is arithmetical if and only if it is Turing reducible to for some m.