Enumerated model

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