Kleene-Mostowski classification

A classification of number-theoretic predicates, introduced independently by S.C. Kleene [1] and A. Mostowski [2]. 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.

References

[1]	S.C. Kleene, "Recursive predicates and quantifiers" Trans. Amer. Math. Soc. , 53 (1943) pp. 41–73
[2]	A. Mostowski, "On definable sets of positive integers" Fund. Math. , 34 (1947) pp. 81–112

Comments

is commonly denoted by . One usually speaks of the arithmetical hierarchy (rather than the Kleene–Mostowski classification).

References

[a1]	H.B. Enderton, "Elements of recursion theory" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 527–566