Chemistry - 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 $X$ of $ω$ is $Σ n$ if there is a $Σ n$ formula with free variable $n$ which is true if and only if $n$ is in $X$ .

Formally Post's theorem states:

For every $n \geq 0$ , $B \in \Sigma_{n+1}$ if and only if $B$ is a recursively enumerable set with an oracle of some $Π n$ set or, equivalently, some $Σ n$ set.

$\emptyset^{(n)}$ , i.e. the n-th Turing jump of the empty set is $Σ n$ complete for every $n > 0$ .

The first result says that the $Σ n$ 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 $Σ n$ ( $X$ complete for $Σ n$ means that every other set in $Σ n$ is Turing reducible from $X$ ).

As immediate corollaries we get:

$B \in \Sigma_{n+1}$ if and only if $B$ is a recursively enumerable set with an oracle of $\emptyset^{(n)}$ .

$B \in \Delta_{n+1}$ if and only if $B \leq_T \emptyset^{(n)}$ , i.e. $B$ is Turing reducible to $\emptyset^{(n)}$ .

Categories: Mathematical logic | Theorems | Computability