Editing Post's theorem (section)

== Post's theorem and corollaries ==

Post's theorem establishes a close connection between the arithmetical hierarchy and the Turing degrees of the form <math>\emptyset^{(n)}</math>, 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:
#A set <math>B</math> is <math>\Sigma^0_{n+1}</math> if and only if <math>B</math> is [[recursively enumerable]] by an oracle Turing machine with an oracle for <math>\emptyset^{(n)}</math>, that is, if and only if <math>B</math> is <math>\Sigma^{0,\emptyset^{(n)}}_1</math>.
#The set <math>\emptyset^{(n)}</math> is <math>\Sigma^0_n</math>-complete for every <math>n > 0</math>.  This means that every <math>\Sigma^0_n</math> set is [[many-one reduction|many-one reducible]] to <math>\emptyset^{(n)}</math>. 

Post's theorem has many corollaries that expose additional relationships between the arithmetical
hierarchy and the Turing degrees.  These include:
#Fix a set <math>C</math>. A set <math>B</math> is <math>\Sigma^{0,C}_{n+1}</math> if and only if <math>B</math> is <math>\Sigma^{0,C^{(n)}}_1</math>.  This is the relativization of the first part of Post's theorem to the oracle <math>C</math>.
#A set <math>B</math> is <math>\Delta_{n+1}</math> if and only if <math>B \leq_T \emptyset^{(n)}</math>. More generally, <math>B</math> is <math>\Delta^C_{n+1}</math> if and only if <math>B \leq_T C^{(n)}</math>.
#A set is defined to be arithmetical if it is <math>\Sigma^0_n</math> for some <math>n</math>.  Post's theorem shows that, equivalently, a set is arithmetical if and only if it is Turing reducible to <math>\emptyset^{(m)}</math> for some ''m''.