# Kleene-Mostowski classification

(Redirected from Arithmetical hierarchy)

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