Post's theorem
From Free net encyclopedia
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>.fa:قضیه پست