Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Home > 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 of is if there is a formula with free variable which is true if and only if is in .Formally Post's theorem states:
- , i.e. the n-th Turing jump of the empty set is complete for every .
- if and only if , i.e. is Turing reducible to .
The first result says that the sets represent sets which are computably enumerable with an oracle in a one lower set. The second results says that the Turing jumps form complete sets of the ( complete for means that every other set in is Turing reducible from ).
As immediate corollaries we get:
- if and only if , i.e. is Turing reducible to .
The result is named for Emil Post.
Mathematical logic
Theorems
Computability
Read more »