Post's theorem
|
|
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 <math>X<math> of <math>\omega<math> is <math>\Sigma_n<math> if there is a <math>\Sigma_n<math> formula with free variable <math>n<math> which is true if and only if <math>n<math> is in <math>X<math>.
Formally Post's theorem states:
- For every <math>n \geq 0<math>, <math>B \in \Sigma_{n+1}<math> if and only if <math>B<math> is a recursively enumerable set with an oracle of some <math>\Pi_n<math> set or, equivalently, some <math>\Sigma_n<math> set.
- <math>\emptyset^{(n)}<math>, i.e. the n-th Turing jump of the empty set is <math>\Sigma_n<math> complete for every <math>n > 0<math>.
The first result says that the <math>\Sigma_n<math> 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 <math>\Sigma_n<math> (<math>X<math> complete for <math>\Sigma_n<math> means that every other set in <math>\Sigma_n<math> is Turing reducible from <math>X<math>).
As immediate corollaries we get:
- <math>B \in \Sigma_{n+1}<math> if and only if <math>B<math> is a recursively enumerable set with an oracle of <math>\emptyset^{(n)}<math>.
- <math>B \in \Delta_{n+1}<math> if and only if <math>B \leq_T \emptyset^{(n)}<math>, i.e. <math>B<math> is Turing reducible to <math>\emptyset^{(n)}<math>.fr:théorème de Post