Namespaces
Variants
Actions

Difference between revisions of "Model theory"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎Theorem 1: texification)
m (correction)
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
 +
{{TEX|done}}
 +
 
The part of mathematical logic studying mathematical models (cf. [[Model (in logic)|Model (in logic)]]).
 
The part of mathematical logic studying mathematical models (cf. [[Model (in logic)|Model (in logic)]]).
  
Line 7: Line 10:
  
 
===Theorem 2===
 
===Theorem 2===
(Löwenheim–Skolem theorem). If a collection of propositions in a first-order language of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m0643903.png" /> has an infinite model, then it has a model of any infinite cardinality not less than the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m0643904.png" />.
+
 
 +
(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|Mal'tsev local theorems]]).
 
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|Mal'tsev local theorems]]).
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m0643905.png" /> be an [[Algebraic system|algebraic system]] of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m0643906.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m0643907.png" /> be the underlying set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m0643908.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m0643909.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439010.png" /> denote the signature obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439011.png" /> by the addition of symbols for distinguished elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439012.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439013.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439014.png" /> denote the algebraic system of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439015.png" /> which is an enrichment of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439016.png" /> in which for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439017.png" /> the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439018.png" /> is interpreted by the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439019.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439020.png" /> of all closed formulas of the signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439021.png" /> in a first-order language which are true in the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439022.png" /> is called the elementary diagram of the algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439023.png" /> (or the description of the algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439024.png" />), and the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439025.png" /> of those formulas from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439026.png" /> which are either atomic or the negation of an atomic formula is called the diagram of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439027.png" />. An algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439028.png" /> is called an elementary extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439029.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439030.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439031.png" /> is a model for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439032.png" />. In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439033.png" /> is called an elementary subsystem of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439034.png" />. 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.
+
Let $A$ be an [[Algebraic system|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439035.png" /> of an algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439036.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439037.png" /> is an elementary subsystem of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439038.png" /> if and only if for each closed formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439039.png" /> in the first-order language of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439040.png" /> which is true in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439041.png" /> there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439042.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439043.png" /> is true in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439044.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439045.png" />-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 [[#References|[1]]], [[#References|[8]]]).
+
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 [[#References|[1]]], [[#References|[8]]]).
  
Let the signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439046.png" /> contain a one-place relation symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439047.png" />. One says that a model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439048.png" /> of a theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439049.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439050.png" /> has type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439052.png" /> if the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439053.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439054.png" /> and if the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439055.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439056.png" />. Vaught's theorem: If an elementary theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439057.png" /> of countable signature has a model of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439058.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439059.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439060.png" /> has a model of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439061.png" /> (see [[#References|[7]]], [[#References|[8]]], [[#References|[10]]]). Under the assumption that the generalized [[Continuum hypothesis|continuum hypothesis]] holds, an [[Elementary theory|elementary theory]] of countable signature has models of types <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439062.png" /> for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439063.png" />, if it has a model of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439064.png" /> (see [[#References|[10]]]). Under the same assumption the theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439065.png" />, where the signature of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439066.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439068.png" /> is the set of all real numbers, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439069.png" /> the set of all integers, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439070.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439071.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439072.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439073.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439074.png" /> are defined in the usual way, does not have a model of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439075.png" />.
+
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 [[#References|[7]]], [[#References|[8]]], [[#References|[10]]]). Under the assumption that the generalized [[Continuum hypothesis|continuum hypothesis]] holds, an [[Elementary theory|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 [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439076.png" /> denote the enrichment of the algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439077.png" /> by a predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439078.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439079.png" /> be the signature obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439080.png" /> by the addition of the predicate symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439081.png" />. In many cases it is important to understand when in each member of a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439082.png" /> of algebraic systems of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439083.png" /> the predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439084.png" /> is given by a formula in the first-order language of the signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439085.png" />. A partial answer to this question is given by Beth's definability theorem: There exists a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439086.png" /> in the first-order language of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439087.png" /> such that the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439088.png" /> is true for all members of an axiomatizable class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439089.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439090.png" /> if and only if the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439091.png" /> contains at most one element for each algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439092.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439093.png" /> (see [[#References|[2]]], [[#References|[8]]]).
+
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 [[#References|[2]]], [[#References|[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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439094.png" /> is said to be stable with respect to homomorphisms if the truth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439095.png" /> in an algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439096.png" /> implies the truth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439097.png" /> in all epimorphic images of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439098.png" />. A formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m06439099.png" /> in a first-order language is called positive if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390100.png" /> does not contain negation and implication signs. It has been proved (see [[#References|[1]]], [[#References|[8]]]) that a statement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390101.png" /> in a first-order language is stable relative to homomorphisms if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390102.png" /> is equivalent to a positive statement. A similar theorem holds for the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390103.png" />.
+
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 [[#References|[1]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390104.png" /> in a first-order language of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390105.png" /> is called a Horn formula it it can be obtained by conjunction and quantification from formulas of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390106.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390107.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390108.png" /> are atomic formulas in the first-order language of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390109.png" />. 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|ultrafilter]] (see [[#References|[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 [[#References|[9]]]): Two algebraic systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390110.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390111.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390112.png" /> are elementarily equivalent if and only if there is an ultrafilter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390113.png" /> on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390114.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390115.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390116.png" /> are isomorphic. The cardinality of a filtered product is countably infinite if for each natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390117.png" /> the number of factors of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390118.png" /> is finite. If for each natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390119.png" /> the set of indices for which the corresponding factors have cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390120.png" /> does not belong to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390121.png" />, then the cardinality of the ultraproduct with respect to a non-principal ultrafilter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390122.png" /> on a countable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390123.png" /> is equal to that of the continuum. For each infinite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390124.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390125.png" /> there is a filter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390126.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390127.png" /> such that for each filter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390128.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390129.png" /> containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390130.png" />, and each infinite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390131.png" />, the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390132.png" /> is not less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390133.png" /> (see [[#References|[1]]]).
+
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|ultrafilter]] (see [[#References|[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 [[#References|[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 [[#References|[1]]]).
  
Many applications have been found for the Ehrenfeucht–Mostowski theorem on the existence of models with a large number of automorphisms (see [[#References|[3]]]): For any totally ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390134.png" /> in an axiomatizable class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390135.png" /> of algebraic systems containing an infinite system, there is a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390136.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390137.png" /> and such that each order-preserving one-to-one mapping of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390138.png" /> onto <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390139.png" /> can be extended to an automorphism of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390140.png" />.
+
Many applications have been found for the Ehrenfeucht–Mostowski theorem on the existence of models with a large number of automorphisms (see [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390141.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390142.png" /> be algebraic systems of a signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390143.png" />. A mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390144.png" /> of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390145.png" /> into a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390146.png" /> is called elementary if for each formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390147.png" /> in the first-order language of the signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390148.png" /> and any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390149.png" /> the equivalence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390150.png" /> holds. A system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390151.png" /> is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390153.png" />-universal if for every system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390154.png" /> that is elementarily equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390155.png" /> and of cardinality not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390156.png" />, there is an elementary mapping from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390157.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390158.png" />. A system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390159.png" /> is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390161.png" />-homogeneous if for every set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390162.png" /> of cardinality less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390163.png" />, every elementary mapping from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390164.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390165.png" /> can be extended to an elementary mapping of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390166.png" /> onto <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390167.png" /> (that is, to an [[Automorphism|automorphism]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390168.png" />). A system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390169.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390170.png" /> is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390172.png" />-saturated if for every set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390173.png" /> of cardinality less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390174.png" /> and every collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390175.png" /> of formulas in the first-order language of the signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390176.png" /> not containing free variables other than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390177.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390178.png" /> finitely satisfiable in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390179.png" /> implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390180.png" /> is satisfiable in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390181.png" />. A system is called universal (respectively, homogeneous or saturated) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390182.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390183.png" />-universal (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390184.png" />-homogeneous or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390185.png" />-saturated), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390186.png" /> is the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390187.png" />. 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 [[#References|[3]]]). All uncountable models of elementary theories which are categorical in uncountable cardinalities (cf. [[Categoricity in cardinality|Categoricity in cardinality]]) and of countable signature are saturated (Morley's theorem, see [[#References|[3]]], [[#References|[8]]]). A large number of examples of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390188.png" />-saturated systems is given by ultraproducts. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390189.png" /> is a non-principal ultrafilter on a countable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390190.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390191.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390192.png" />-saturated system for any algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390193.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390194.png" />) of a countable signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390195.png" />.
+
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|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 [[#References|[3]]]). All uncountable models of elementary theories which are categorical in uncountable cardinalities (cf. [[Categoricity in cardinality|Categoricity in cardinality]]) and of countable signature are saturated (Morley's theorem, see [[#References|[3]]], [[#References|[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 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.
Line 46: Line 50:
 
====Comments====
 
====Comments====
 
Theorem 1 was proved by K. Gödel in [[#References|[a1]]].
 
Theorem 1 was proved by K. Gödel in [[#References|[a1]]].
 +
$\newcommand{\nmodels}{\mathop{\models}\limits}$
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390196.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390197.png" />, be a collection of relational structures of the same type (algebraic systems of the same signature). (I.e. the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390198.png" /> are sets, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390199.png" /> relations.) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390200.png" /> be an [[Ultrafilter|ultrafilter]] on the index set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390201.png" />. Then the ultraproduct <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390202.png" /> is a relational structure of the same type. (Cf. (the editorial comments to) [[Ultrafilter|Ultrafilter]] for the definition of ultraproduct.)
+
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|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|Ultrafilter]] for the definition of ultraproduct.)
 
 
A precise formulation of Łos' theorem is now as follows (cf. [[#References|[a8]]] or [[#References|[a9]]]). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390203.png" /> be a sequence of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390204.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390205.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390206.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390207.png" /> be the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390208.png" /> of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390209.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390210.png" /> be the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390211.png" />. Then for any formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390212.png" /> from the language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390213.png" /> for which the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390214.png" /> are interpretations,
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390215.png" /></td> </tr></table>
+
A precise formulation of Łos' theorem is now as follows (cf. [[#References|[a8]]] or [[#References|[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.
 
Łos' theorem is also called the fundamental theorem on ultraproducts.
  
The theorem to the effect that two algebraic systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390216.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064390/m064390217.png" /> are equivalent if and only if they have isomorphic ultrapowers is known as the Keisler ultrapower theorem.
+
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 [[#References|[a2]]].
 
One of the basic applications of logic to algebra is the work by J. Ax and S. Kochen [[#References|[a2]]].

Latest revision as of 15:19, 16 December 2020


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
How to Cite This Entry:
Model theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Model_theory&oldid=30755
This article was adapted from an original article by A.D. TaimanovM.A. Taitslin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article