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 $ \Pi _ {0} $ and $ \Sigma _ {0} $. For each $ k > 0 $ the class $ \Sigma _ {k} $ is defined as the class of all predicates expressible in the form $ \exists y R ( y , x _ {1} \dots x _ {n} ) $, where $ \exists $ is the existential quantifier and $ R( y , x _ {1} \dots x _ {n} ) $ is a predicate in the class $ \Pi _ {k-} 1 $, while the class $ \Pi _ {k} $ is defined as the class of predicates expressible in the form $ \forall y R( y, x _ {1} \dots x _ {n} ) $, where $ \forall $ is the universal quantifier and the predicate $ R ( y , x _ {1} \dots x _ {n} ) $ belongs to the class $ \Sigma _ {k-} 1 $. In this way a double sequence of classes is obtained:

$$ \Sigma _ {0} = \Pi _ {0} \ \begin{array}{cccc} \Sigma _ {1} &\Sigma _ {2} &\Sigma _ {3} &\dots \\ \Pi _ {1} &\Pi _ {2} &\Pi _ {3} &\dots \\ \end{array} . $$

If a predicate belongs to $ \Sigma _ {k} $ or $ \Pi _ {k} $, then it belongs to the classes $ \Pi _ {j} $ and $ \Sigma _ {j} $ for any $ j > k $, that is, $ \Sigma _ {k} \subseteq \Sigma _ {j} \cap \Pi _ {j} $ and $ \Pi _ {k} \subseteq \Sigma _ {j} \cap \Pi _ {j} $ for any $ j > k $. If $ k > 0 $, then there exist predicates in $ \Sigma _ {k} $ not belonging to $ \Pi _ {k} $ and also predicates in $ \Pi _ {k} $ not belonging to $ \Sigma _ {k} $, that is, $ \Sigma _ {k} \setminus \Pi _ {k} \neq \emptyset $ and $ \Pi _ {k} \setminus \Sigma _ {k} \neq \emptyset $. A predicate belongs to one of the classes $ \Sigma _ {k} $ or $ \Pi _ {k} $ if and only if it is expressible in the language of formal arithmetic (cf. Arithmetic, formal). If a predicate $ Q ( x _ {1} \dots x _ {n} ) $ belongs to $ \Sigma _ {k} $( or $ \Pi _ {k} $) then $ \neg Q ( x _ {1} \dots x _ {n} ) $, where $ \neg $ is the negation sign, belongs to $ \Pi _ {k} $( respectively, $ \Sigma _ {k} $). A predicate $ Q ( x _ {1} \dots x _ {n} ) $ is recursive (cf. Recursive predicate) if and only if $ Q ( x _ {1} \dots x _ {n} ) $ and $ \neg Q ( x _ {1} \dots x _ {n} ) $ belong to $ \Sigma _ {1} $, i.e. $ \Sigma _ {1} \cap \Pi _ {1} = \Sigma _ {0} = \Pi _ {0} $. If $ k > 0 $, then $ ( \Sigma _ {k+} 1 \cap \Pi _ {k+} 1 ) \setminus ( \Sigma _ {k} \cup \Pi _ {k} ) \neq \emptyset $.

The classification of sets defined in the language of formal arithmetic is based on the classification of predicates: A set $ M $ belongs to $ \Pi _ {k} $( or $ \Sigma _ {k} $) 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

$ \Pi _ {j} \cap \Sigma _ {j} $ is commonly denoted by $ \Delta _ {j} $. 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