Editing Post's theorem (section)

== Background ==
{{See also|Arithmetical hierarchy#Relation to Turing machines}}
The statement of Post's theorem uses several concepts relating to [[Structure (mathematical logic)#Definable_relations|definability]] and [[recursion theory]].  This section gives a brief overview of these concepts, which are covered in depth in their respective articles. 

The [[arithmetical hierarchy]] classifies certain sets of natural numbers that are definable in the language of Peano arithmetic.   A [[formula (mathematical logic)|formula]]  is said to be <math>\Sigma^{0}_m</math> if it is an existential statement in [[prenex normal form]] (all quantifiers at the front) with <math>m</math> alternations between existential and universal quantifiers applied to a formula with [[bounded quantifier]]s only.  Formally a formula <math>\phi(s)</math> in the language of Peano arithmetic is a <math>\Sigma^{0}_m</math> formula if it is of the form
:<math>\left(\exists n^1_1\exists n^1_2\cdots\exists n^1_{j_1}\right)\left(\forall n^2_1 \cdots \forall n^2_{j_2}\right)\left(\exists n^3_1\cdots\right)\cdots\left(Q n^m_1 \cdots \right)\rho(n^1_1,\ldots n^m_{j_m},x_1,\ldots,x_k)</math>
where <math>\rho</math> contains only [[bounded quantifier]]s and ''Q'' is <math>\forall</math> if ''m'' is even and <math>\exists</math> if ''m'' is odd.

A set of natural numbers <math>A</math> is said to be <math>\Sigma^0_m</math> if it is definable by a <math>\Sigma^0_m</math> formula, that is, if there is a <math>\Sigma^0_m</math> formula <math>\phi(s)</math> such that each number <math>n</math> is in <math>A</math> if and only if <math>\phi(n)</math> holds.   It is known that if a set is <math>\Sigma^0_m</math> then it is <math>\Sigma^0_n</math> for any <math>n > m</math>, but for each ''m'' there is a <math>\Sigma^0_{m+1}</math> set that is not <math>\Sigma^0_m</math>.  Thus the number of quantifier alternations required to define a set gives a measure of the complexity of the set.

Post's theorem uses the relativized arithmetical hierarchy as well as the unrelativized hierarchy just defined.   A set <math>A</math> of natural numbers is said to be <math>\Sigma^0_m</math> relative to a set <math>B</math>, written <math>\Sigma^{0,B}_m</math>, if <math>A</math> is definable by a <math>\Sigma^0_m</math> formula in an extended language that includes a predicate for membership in <math>B</math>.

While the arithmetical hierarchy measures definability of sets of natural numbers, [[Turing degrees]] measure the level of uncomputability of sets of natural numbers.  A set <math>A</math> is said to be [[Turing reduction|Turing reducible]] to a set <math>B</math>, written <math>A \leq_T B</math>, if there is an [[oracle Turing machine]] that, given an oracle for <math>B</math>, computes the [[Indicator function|characteristic function]] of <math>A</math>.
The [[Turing jump]] of a set <math>A</math> is a form of the [[Halting problem]] relative to <math>A</math>.  Given a set <math>A</math>, the Turing jump <math>A'</math> is the set of indices  of oracle Turing machines that halt on input <math>0</math> when run with oracle <math>A</math>.  It is known that every set <math>A</math> is Turing reducible to its Turing jump, but the Turing jump of a set is never Turing reducible to the original set.  

Post's theorem uses finitely iterated Turing jumps.  For any set <math>A</math> of natural numbers, the notation <math>A^{(n)}</math> indicates the <math>n</math>&ndash;fold iterated Turing jump of <math>A</math>.  Thus <math>A^{(0)}</math> is just <math>A</math>, and <math>A^{(n+1)}</math> is the Turing jump of <math>A^{(n)}</math>.