theory of arithmetic that is able to represent every primitive recursive function is able to represent and . Examples of such arithmetical theories include Robinson arithmetic and stronger theories such as Peano arithmetic. Normal form theorem The predicates can be used to obtain Kleene's normal form theorem for computable functions (Soare 1987, p. 15; Kleene 1943, p. 52—53). This states there exists a fixed primitive recursive function such that a function is computable if and only if there is a number such that for all one has , where μ is the μ operator ( is the smallest natural number for which is true) and is true if both sides are undefined or if both are defined and they are equal. By the theorem, the definition of every general recursive function f can be rewritten into a normal form such that the μ operator is used only once, viz. immediately below the topmost , which is independent of the computable function . 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 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 Tn 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. Notes References Peter Hinman, 2005, Fundamentals of Mathematical Logic, A K Peters. Reprinted in The Undecidable, Martin Davis, ed., 1965, pp. 255–287. —, 1952, Introduction to Metamathematics, North-Holland. Reprinted by Ishi press, 2009, . —, 1967. Mathematical Logic, John Wiley. Reprinted by Dover, 2001, . Robert I. Soare, 1987, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer. Computability theory