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 |
Enumerated model. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Enumerated_model&oldid=46829