View source for Enumerated model

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" />.

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]]).

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.

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.

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

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

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 study of enumerated total orders has made it possible to disprove the conjecture of the strong homogeneity of the Turing degrees.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  Yu.L. Ershov,   "Theorie der Numierungen" , '''I-II''' , Deutsch. Verlag Wissenschaft.  (1973–1976)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  L. Feiner,   "Hierarchies of Boolean algebras"  ''J. Symbolic Logic'' , '''35'''  (1970)  pp. 365–374</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  L. Feiner,   "The strong homogeneity conjecture"  ''J. Symbolic Logic'' , '''35'''  (1970)  pp. 375–377</TD></TR></table>