Recursive model theory
recursively presented model theory
A branch of mathematics that is on the border-line between model theory, algebra and the theory of recursive functions (cf. Recursive function), and related to the study of questions of effectiveness in models and algebras.
A.I. Mal'tsev's article Constructive algebras [1] was the first overviewing work on recursively presented models. In it the basic concepts were developed and systematized, and the road to further development of this theory was indicated. A major role in the erection and development of this branch of mathematics was played by Yu.L. Ershov and his students, who solved a number of fundamental problems, worked out new concepts and determined new directions of research in recursive model theory (cf. [2]).
The basic notions and results in recursive model theory are formulated below. All considerations are, usually, in a fixed signature
![]() |
such that the function :
is recursive. When considering algebraic systems, function symbols may occur in the signature. The signature
![]() |
which is obtained from by adjoining a countable number of individual constants, is also used. It is always understood that
and that the predicate
is defined on any model as equality. Let
,
, be the collection of all formulas of restricted predicate calculus with equality
of signatures
,
, and let
be a fixed Gödel enumeration (cf. [3]) of
(
). A subset
is called decidable if the set
is recursive (cf. Recursive set theory). An enumerated model (of signature
) is a pair
, where
is a model of signature
and
is a enumeration of the underlying set
of
. An enumerated model
is called a recursively presented model if the set
![]() |
is recursive.
For each enumerated model one can construct some
-saturation
of
, i.e. a model of signature
, with underlying set that of
, with predicates from
in
coinciding with the corresponding predicates of
, and with constants defined by: As the element
, one takes
. Let
be the elementary theory of
, i.e. the set of closed formulas of signature
that are true on
. Let
be the elementary theory of the enumerated model
. An enumerated model
is called strongly recursively presented or decidable if
is a decidable theory. From the definition it is immediately clear that a strongly recursively presented model is recursively presented.
One of the basic problems in recursive model theory is the existence of recursively presented models with various elementary properties, i.e. with properties describable in the language of restricted predicate calculus. A number of interesting and important theorems have been obtained (1990) in this direction. The following yields the existence of a large class of strongly recursively presented models: If is a decidable theory, then there is a sequence of strongly recursively presented models
![]() |
such that and the set
is recursive. It has been noticed that there are formulas having no recursively presented models. The following two theorems give some sufficient conditions for the existence of recursively presented models for a theory with a recursively-enumerable set of axioms.
If is a recursively-enumerable
-theory having a model
with a recursively-enumerable
-theory, then
has a recursively presented model.
A theory of finite signature
is called
-finite if the universal theory of any extension
(of the same signature) is finitely axiomatizable (by universal statements). A theory
is called strongly
-finite if for any finite set
of individual constants the theory
is
-finite. Here
is defined to be
but now in the language of the signature
.
If a theory is strongly
-finite, and
is a recursively-enumerable extension of
, then
has a recursively presented model.
Another circle of problems is related to the existence, for a given model , of enumerations
such that
becomes a (strongly) recursively presented model. Models for which such an enumeration exists are called (strongly) recursively presentable, while the corresponding enumeration is called a (strong) recursive presentation. For the solution of a number of problems related to the recursive presentability of models, Ershov's kernel theorem turns out to be useful. Its application to concrete algebraic systems allows one to solve a number of natural problems. In particular, it has been established that: 1) any recursively presented locally nilpotent torsion-free group has a recursively presented completion; and 2) if
is a recursively presented field and
is an algebraic extension of
, then
extends to a recursive presentation of
if and only if the family of finite sets of polynomials over
in a countable number of variables, with roots in
, is recursively enumerable.
A large class of recursively presented models is given by the following theorem: Any countable model of an -categorical (cf. Categoricity in cardinality) decidable theory is strongly recursively presentable. The problem of the (strong) recursive presentability of special models of complete theories, in particular of simple and universal models, is of interest. Sufficient and necessary conditions for the (strong) recursive presentability of simple (and countable saturated) models of a complete theory have been found. Examples of complete theories with non-recursively presentable simple and universal models have been constructed. It has been proved that a simple model of a complete decidable theory that has a strongly recursively presentable universal model or a finite number of pairwise non-isomorphic countable models, is always strongly recursively presentable.
The question of the number of inequivalent recursive presentations for a given model has been investigated. Two recursive presentations and
of a model
are called (recursively) equivalent if there exists an isomorphism
(
) and a recursive function
such that
. A model is called self-stable (recursively stable) if any two recursive presentations of it are (recursively) equivalent.
For a large class of algebraic systems it has been proved that there exists either only one (up to equivalence) or a countable number of inequivalent recursive presentations [4], [5]. For the theories of fields, Boolean algebras, torsion-free Abelian groups, and some other classes of algebraic systems the question of the number of inequivalent recursive presentations has been solved completely [11], and the self-stable models have been described [2]. It has also been demonstrated that questions of self-stability are related to the study of computability of classes of recursively presented models.
References
[1] | A.I. Mal'tsev, "Constructive algebras I" Russian Math. Surveys , 16 : 3 (1961) pp. 77–129 ((Also in: A.I. Mal'cev, The metamathematics of algebraic systems, North-Holland, 1971, Chapt. 18)) Uspekhi Mat. Nauk , 16 : 3 (1962) pp. 3–60 |
[2] | Yu.L. Ershov, "Theory of enumerations" , 3. Constructive models , Novosibirsk (1974) (In Russian) |
[3] | Yu.L. Ershov, I.A. Lavrov, A.D. Taimanov, M.A. Taitslin, "Elementary theories" Russian Math. Surveys , 20 : 4 (1965) pp. 35–105 Uspekhi Mat. Nauk , 20 : 4 (1965) pp. 37–108 |
[4] | S.S. Goncharov, "Selfstability, and computable families of constructivizations" Algebra and Logic , 14 : 6 (1975) pp. 392–408 Algebra i Logika , 14 : 6 (1975) pp. 647–680 |
[5] | A.T. Nurtazin, "Strong and weak constructivizations, and enumerable families" Algebra and Logic , 13 : 3 (1974) pp. 177–184 Algebra i Logika , 13 : 3 (1974) pp. 311–323 |
[6] | A. Cobham, , Summaries of talks presented at the summer institute for symbolic logic Cornell University, 1957 , Washington, D.C. (1960) pp. 391–395 |
[7] | A. Fröhlich, J.C. Shepherdson, "Effective procedures in field theory" Phil. Trans. Royal. Soc. London Ser. A. , 2458 (1956) pp. 407–428 |
[8] | A. Mostowski, "A formula with no recursively enumerable model" Fund. Math. , 42 : 1 (1955) pp. 125–140 |
[9] | M.O. Rabin, "Computable algebra, general theory and theory of computable fields" Trans. Amer. Math. Soc. , 95 : 2 (1960) pp. 341–360 |
[10] | R.L. Vaught, "Sentences true in all constructive models" J. Symb. Logic , 25 : 1 (1960) pp. 39–58 |
[11] | S.S. Goncharov, "Problem of the number of non-self-equivalent constructivizations" Algebra and Logic , 19 : 6 (1980) pp. 401–414 Algebra i Logika , 19 : 6 (1980) pp. 621–639 |
Comments
The theory of recursive functions can be mixed with model theory in several ways. First, one can study recursive models, i.e. models (corresponding to a recursive vocabulary) over the natural numbers with all of their relations and functions recursive. By the Gödel completeness theorem, every consistent (first-order) sentence has a model. However, not every such sentence has a recursive model (Mostowski's theorem). There are conditions under which recursive models exist, e.g., each recursively enumerable -theory allowing a model with a recursively enumerable
-theory has a recursive model also. And each countable model of an
-categorical decidable theory has an equivalent
which is strongly recursive in the sense that the theory of its expansion
is decidable. By the Gödel incompleteness theorem, Peano's arithmetic has many models besides its standard (recursive) one, although none of these is recursive (Tennenbaum's theorem). However, the subject is broader than just the study of recursive models. For instance, one can try to "effectivize" model-theoretic results. E.g.: by the interpolation theorem, for every valid (first-order) implication
there exists an "interpolant"
whose vocabulary is contained in the common part of those of
and
such that both
and
are valid. Such an interpolant cannot always be obtained recursively from
and
(Friedman's theorem). By Lindenbaum's theorem, every consistent (first-order) theory has a complete extension. How complex will this extension be, given that the initial theory is (say) recursive? (Answer:
(cf. Descriptive set theory) suffices. Note that, by a theorem of Tarski, the complete theory of the standard model of arithmetic is not even arithmetical.)
Recursive model theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Recursive_model_theory&oldid=48458