Namespaces
Variants
Actions

Difference between revisions of "Kleene-Mostowski classification"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (fix tex)
 
Line 18: Line 18:
 
where  $  \exists $
 
where  $  \exists $
 
is the existential [[Quantifier|quantifier]] and  $  R( y , x _ {1} \dots x _ {n} ) $
 
is the existential [[Quantifier|quantifier]] and  $  R( y , x _ {1} \dots x _ {n} ) $
is a predicate in the class  $  \Pi _ {k-} 1 $,  
+
is a predicate in the class  $  \Pi _ {k-1}$,  
 
while the class  $  \Pi _ {k} $
 
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} ) $,  
 
is defined as the class of predicates expressible in the form  $  \forall y  R( y, x _ {1} \dots x _ {n} ) $,  
 
where  $  \forall $
 
where  $  \forall $
 
is the universal quantifier and the predicate  $  R ( y , x _ {1} \dots x _ {n} ) $
 
is the universal quantifier and the predicate  $  R ( y , x _ {1} \dots x _ {n} ) $
belongs to the class  $  \Sigma _ {k-} 1 $.  
+
belongs to the class  $  \Sigma _ {k-1}$.  
 
In this way a double sequence of classes is obtained:
 
In this way a double sequence of classes is obtained:
  
Line 66: Line 66:
 
i.e.  $  \Sigma _ {1} \cap \Pi _ {1} = \Sigma _ {0} = \Pi _ {0} $.  
 
i.e.  $  \Sigma _ {1} \cap \Pi _ {1} = \Sigma _ {0} = \Pi _ {0} $.  
 
If  $  k > 0 $,  
 
If  $  k > 0 $,  
then  $  ( \Sigma _ {k+} 1 \cap \Pi _ {k+} 1 ) \setminus  ( \Sigma _ {k} \cup \Pi _ {k} ) \neq \emptyset $.
+
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 $
 
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} $(
+
belongs to  $  \Pi _ {k} $ (or  $  \Sigma _ {k} $)  
or  $  \Sigma _ {k} $)  
+
if the predicate  "$x \in M$"  belongs to this class.
if the predicate  "x M"  belongs to this class.
 
  
 
====References====
 
====References====
Line 77: Line 76:
  
 
====Comments====
 
====Comments====
$  \Pi _ {j} \cap \Sigma _ {j} $
+
$  \Pi _ {j} \cap \Sigma _ {j} $ is commonly denoted by  $  \Delta _ {j} $.  
is commonly denoted by  $  \Delta _ {j} $.  
 
 
One usually speaks of the arithmetical hierarchy (rather than the Kleene–Mostowski classification).
 
One usually speaks of the arithmetical hierarchy (rather than the Kleene–Mostowski classification).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H.B. Enderton,  "Elements of recursion theory"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1977)  pp. 527–566</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H.B. Enderton,  "Elements of recursion theory"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1977)  pp. 527–566</TD></TR></table>

Latest revision as of 15:41, 22 June 2020


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