Arithmetical Hierarchy
In addition to encoding computability, the T predicate can be used to generate complete sets in the arithmetical hierarchy. In particular, the set
- K = { e : ∃ x T(e,0,x)},
which is of the same Turing degree as the halting problem, is a complete unary relation (Soare 1987, pp. 28, 41). More generally, the set
is a complete (n+1)-ary predicate. Thus, once a representation of the T predicate is obtained in a theory of arithmetic, a representation of a -complete predicate can be obtained from it.
This construction can be extended higher in the arithmetical hierarchy, as in Post's theorem (compare Hinman 2005, p. 397). For example, if a set is complete then the set
is complete.
Read more about this topic: Kleene's T Predicate
Famous quotes containing the word hierarchy:
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (1919–1990)