Namespaces
Variants
Actions

Difference between revisions of "Kleene-Mostowski classification"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(No difference)

Revision as of 18:52, 24 March 2012

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
How to Cite This Entry:
Kleene-Mostowski classification. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kleene-Mostowski_classification&oldid=18718
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article