Model theory

The part of mathematical logic studying mathematical models (cf. Model (in logic)).

The origins of model theory go back to the 1920's and 1930's, when the following two fundamental theorems were proved.

Theorem 1

(Gödel compactness theorem). If each finite subcollection of a collection $T$ of propositions in a first-order language is consistent, then the whole collection $T$ is consistent (see [1]).

Theorem 2

(Löwenheim–Skolem theorem). If a collection of propositions in a first-order language of signature $\Omega$ has an infinite model, then it has a model of any infinite cardinality not less than the cardinality of $\Omega$.

Theorem 1 has had extensive application in algebra. On the basis of this theorem, A.I. Mal'tsev created a method of proof of local theorems in algebra (see Mal'tsev local theorems).

Let $A$ be an algebraic system of signature $\Omega$, let $|A|$ be the underlying set of $A$, let $X\subseteq|A|$, let $(\Omega,X)$ denote the signature obtained from $\Omega$ by the addition of symbols for distinguished elements $c_a$ for all $a\in X$, and let $(A,X)$ denote the algebraic system of signature $(\Omega,X)$ which is an enrichment of $A$ in which for each $a\in X$ the symbol $c_a$ is interpreted by the element $a$. The set $O(A)$ of all closed formulas of the signature $(\Omega,|A|)$ in a first-order language which are true in the system $(A,|A|)$ is called the elementary diagram of the algebraic system $A$ (or the description of the algebraic system $A$), and the set $D(A)$ of those formulas from $O(A)$ which are either atomic or the negation of an atomic formula is called the diagram of $A$. An algebraic system $B$ is called an elementary extension of $A$ if $|A|\subseteq|B|$ and if $(B,|A|)$ is a model for $O(A)$. In this case $A$ is called an elementary subsystem of $B$. For example, the set of rational numbers with the usual order relation is an elementary subsystem of the system of real numbers with the usual order relation.

A subsystem $A$ of an algebraic system $B$ of signature $\Omega$ is an elementary subsystem of $B$ if and only if for each closed formula $(\exists v)\Phi(v)$ in the first-order language of signature $(\Omega,|A|)$ which is true in $(B,|A|)$ there is an $a\in|A|$ such that $\Phi(c_a)$ is true in $(B,|A|)$. It follows at once from this criterion that the union of an increasing chain of elementary subsystems is an elementary extension of each of these subsystems. If a closed $\forall\exists$-formula in a first-order language is true in every system of an increasing chain of systems, then it is true in the union of the chain (see [1], [8]).

Let the signature $\Omega$ contain a one-place relation symbol $U$. One says that a model $A$ of a theory $T$ of signature $\Omega$ has type $(\alpha,\beta)$ if the cardinality of $|A|$ is equal to $\alpha$ and if the cardinality of $U(A)=\{a\in|A|: A\models U(a)\}$ is equal to $\beta$. Vaught's theorem: If an elementary theory $T$ of countable signature has a model of type $(\alpha,\beta)$ where $\alpha>\beta$, then $T$ has a model of type $(\aleph_1,\aleph_0)$ (see [7], [8], [10]). Under the assumption that the generalized continuum hypothesis holds, an elementary theory of countable signature has models of types $(\aleph_{\alpha+2},\aleph_{\alpha+1})$ for each $\alpha$, if it has a model of type $(\aleph_1,\aleph_0)$ (see [10]). Under the same assumption the theory ${\rm Th}(A)$, where the signature of $A$ is $(+,\,.\,,0,1,<,U)$, $|A|$ is the set of all real numbers, $U(A)$ the set of all integers, and $+,\,.\,,0,1,<$, are defined in the usual way, does not have a model of type $(\aleph_2,\aleph_0)$.

Let $(A,P)$ denote the enrichment of the algebraic system $A$ by a predicate $P$, and let $\Omega,P)$ be the signature obtained from $\Omega$ by the addition of the predicate symbol $P$. In many cases it is important to understand when in each member of a class $\mathcal K$ of algebraic systems of signature $(\Omega,P)$ the predicate $P$ is given by a formula in the first-order language of the signature $\Omega$. A partial answer to this question is given by Beth's definability theorem: There exists a formula $\Phi(x)$ in the first-order language of signature $\Omega$ such that the formula $(\forall x)(\Phi(x)\leftrightarrow P(x))$ is true for all members of an axiomatizable class $\mathcal K$ of signature $(\Omega,P)$ if and only if the set $\{P: (A,P)\in\mathcal K\}$ contains at most one element for each algebraic system $A$ of signature $\Omega$ (see [2], [8]).

Much research in model theory is connected with the study of properties preserved under operations on algebraic systems. The most important operations include homomorphism, direct and filtered products.

A statement $\Phi$ is said to be stable with respect to homomorphisms if the truth of $\Phi$ in an algebraic system $A$ implies the truth of $\Phi$ in all epimorphic images of $A$. A formula $\Phi$ in a first-order language is called positive if $\Phi$ does not contain negation and implication signs. It has been proved (see [1], [8]) that a statement $\Phi$ in a first-order language is stable relative to homomorphisms if and only if $\Phi$ is equivalent to a positive statement. A similar theorem holds for the language $L_{\omega_1\omega}$.

A formula $\Phi(x_1,\dots,x_n)$ in a first-order language of signature $\Omega$ is called a Horn formula if it can be obtained by conjunction and quantification from formulas of the form $(\Phi_1 \&\dots\&\Phi_s)\rightarrow\Phi$, $\neg(\Phi_1\&\dots\&\Phi_s)$, where $\Phi_1,\dots,\Phi_s$ are atomic formulas in the first-order language of $\Omega$. Examples of Horn formulas are identities and quasi-identities. Central in the theory of ultraproducts is the theorem of J. Łos: Every formula in a first-order language is stable with respect to any ultrafilter (see [1]). A formula in a first-order language is conditionally stable with respect to any filter if and only if it is equivalent to a Horn formula. There is the following theorem (see [9]): Two algebraic systems $A$ and $B$ of signature $\Omega$ are elementarily equivalent if and only if there is an ultrafilter $D$ on a set $I$ such that $A^I/D$ and $B^I/D$ are isomorphic. The cardinality of a filtered product is countably infinite if for each natural number $n$ the number of factors of cardinality $n$ is finite. If for each natural number $n$ the set of indices for which the corresponding factors have cardinality $n$ does not belong to $D$, then the cardinality of the ultraproduct with respect to a non-principal ultrafilter $D$ on a countable set $I$ is equal to that of the continuum. For each infinite set $I$ of cardinality $\alpha$ there is a filter $D$ on $I$ such that for each filter $D_1$ on $I$ containing $D$, and each infinite set $A$, the cardinality of $A^I/D$ is not less than $2^\alpha$ (see [1]).

Many applications have been found for the Ehrenfeucht–Mostowski theorem on the existence of models with a large number of automorphisms (see [3]): For any totally ordered set $X$ in an axiomatizable class $\mathcal K$ of algebraic systems containing an infinite system, there is a system $A$ such that $X\subseteq|A|$ and such that each order-preserving one-to-one mapping of $X$ onto $X$ can be extended to an automorphism of $A$.

The major notions in model theory are those of universal, homogeneous and saturated systems. Let $A$ and $B$ be algebraic systems of a signature $\Omega$. A mapping $f$ of a set $X\subseteq|A|$ into a set $Y\subseteq|B|$ is called elementary if for each formula $\Phi(x_1,\dots,x_n)$ in the first-order language of the signature $\Omega$ and any $a_1,\dots,a_n\in X$ the equivalence $A\models\Phi(x_1,\dots,x_n)\iff B\models\Phi(f(a_1),\dots,f(a_n))$ holds. A system $A$ is called $\alpha$-universal if for every system $B$ that is elementarily equivalent to $A$ and of cardinality not exceeding $\alpha$, there is an elementary mapping from $|B|$ into $|A|$. A system $A$ is called $\alpha$-homogeneous if for every set $X\subseteq|A|$ of cardinality less than $\alpha$, every elementary mapping from $X$ into $|A|$ can be extended to an elementary mapping of $|A|$ onto $|A|$ (that is, to an automorphism of $A$). A system $A$ of signature $\Omega$ is called $\alpha$-saturated if for every set $X\subseteq|A|$ of cardinality less than $\alpha$ and every collection $\Sigma$ of formulas in the first-order language of the signature $(\Omega,X)$ not containing free variables other than $x_0$, $\Sigma$ finitely satisfiable in $(A,X)$ implies that $\Sigma$ is satisfiable in $(A,X)$. A system $A$ is called universal (respectively, homogeneous or saturated) if $A$ is $\alpha$-universal (respectively, $\alpha$-homogeneous or $\alpha$-saturated), where $\alpha$ is the cardinality of $|A|$. A system is saturated if and only if it is simultaneously universal and homogeneous. Two elementary equivalent saturated systems of the same cardinality are isomorphic (see [3]). All uncountable models of elementary theories which are categorical in uncountable cardinalities (cf. Categoricity in cardinality) and of countable signature are saturated (Morley's theorem, see [3], [8]). A large number of examples of $\alpha$-saturated systems is given by ultraproducts. For example, if $D$ is a non-principal ultrafilter on a countable set $I$, then $\prod_{i\in I}A_i/D$ is an $\aleph_1$-saturated system for any algebraic system $A_i$ ($i\in I$) of a countable signature $\Omega$.

The basic problems of model theory are the study of the expressive possibilities of a formalized language and the study of classes of structures defined by means of such a language. Some important properties of stable theories have been found, and the classes of categorical and superstable theories have been studied in even more detail.

The basic apparatus for the study of stable theories is the classification of formulas and locally consistent sets of formulas in these theories. Such a classification can be obtained by means of ascribing to formulas their ranks. Such ranks are usually ordinals and the ranking functions are given with the help of special topologies and other means. The study of ranking functions and their improvements is a rich source of information on the theories.

In the study of classes of models one is concerned with the number of distinct models, up to isomorphism, of a theory of a given cardinality, the existence of special models, for example, simple, minimal, saturated, homogeneous, universal, etc., and one creates means for constructing them.

The classical examples of application of methods of model theory are the papers of A. Robinson and his school, which developed an independent science — non-standard analysis; from the work of Mal'tsev and his school the applications of model-theoretic methods to topological algebra have been developed; the latest results on the properties of stable theories have been used in the study of concrete algebraic questions.

The above problems arose also in the study of various non-elementary languages, for example, obtained by the addition of new quantifiers, the introduction of infinite expressions, modalities, etc.

References

[1]	A.I. Mal'tsev, "Algebraic systems" , Springer (1973) (Translated from Russian)
[2]	A. Robinson, "Introduction to model theory and to the metamathematics of algebra" , North-Holland (1963)
[3]	M.A. Taitslin, "Model theory" , Novosibirsk (1970) (In Russian)
[4]	Yu.L. Ershov, "Decidability problems and constructive models" , Moscow (1980) (In Russian)
[5]	Yu.A. Palyutin, "Mathematical logic" , Moscow (1979) (In Russian)
[6]	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
[7]	A.I. Mal'tsev, "Some problems in the theory of classes of models" , Proc. 4-th All-Union Math. Congress (1961) , 1 , Leningrad (1963) pp. 169–198 (In Russian) (Transl. in: Amer. Math. Soc. Transl. (2) 83 (1969), 1–48)
[8]	C.C. Chang, H.J. Keisler, "Model theory" , North-Holland (1973)
[9]	G.E. Sacks, "Saturated model theory" , Benjamin (1972)
[10]	R.L. Vaught, "Denumerable models of complete theories" , Infinitistic methods. Proc. Symp. Foundations of Math. Warsaw, 1959 , Pergamon (1961) pp. 303–321
[11]	M. Morley, R. Vaught, "Homogeneous universal models" Math. Scand. , 11 : 1 (1962) pp. 37–57
[12]	M. Morley, "Categoricity in power" Trans. Amer. Math. Soc. , 114 : 2 (1965) pp. 514–538
[13]	S. Shelah, "Classification theory and the number of non-isomorphic models" , North-Holland (1978)
[14]	J.L. Bell, A.B. Slomson, "Models and ultraproducts: an introduction" , North-Holland (1971)

Comments

Theorem 1 was proved by K. Gödel in [a1]. $\newcommand{\nmodels}{\mathop{\models}\limits}$

Let $\mathfrak A_i=(A_i,\{R_n(i)\})$, $i\in I$, be a collection of relational structures of the same type (algebraic systems of the same signature). (I.e. the $A_i$ are sets, the $R_n(i)$ relations.) Let $F$ be an ultrafilter on the index set $I$. Then the ultraproduct $(\prod_i A_i)/F$ is a relational structure of the same type. (Cf. (the editorial comments to) Ultrafilter for the definition of ultraproduct.)

A precise formulation of Łos' theorem is now as follows (cf. [a8] or [a9]). Let $f=(f_1,\dots,f_n,\dots)$ be a sequence of elements from $\prod A_i$, i.e. $f_n=(f_n(i))_{i\in I}\in\prod A_i$ for all $n$. Let $f/F$ be the sequence $(f_1/F,\dots,f_n/F,\dots)$ of elements from $(\prod A_i)/F$ and let $f(i)$ be the sequence $f(i)=(f_1(i),\dots,f_n(i),\dots)$. Then for any formula $\phi$ from the language $L$ for which the $\mathfrak A_i$ are interpretations, $$ (\prod A_i)/F\nmodels_{f/F}\phi\quad\iff\quad \{i\in I: \mathfrak A_i\nmodels_{f(i)}\phi\}\in F.$$

Łos' theorem is also called the fundamental theorem on ultraproducts.

The theorem to the effect that two algebraic systems $\mathfrak A$ and $\mathfrak B$ are equivalent if and only if they have isomorphic ultrapowers is known as the Keisler ultrapower theorem: see Keisler-Shelah isomorphism theorem.

One of the basic applications of logic to algebra is the work by J. Ax and S. Kochen [a2].

See [a3] for the model theory of infinitary languages; [a4], [a5] for stability theory; and [a6], [a7] for categorical model theory.

The Gödel compactness theorem and the Löwenheim–Skolem theorem are in the Russian literature sometimes known as the Gödel–Mal'tsev theorem and the Löwenheim–Skolem–Mal'tsev theorem, respectively.

References

[a1]	K. Gödel, "Die Vollständigheit der Axiome des logischen Funktionenkalküls" Monatshefte für Math. und Physik , 37 (1930) pp. 344–360
[a2]	J. Ax, S. Kochen, "Diophantine problems over local fields III: decidable fields" Ann. of Math. , 83 (1966) pp. 437–456
[a3]	M.A. Dickmann, "Large infinitary languages" , North-Holland (1975)
[a4]	A. Pillay, "An introduction to stability theory" , Oxford Univ. Press (1985)
[a5]	J.T. Baldwin, "Fundamentals of stability theory" , Springer (1988)
[a6]	G.E. Reges, "First order categorical logic" , Lect. notes in math. , 611 , Springer (1977)
[a7]	J. Lambek, P. Scott, "Higher order categorical logic" , Cambridge Univ. Press (1986)
[a8]	J.L. Bell, A.B. Slomson, "Models and ultraproducts" , North-Holland (1969)
[a9]	W.W. Comfort, S. Negrepontis, "The theory of ultrafilters" , Springer (1974) pp. §11