Namespaces
Variants
Actions

Difference between revisions of "Enumerated model"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fixing superscripts)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357901.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357902.png" /> is a model of a certain fixed signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357903.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357904.png" /> is an [[Enumeration|enumeration]] of the underlying set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357905.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357906.png" />. The most extensively developed trend in the study of enumerated models is [[Recursive model theory|recursive model theory]]. Another is the investigation of the problem of the complexity of an enumerated model, by which one means the complexity of the set of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357907.png" />, or of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357908.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e0357909.png" /> is a certain Gödel enumeration of all formulas of the signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579010.png" />. Here the constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579011.png" /> do not belong to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579013.png" /> is the set of all closed formulas of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579014.png" /> that are true in the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579015.png" /> which is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579016.png" /> by enriching <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579017.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579018.png" />, the value of the constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579019.png" /> being put equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579020.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579021.png" /> denotes the set of all quantifier-free formulas that are true in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579022.png" />.
+
<!--
 +
e0357901.png
 +
$#A+1 = 64 n = 0
 +
$#C+1 = 64 : ~/encyclopedia/old_files/data/E035/E.0305790 Enumerated model
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
Various special models of elementary theories (cf. [[Elementary theory|Elementary theory]]) play an important role in mathematical logic and algebra. One of the important problems is that of their complexity. The following results have been obtained. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579028.png" /> denote, respectively, the arithmetic and analytic hierarchies relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579029.png" /> (cf. [[Hierarchy|Hierarchy]]).
+
{{TEX|auto}}
 +
{{TEX|done}}
  
If a theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579030.png" /> is recursive relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579031.png" /> and has a simple model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579032.png" />, then there exists an enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579033.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579034.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579035.png" />, that is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579036.png" /> is recursive with respect to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579037.png" /> of all Gödel numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579038.png" /> of those computable functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579039.png" /> relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579040.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579041.png" /> is defined.
+
A pair  $  ( \mathfrak M , \nu ) $,
 +
where  $  \mathfrak M $
 +
is a model of a certain fixed signature  $  \sigma _ {0} $
 +
and  $  \nu $
 +
is an [[Enumeration|enumeration]] of the underlying set  $  M $
 +
of  $  \mathfrak M $.  
 +
The most extensively developed trend in the study of enumerated models is [[Recursive model theory|recursive model theory]]. Another is the investigation of the problem of the complexity of an enumerated model, by which one means the complexity of the set of natural numbers  $  \gamma  ^ {-1} (  \mathop{\rm Th} ( \mathfrak M , \nu )) $,
 +
or of the set  $  \gamma  ^ {-1} (  \mathop{\rm Th} _ {0} ( \mathfrak M , \nu )) $,  
 +
where  $  \gamma $
 +
is a certain Gödel enumeration of all formulas of the signature  $  \sigma = \sigma _ {0} \cup \{ c _ {0} \dots c _ {n} ,\dots \} $.  
 +
Here the constants  $  c _ {n} $
 +
do not belong to  $  \sigma _ {0} $,
 +
$  \mathop{\rm Th} ( \mathfrak M , \nu ) $
 +
is the set of all closed formulas of  $  \sigma $
 +
that are true in the system  $  \mathfrak M _  \nu  $
 +
which is obtained from  $  \mathfrak M $
 +
by enriching  $  \sigma _ {0} $
 +
to  $  \sigma $,
 +
the value of the constant  $  c _ {n} $
 +
being put equal to $  \nu ( n) $,
 +
and  $  \mathop{\rm Th} _ {0} ( \mathfrak M , \nu ) $
 +
denotes the set of all quantifier-free formulas that are true in  $  \mathfrak M _  \nu  $.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579042.png" /> is recursive relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579043.png" /> and has a countable saturated model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579044.png" />, then there exists an enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579045.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579046.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579047.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579048.png" /> is a hyper-arithmetic set relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579049.png" />; these bounds on the complexity are in a certain sense exact.
+
Various special models of elementary theories (cf. [[Elementary theory|Elementary theory]]) play an important role in mathematical logic and algebra. One of the important problems is that of their complexity. The following results have been obtained. Let  $  \Sigma _ {n}  ^ {A} $,
 +
$  \Pi _ {n}  ^ {A} $,
 +
$  \Delta _ {n}  ^ {A} $
 +
and $  \Sigma _ {n}  ^ {1,A} $,
 +
$  \Pi _ {n}  ^ {1,A} $,
 +
$  \Delta _ {n}  ^ {1,A} $
 +
denote, respectively, the arithmetic and analytic hierarchies relative to $  A $ (cf. [[Hierarchy|Hierarchy]]).
  
The following result is also connected with the task of finding exact bounds. It is known that every non-contradictory formula has an enumerated model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579050.png" /> of complexity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579051.png" />, that is
+
If a theory  $  T $
 +
is recursive relative to  $  A $
 +
and has a simple model  $  \mathfrak M $,
 +
then there exists an enumeration  $  \nu $
 +
of $  \mathfrak M $
 +
such that $  \gamma  ^ {-1} (  \mathop{\rm Th} ( \mathfrak M , \nu )) \in \Delta _ {2}  ^ {A} $,  
 +
that is $  \gamma  ^ {-1} (  \mathop{\rm Th} ( \mathfrak M , \nu )) $
 +
is recursive with respect to the set  $  A  ^  \prime  $
 +
of all Gödel numbers  $  x $
 +
of those computable functions  $  \phi _ {x}  ^ {A} $
 +
relative to  $  A $
 +
for which  $  \phi _ {x}  ^ {A} ( x) $
 +
is defined.
  
<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/e/e035/e035790/e03579052.png" /></td> </tr></table>
+
If  $  T $
 +
is recursive relative to  $  A $
 +
and has a countable saturated model  $  \mathfrak M $,
 +
then there exists an enumeration  $  \nu $
 +
of  $  \mathfrak M $
 +
such that  $  \gamma  ^ {-1} (  \mathop{\rm Th} ( \mathfrak M , \nu )) \in \Delta _ {1}  ^ {1,A} $,
 +
that is,  $  \gamma  ^ {-1} (  \mathop{\rm Th} ( \mathfrak M , \nu )) $
 +
is a hyper-arithmetic set relative to  $  A $;  
 +
these bounds on the complexity are in a certain sense exact.
  
The Ershov hierarchy gives a finer classification of the sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579053.png" />. The following theorem has been proved: For any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579054.png" /> there exists a non-contradictory formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579055.png" /> that has no enumerated model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579056.png" /> with predicates in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579057.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579059.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579060.png" />. In a constructive non-atomic Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579061.png" /> one can construct a recursively-enumerable ideal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579062.png" /> (that is, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579063.png" /> is recursively enumerable) such that the Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035790/e03579064.png" /> is not constructive. This makes it possible to prove that the lattice of recursively-enumerable sets is not recursively presentable.
+
The following result is also connected with the task of finding exact bounds. It is known that every non-contradictory formula has an enumerated model  $  ( \mathfrak M , \nu ) $
 +
of complexity  $  \Delta _ {2}  ^ {0} $,
 +
that is
 +
 
 +
$$
 +
\gamma  ^ {-1} (  \mathop{\rm Th} ( \mathfrak M , \nu ))  \in  \Delta _ {2}  ^ {0} .
 +
$$
 +
 
 +
The Ershov hierarchy gives a finer classification of the sets in $  \Delta _ {2}  ^ {0} $.  
 +
The following theorem has been proved: For any $  n $
 +
there exists a non-contradictory formula $  \phi _ {n} $
 +
that has no enumerated model $  ( \mathfrak M , \nu ) $
 +
with predicates in $  \Sigma _ {n}  ^ {-1} $,  
 +
that is, $  \nu  ^ {-1} ( P _ {i} ) \in \Sigma _ {n}  ^ {-1} $
 +
and $  \mathfrak M \vdash \phi _ {n} $,  
 +
where $  \sigma _ {0} = \langle  P _ {1} , P _ {2} , P _ {3} , P _ {4} \rangle $.  
 +
In a constructive non-atomic Boolean algebra $  ( \mathfrak M , \nu ) $
 +
one can construct a recursively-enumerable ideal $  I $ (that is, the set $  \nu  ^ {-1} ( I) $
 +
is recursively enumerable) such that the Boolean algebra $  \mathfrak M /I $
 +
is not constructive. This makes it possible to prove that the lattice of recursively-enumerable sets is not recursively presentable.
  
 
The study of enumerated total orders has made it possible to disprove the conjecture of the strong homogeneity of the Turing degrees.
 
The study of enumerated total orders has made it possible to disprove the conjecture of the strong homogeneity of the Turing degrees.

Latest revision as of 10:15, 21 March 2022


A pair $ ( \mathfrak M , \nu ) $, where $ \mathfrak M $ is a model of a certain fixed signature $ \sigma _ {0} $ and $ \nu $ is an enumeration of the underlying set $ M $ of $ \mathfrak M $. The most extensively developed trend in the study of enumerated models is recursive model theory. Another is the investigation of the problem of the complexity of an enumerated model, by which one means the complexity of the set of natural numbers $ \gamma ^ {-1} ( \mathop{\rm Th} ( \mathfrak M , \nu )) $, or of the set $ \gamma ^ {-1} ( \mathop{\rm Th} _ {0} ( \mathfrak M , \nu )) $, where $ \gamma $ is a certain Gödel enumeration of all formulas of the signature $ \sigma = \sigma _ {0} \cup \{ c _ {0} \dots c _ {n} ,\dots \} $. Here the constants $ c _ {n} $ do not belong to $ \sigma _ {0} $, $ \mathop{\rm Th} ( \mathfrak M , \nu ) $ is the set of all closed formulas of $ \sigma $ that are true in the system $ \mathfrak M _ \nu $ which is obtained from $ \mathfrak M $ by enriching $ \sigma _ {0} $ to $ \sigma $, the value of the constant $ c _ {n} $ being put equal to $ \nu ( n) $, and $ \mathop{\rm Th} _ {0} ( \mathfrak M , \nu ) $ denotes the set of all quantifier-free formulas that are true in $ \mathfrak M _ \nu $.

Various special models of elementary theories (cf. Elementary theory) play an important role in mathematical logic and algebra. One of the important problems is that of their complexity. The following results have been obtained. Let $ \Sigma _ {n} ^ {A} $, $ \Pi _ {n} ^ {A} $, $ \Delta _ {n} ^ {A} $ and $ \Sigma _ {n} ^ {1,A} $, $ \Pi _ {n} ^ {1,A} $, $ \Delta _ {n} ^ {1,A} $ denote, respectively, the arithmetic and analytic hierarchies relative to $ A $ (cf. Hierarchy).

If a theory $ T $ is recursive relative to $ A $ and has a simple model $ \mathfrak M $, then there exists an enumeration $ \nu $ of $ \mathfrak M $ such that $ \gamma ^ {-1} ( \mathop{\rm Th} ( \mathfrak M , \nu )) \in \Delta _ {2} ^ {A} $, that is $ \gamma ^ {-1} ( \mathop{\rm Th} ( \mathfrak M , \nu )) $ is recursive with respect to the set $ A ^ \prime $ of all Gödel numbers $ x $ of those computable functions $ \phi _ {x} ^ {A} $ relative to $ A $ for which $ \phi _ {x} ^ {A} ( x) $ is defined.

If $ T $ is recursive relative to $ A $ and has a countable saturated model $ \mathfrak M $, then there exists an enumeration $ \nu $ of $ \mathfrak M $ such that $ \gamma ^ {-1} ( \mathop{\rm Th} ( \mathfrak M , \nu )) \in \Delta _ {1} ^ {1,A} $, that is, $ \gamma ^ {-1} ( \mathop{\rm Th} ( \mathfrak M , \nu )) $ is a hyper-arithmetic set relative to $ A $; these bounds on the complexity are in a certain sense exact.

The following result is also connected with the task of finding exact bounds. It is known that every non-contradictory formula has an enumerated model $ ( \mathfrak M , \nu ) $ of complexity $ \Delta _ {2} ^ {0} $, that is

$$ \gamma ^ {-1} ( \mathop{\rm Th} ( \mathfrak M , \nu )) \in \Delta _ {2} ^ {0} . $$

The Ershov hierarchy gives a finer classification of the sets in $ \Delta _ {2} ^ {0} $. The following theorem has been proved: For any $ n $ there exists a non-contradictory formula $ \phi _ {n} $ that has no enumerated model $ ( \mathfrak M , \nu ) $ with predicates in $ \Sigma _ {n} ^ {-1} $, that is, $ \nu ^ {-1} ( P _ {i} ) \in \Sigma _ {n} ^ {-1} $ and $ \mathfrak M \vdash \phi _ {n} $, where $ \sigma _ {0} = \langle P _ {1} , P _ {2} , P _ {3} , P _ {4} \rangle $. In a constructive non-atomic Boolean algebra $ ( \mathfrak M , \nu ) $ one can construct a recursively-enumerable ideal $ I $ (that is, the set $ \nu ^ {-1} ( I) $ is recursively enumerable) such that the Boolean algebra $ \mathfrak M /I $ is not constructive. This makes it possible to prove that the lattice of recursively-enumerable sets is not recursively presentable.

The study of enumerated total orders has made it possible to disprove the conjecture of the strong homogeneity of the Turing degrees.

References

[1] S.S. Goncharov, B.N. Drobotun, "Numerations of saturated and homogeneous models" Siberian Math. J. , 21 (1980) pp. 183–190 Sibirsk. Mat. Zh. , 21 : 2 (1980) pp. 25–41
[2] S.D. Denisov, "Models of a non-contradictory formula and the hierarchy of Eshov" Algebra and Logic , 11 (1972) pp. 359–362 Algebra i Logika , 11 : 6 (1972) pp. 648–655
[3] B.N. Drobotun, "Enumerations of simple models" Siberian Math. J. , 18 (1977) pp. 707–716 (In Russian) Sibirsk. Mat. Zh. , 18 : 5 (1977) pp. 1002–1014
[4] Yu.L. Ershov, "Theorie der Numierungen" , I-II , Deutsch. Verlag Wissenschaft. (1973–1976) (Translated from Russian)
[5] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
[6] L. Feiner, "Hierarchies of Boolean algebras" J. Symbolic Logic , 35 (1970) pp. 365–374
[7] L. Feiner, "The strong homogeneity conjecture" J. Symbolic Logic , 35 (1970) pp. 375–377
How to Cite This Entry:
Enumerated model. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Enumerated_model&oldid=18678
This article was adapted from an original article by S.S. Goncharov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article