Namespaces
Variants
Actions

Difference between revisions of "Kleene-Mostowski classification"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fix tex)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
A classification of number-theoretic predicates, introduced independently by S.C. Kleene [[#References|[1]]] and A. Mostowski [[#References|[2]]]. The class of all recursive predicates is denoted simultaneously by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554601.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554602.png" />. For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554603.png" /> the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554604.png" /> is defined as the class of all predicates expressible in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554605.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554606.png" /> is the existential [[Quantifier|quantifier]] and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554607.png" /> is a predicate in the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554608.png" />, while the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k0554609.png" /> is defined as the class of predicates expressible in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546010.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546011.png" /> is the universal quantifier and the predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546012.png" /> belongs to the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546013.png" />. In this way a double sequence of classes is obtained:
+
<!--
 +
k0554601.png
 +
$#A+1 = 50 n = 0
 +
$#C+1 = 50 : ~/encyclopedia/old_files/data/K055/K.0505460 Kleene\ANDMostowski classification
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546014.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
If a predicate belongs to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546015.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546016.png" />, then it belongs to the classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546018.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546019.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546021.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546022.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546023.png" />, then there exist predicates in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546024.png" /> not belonging to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546025.png" /> and also predicates in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546026.png" /> not belonging to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546027.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546029.png" />. A predicate belongs to one of the classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546030.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546031.png" /> if and only if it is expressible in the language of formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]). If a predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546032.png" /> belongs to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546033.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546034.png" />) then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546035.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546036.png" /> is the negation sign, belongs to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546037.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546038.png" />). A predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546039.png" /> is recursive (cf. [[Recursive predicate|Recursive predicate]]) if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546041.png" /> belong to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546042.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546043.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546044.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546045.png" />.
+
A classification of number-theoretic predicates, introduced independently by S.C. Kleene [[#References|[1]]] and A. Mostowski [[#References|[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|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:
  
The classification of sets defined in the language of formal arithmetic is based on the classification of predicates: A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546046.png" /> belongs to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546047.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546048.png" />) if the predicate  "x M"  belongs to this class.
+
$$
 +
\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|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|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====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.C. Kleene,  "Recursive predicates and quantifiers"  ''Trans. Amer. Math. Soc.'' , '''53'''  (1943)  pp. 41–73</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A. Mostowski,  "On definable sets of positive integers"  ''Fund. Math.'' , '''34'''  (1947)  pp. 81–112</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.C. Kleene,  "Recursive predicates and quantifiers"  ''Trans. Amer. Math. Soc.'' , '''53'''  (1943)  pp. 41–73</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A. Mostowski,  "On definable sets of positive integers"  ''Fund. Math.'' , '''34'''  (1947)  pp. 81–112</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546049.png" /> is commonly denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k055/k055460/k05546050.png" />. One usually speaks of the arithmetical hierarchy (rather than the Kleene–Mostowski classification).
+
$  \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====
 
====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=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