Enumerated model

A pair , where is a model of a certain fixed signature and is an enumeration of the underlying set of . 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 , or of the set , where is a certain Gödel enumeration of all formulas of the signature . Here the constants do not belong to , is the set of all closed formulas of that are true in the system which is obtained from by enriching to , the value of the constant being put equal to , and denotes the set of all quantifier-free formulas that are true in .

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 , , and , , denote, respectively, the arithmetic and analytic hierarchies relative to (cf. Hierarchy).

If a theory is recursive relative to and has a simple model , then there exists an enumeration of such that , that is is recursive with respect to the set of all Gödel numbers of those computable functions relative to for which is defined.

If is recursive relative to and has a countable saturated model , then there exists an enumeration of such that , that is, is a hyper-arithmetic set relative to ; 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 of complexity , that is

The Ershov hierarchy gives a finer classification of the sets in . The following theorem has been proved: For any there exists a non-contradictory formula that has no enumerated model with predicates in , that is, and , where . In a constructive non-atomic Boolean algebra one can construct a recursively-enumerable ideal (that is, the set is recursively enumerable) such that the Boolean algebra 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