A classification of number-theoretic predicates, introduced independently by S.C. Kleene  and A. Mostowski . The class of all recursive predicates is denoted simultaneously by and . For each the class is defined as the class of all predicates expressible in the form , where is the existential quantifier and is a predicate in the class , while the class is defined as the class of predicates expressible in the form , where is the universal quantifier and the predicate belongs to the class . In this way a double sequence of classes is obtained:
If a predicate belongs to or , then it belongs to the classes and for any , that is, and for any . If , then there exist predicates in not belonging to and also predicates in not belonging to , that is, and . A predicate belongs to one of the classes or if and only if it is expressible in the language of formal arithmetic (cf. Arithmetic, formal). If a predicate belongs to (or ) then , where is the negation sign, belongs to (respectively, ). A predicate is recursive (cf. Recursive predicate) if and only if and belong to , i.e. . If , then .
The classification of sets defined in the language of formal arithmetic is based on the classification of predicates: A set belongs to (or ) if the predicate "x M" belongs to this class.
|||S.C. Kleene, "Recursive predicates and quantifiers" Trans. Amer. Math. Soc. , 53 (1943) pp. 41–73|
|||A. Mostowski, "On definable sets of positive integers" Fund. Math. , 34 (1947) pp. 81–112|
is commonly denoted by . One usually speaks of the arithmetical hierarchy (rather than the Kleene–Mostowski classification).
|[a1]||H.B. Enderton, "Elements of recursion theory" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 527–566|
Arithmetical hierarchy. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Arithmetical_hierarchy&oldid=42300