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 \in 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