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 |
Kleene-Mostowski classification. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kleene-Mostowski_classification&oldid=47502