MODEL THEORY

:''This article discusses model theory as a mathematical discipline and 'not' the informally used term mathematical model as used in other parts of mathematics and science.''
In mathematics, 'model theory' is the study of mathematical structures via logical formulas. Model theory uses results about the logical properties of a language to get results about objects (structures, sets) that the language can describe.
For example:

★ One can classify structures depending on which sentences are true in them. This is generally a coarser classification than isomorphism classes.

★ One can classify sets of sentences depending on properties of classes of structures which satisfy them.

★ One has methods for finding or constructing structures satisfying a given set of sentences.

★ Given a structure, one can consider the sets definable within it via logical formulas. One can ask whether these sets have a "good" geometry.
This article focuses on finitary first order model theory of infinite structures. The model theoretic study of finite structures (for which see finite model theory) diverges significantly from the study of infinite structures both in terms of the problems studied and the techniques used. Model theory in higher-order logics or infinitary logics is hampered by the fact that completeness does not in general hold for these logics. However, a great deal of study has also been done in such languages.

Contents

Preliminaries

Languages and structures

Theories and pseudo-elementary classes

Formulae and definable sets

The areas of model theory

Methods of early applied model theory

Elimination of quantifiers and model completeness

Interpretability

Ultraproduct constructions

Methods of classical model theory

Using the compactness and completeness theorems

Types

Elementary embeddings

Ehrenfeucht-Fraïssé games and Scott sentences

Saturated and prime models, omitting types

Categoricity

Model completion, model companions

Shelah's classification program

Methods of geometric model theory

Model theory and set theory

Computable model theory

See also

References

Preliminaries

Model theory recognises, and is intimately concerned with a duality: we consider syntactical elements (of a language) and the corresponding semantical elements.

Languages and structures

The syntactical object we need is a language. This consists of some logical symbols, a list of non-logical symbols known as the signature, and grammatical rules which govern the formation of formulae and sentences.
Let $L$ be a language, and $M$ a set. Then we can make $M$ into an $L$-structure by giving an interpretation to each of the non-logical symbols of $L$. The grammatical rules of $L$ are designed so that one can then give each formula and sentence of $L$ a meaning on $M$. The class of $L$-structures together with, for each structure, the interpretations of the symbols, formulae and sentences are the semantical objects which correspond to the language.
Examples.

★ Consider the first order language with non-logical symbols $\{\; imes,\; +,\; -,\; 0,\; 1\; \}$, where the grammar is arranged so that $imes$ and $+$ are binary operation symbols, $-$ is a unary operation symbol and $0$ and $1$ are both constant symbols.
Then if $M$ is a set, $f\_1,f\_2:M^2\; o\; M$ are any binary functions, $f\_3$ is any unary function, and $m\_0,m\_1$ are elements of $M$ then we can make $M$ an $L$-structure by interpreting $imes$ by $f\_1$, $+$ by $f\_2$, $-$ by $f\_3$, $0$ by $m\_0$ and $1$ by $m\_1$.
For example we can take the set of real numbers and interpret the symbols of $L$ by their usual meanings in the real numbers. If we ask a question such as "∃''y'' (''y'' × ''y'' = 1 + 1)" in this language, then it is clear that the sentence is true for the reals - there is such a real number ''y'', namely the square root of 2.
One can also make the rational numbers into a model (with the standard meanings for the symbols on the rationals). Then the sentence considered above is false for the rationals. A similar proposition, "∃''y'' (''y'' × ''y'' = − 1)", is false in the reals, but is true in the complex numbers, where ''i'' × ''i'' = − 1.

Theories and pseudo-elementary classes

A 'theory' in the language ''L'', or '''L''-theory', is defined as a set of sentences in the language ''L'', and is called a 'closed theory' if the set of sentences is closed under the usual rules of inference.
For example, the set of all sentences true in some particular ''L''-structure ''M'' (e.g. the reals) is a closed ''L''-theory, and is called 'the theory of ''M''.
A 'model' of an ''L''-theory ''T'' consists of an ''L''-structure in which all sentences of
''T'' are true, normally defined by means of a T-schema.
A theory is said to be 'satisfiable' if it has a model. A theory is 'consistent' if its closure (under the usual rules of inference) does not contain a contradiction. One way of stating the completeness theorem is the following: A theory is satisfiable if and only if it is consistent.
A theory is a syntactic object, and the collection of all models of the theory is called a 'pseudo-elementary class', and is the corresponding semantical object.
For example, the language of partial orders has just one binary relation ≥. So a structure of the ''language'' of partial orders is just a set with a binary relation denoted by ≥, and it is a model of the ''theory'' of partial orders so long as it satisfies the axioms of a partial order.

Formulae and definable sets

We said earlier that when we fix an $L$-structure, all the sentences and formulae are given a meaning. The sentences are either true or false, but the formulae have a different meaning. Formulae contain free variables, and these must be assigned a meaning before we can ascertain their veracity. An example in plain English is the following: 'it is red' (applied to the real world). Only when we substitute the name of a particular object can we ascertain whether this formula is true. The above formula divides the world into the set of things which are red, and the set of things which are not red. This is the function of formulae: for a given $L$-formula $phi(x\_1,ldots,x\_n)$, $L$-structure $M$, and elements $m\_1,ldots,m\_n$ of $M$, we write $m\_1,ldots,m\_n\; models\; phi(x\_1,ldots,x\_n)$ if $m\_1,ldots,m\_n$ satisfy $phi(x\_1,ldots,x\_n)$. Then we call $\{m\_1,ldots,m\_n\; in\; M^n:m\_1,ldots,m\_n\; models\; phi(x\_1,ldots,x\_n)\}$ the set defined by $phi$ in $M$.
Thus for each formula in $L$, and each $L$-structure $M$ we have the set defined by the formula. For any given $M$, the collection of definable sets is the important semantical notion corresponding to the collection of formulae.

The areas of model theory

An incomplete and somewhat arbitrary subdivision of model theory is into classical model theory, model theory applied to groups and fields, and geometric model theory. A missing subdivision is computable model theory, but this can arguably be viewed as an independent subfield of logic. Examples of early theorems from classical model theory include Gödel's completeness theorem , the upward and downward Löwenheim–Skolem theorems, Vaught's two cardinal theorem, Scott's isomorphism theorem, the omitting types theorem, and the Ryll-Nardjewski theorem. Examples of early results from model theory applied to fields are Tarski's elimination of quantifiers for real closed fields, Ax's theorem on pseudo-finite fields, and Robinson's development of nonstandard analysis. An important step in the evolution of classical model theory occurred with the birth of stability theory (through Morley's theorem on totally transcendental theories and Shelah's classification program), which developed a calculus of independence and rank based on syntactical conditions satisfied by theories. During the last several decades applied model theory has repeatedly merged with the more pure stability theory. The result of this synthesis is called geometric model theory in this article (which is taken to include o-minimality, for example, as well as classical geometric stability theory). An example of a theorem from geometric model theory is Hrushovski's proof of the Mordell-Lang conjecture for function fields. The ambition of geometric model theory is to provide a ''geography of mathematics'' by embarking on a detailed study of definable sets in various mathematical structures, aided by the substantial tools developed in the study of pure model theory.

Methods of early applied model theory

Elimination of quantifiers and model completeness

A theory ''T'' is said to admit elimination of quantifiers if every formula is provably equivalent to a quantifier-free formula under ''T''. The theory ''T'' is model complete if every formula is provably equivalent to an existential formula.
These definitions concerning the syntactics of ''T'' can be shown to be equivalent to the following statement concerning the models of ''T'' (i.e. the semantics of ''T''):
:: ''T'' has quantifier elimination iff for any two models ''B'' and ''C'' of ''T'' and for any common substructure ''A'' of ''B'' and ''C'', ''B'' and ''C'' are elementarily equivalent in the language of ''T'' augmented with constants from ''A''. In fact, it is sufficient to show that any sentence with only existential quantifiers have the same truth value for ''B'' and ''C''.
:: ''T'' is model complete iff for every ''A'' and ''B'' models of ''T'', and ''L''-embedding of ''A'' into ''B'', we have that the embedding is elementary.
One can see from the definition that quantifier elimination is stronger than model completeness. This is because formulas in model complete theories are equivalent containing only existential quantifiers. Any formula in a theory that admits quantifier elimination is equivalent to a quantifier-free formula which can be viewed as a special kind of existential formula.
In early model theory, quantifier elimination was used to demonstrate that various theories possess certain model-theoretic properties like decidability and completeness. A common technique was to show first that a theory admits elimination of quantifiers and thereafter prove decidability or completeness by considering only the quantifier-free formulas. This technique is used to show that Presburger arithmetic, i.e. the theory of the additive natural numbers, is decidable. The demonstration of the decidability of Presburger arithmetic already hints at the limitations of this technique. Theories could be decidable yet not admit quantifier elimination. Strictly speaking, the theory of the additive natural numbers did not admit quantifier elimination, but it was an expansion of the additive natural numbers that was shown to be decidable.
Example: Nullstellensatz in 'ACF' and 'DCF'

Interpretability

Given a mathematical structure, there are very often associated structures which can be constructed as a quotient of part of the original structure via an equivalence relation. An important example is a quotient group of a group.
One might say that to understand the full structure one must understand these quotients. When the equivalence relation is definable, we can give the previous sentence a precise meaning. We say that these structures are interpretable.
A key fact is that one can translate sentences from the language of the interpreted structures to the language of the original structure. Thus one can show that if a structure ''M'' interprets another whose theory is undecidable, then ''M'' itself is undecidable.

Ultraproduct constructions

An ultraproduct is a quotient of the direct product of a family of structures of the same type. To use the ultraproduct construction, one chooses a suitable ultrafilter $mathcal\; U$ on the index set $I$ of a family $\{mathbb\; A\_i\; |\; i\; in\; I\}$ of structures, all with the same language. Then one forms the product $Pi\_\{iin\; I\}mathbb\; A\_i$ of the given family, and factors out the equivalence relation $sim\_\{mathcal\; U\}$ that is defined on $mathbb\; A$ by the rule
:
The resulting structure is denoted by $Pi\_\{iin\; I\}mathbb\; A\_i/mathcal\; U$. A subset $X$ of the family $\{mathbb\; A\_i\; |\; i\; in\; I\}$ of structures is said to be ''almost all'' of them if $X$ is an element of the ultrafilter $mathcal\; U$. Thus, in the definition of the equivalence relation above, two (usually infinitely long, in most applications) vectors, and are identified iff their projections onto almost all of the axes $mathbb\; A\_i$ are identical.
The choice of which ultrafilter to use is dependent upon the application, and for many applications of model theory, the first and foremost criterion for choosing an ultrafilter is somehow related to cardinality. (For example, a frequently used type of ultrafilter is a uniform ultrafilter. An ultrafilter $mathcal\; U$ on a set $I$ is ''uniform'' provided that every element of $mathcal\; U$ is a set of the same cardinality as the set $I$.) However, there are some `trivial' cases that are essentially always avoided: non-proper ultrafilters (which many authors do not even call ultrafilters at all), and principal ultrafilters. (Here again, cardinality comes into play, because every (ultra)filter on a finite set is necessarily principal.)
A most important tool in the application of ultraproducts is a theorem of Łoš, which states that for any sentence $sigma$ in the language appropriate for the given structures, $Pi\_\{iin\; I\}mathbb\; A\_i/mathcal\; U$ satisfies $sigma$ if and only if $sigma$ holds in almost all of the given structures.
Some striking applications of ultraproducts include very elegant proofs of the compactness theorem and the completeness theorem, Keisler's ultrapower theorem, which gives an algebraic characterization of the semantic notion of elementary equivalence, and the Robinson-Zakon presentation of the use of superstructures and their monomorphisms to construct nonstandard models of analysis, leading to the growth of the area of nonstandard analysis, which was pioneered (as an application of the compactness theorem) by Abraham Robinson.

Methods of classical model theory

Using the compactness and completeness theorems

Gödel's completeness theorem (not to be confused with his incompleteness theorems) says that a theory has a model if and only if it is consistent, i.e. no contradiction is proved by the theory. This is the heart of model theory as it lets us answer questions about theories by looking at models and vice-versa. One should not confuse the completeness theorem with the notion of a complete theory. A complete theory is a theory that contains every sentence or its negation. Importantly, one can find a complete consistent theory extending any consistent theory. However, as shown by Gödel's incompleteness theorems only in relatively simple cases will it be possible to have a complete consistent theory that is also recursive, i.e. that can be described by a recursively enumerable set of axioms. In particular, the theory of natural numbers has no recursive complete and consistent theory. Non-recursive theories are of little practical use, since it is undecidable if a proposed axiom is indeed an axiom, making proof-checking practically impossible.
The compactness theorem states that a set of sentences S is satisfiable if every finite subset of S is satisfiable. In the context of proof theory the analogous statement is trivial, since every proof can have only a finite number of antecedents used in the proof. In the context of model theory, however, this proof is somewhat more difficult. There are two well known proofs, one by Gödel (which goes via proofs) and one by Malcev (which is more direct and allows us to restrict the cardinality of the resulting model).
Model theory is usually concerned with first-order logic, and many important results (such as the completeness and compactness theorems) fail in second-order logic or other alternatives. In first-order logic all infinite cardinals look the same to a language which is countable. This is expressed in the Löwenheim-Skolem theorems, which state that any countable theory with an infinite model $mathfrak\{A\}$ has models of all infinite cardinalities (at least that of the language) which agree with $mathfrak\{A\}$ on all sentences, i.e. they are 'elementarily equivalent'.

Types

Fix an $L$-structure $M$, and a natural number $n$. The set of definable subsets of $M^n$ over some parameters $A$ is a Boolean algebra. By Stone's representation theorem for Boolean algebras there is a natural dual notion to this. One can consider this to be the topological space consisting of maximal consistent sets of formulae over $A$. We call this the space of (complete) $n$-types over $A$, and write $S\_n(A)$.
Now consider an element $m\; in\; M^n$. Then the set of all formulae $phi$ with parameters in $A$ in free variables $x\_1,ldots,x\_n$ so that $M\; models\; phi(m)$ is consistent and maximal such. It is called the ''type'' of $m$ over $A$.
One can show that for any $n$-type $p$, there exists some elementary extension $N$of $M$ and some $a\; in\; N^n$ so that $p$ is the type of $a$ over $A$.
Many important properties in model theory can be expressed with types. Further many proofs go via constructing models with elements that contain elements with certain types and then using these elements.
'Illustrative Example:' Suppose $M$ is an algebraically closed field. The theory has quantifier elimination . This allows us to show that a type is determined exactly by the polynomial equations it contains. Thus the space of $n$-types over a subfield $A$ is bijective with the set of prime ideals of the polynomial ring $A[x\_1,ldots,x\_n]$. This is the same set as the spectrum of $A[x\_1,ldots,x\_n]$. Note however that the topology considered on the type space is the constructible topology: a set of types is basic open iff it is of the form $\{p:\; f(x)=0\; in\; p\}$ or of the form $\{p:\; f(x)$
eq 0 in p}. This is finer than the Zariski topology.

Elementary embeddings

Ehrenfeucht-Fraïssé games and Scott sentences

Saturated and prime models, omitting types

Categoricity

If $T$ is a first order theory in the language $L$ and $kappa$ is a cardinal, then $T$ is said to be $kappa$-categorical iff any two models of $T$ which are of cardinality $kappa$ are isomorphic. Categorical theories are from many points of view the most well behaved theories. The study of categoricity led on to the wider programme of stability. For more detail see Morley's categoricity theorem.

Model completion, model companions

Given a first order ''L''-theories ''T and ''T', ''T' is a model companion
for ''T'' if
i) ''T' is model complete
ii) Every model of ''T'' has an extension that is a model of ''T'
iii) Every model of ''T' has an extension that is a model of ''T''
If $T\text{'}$ is a model companion for $T$ and $T\text{'}\; cup\; Diag(mathcal\{M\})$ is complete
for any $mathcal\{M\}\; models\; T$ then $T\text{'}$ is a model completion for $T$
from Marker page 106

Shelah's classification program

Methods of geometric model theory

Model theory and set theory

Set theory (which is expressed in a countable language) has a countable model; this is known as Skolem's paradox, since there are sentences in set theory which postulate the existence of uncountable sets and yet these sentences are true in our countable model. Particularly the proof of the independence of the continuum hypothesis requires considering sets in models which appear to be uncountable when viewed from ''within'' the model, but are countable to someone ''outside'' the model.
The model-theoretic viewpoint has been useful in set theory; for example in Kurt Gödel's work on the constructible universe, which, along with the method of forcing developed by Paul Cohen can be shown to prove the (again philosophically interesting) independence of the axiom of choice and the continuum hypothesis from the other axioms of set theory.

Computable model theory

Harrington's result about decidable prime models, application to 'DCF'.

See also

★ Axiomatizable class ★ Compactness theorem ★ Descriptive complexity ★ Elementary embedding ★ Finite model theory

★ First-order theories ★ Forcing (mathematics) ★ Hyperreal number ★ Institutional model theory ★ Kripke semantics

★ Löwenheim–Skolem theorem ★ Proof theory ★ Saturated model

References

★ John L. Bell & Alan B. Slomson (1969), ''Models and Ultraproducts: An Introduction'', North-Holland (re-printed in 2006 by Dover publications), ISBN 0-486-44979-3.

★ Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. ''A Course in Universal Algebra.'' Springer-Verlag, ISBN 3-540-90578-2.

★ C. C. Chang, H. J. Keisler, ''Model theory'' (1977), ISBN 0-7204-0692-7.

★ Wilfrid Hodges, ''A shorter model theory'' (1997), Cambridge University Press. ISBN 0-521-58713-1.

★ Wilfrid Hodges, ''Model theory'' (1993), Cambridge University Press.

★ Wilfrid Hodges, ''First-order Model theory''. The Stanford Encyclopedia Of Philosophy, E. Zalta (ed.).

★ David Marker, ''Model Theory: An Introduction'' (2002), Springer-Verlag, ISBN 0-387-98760-6.