Model theory

This article is about the mathematical discipline. For the informal notion in other parts of mathematics and science, see Mathematical model.
In mathematics, model theory is the study of (classes of) mathematical structures (e.g. groups, fields, graphs, universes of set theory) using tools from mathematical logic.
Objects of study in model theory are models for formal languages which are structures that give meaning to the sentences of these formal languages. If a model for a language moreover satisfies a particular sentence or theory (set of sentences satisfying special conditions), it is called a model of the sentence or theory.
Model theory has close ties to algebra and universal algebra.
This article focuses on finitary first order model theory of infinite structures. Finite model theory, which concentrates on finite structures, diverges significantly from the study of infinite structures in both the problems studied and the techniques used. Model theory in higherorder 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
Introduction
Model theory recognises and is intimately concerned with a duality: It examines semantical elements by means of syntactical elements of a corresponding language. To quote the first page of Chang and Keisler (1990):
 universal algebra + structure (mathematical logic) = model theory.
Model theory developed rapidly during the 1990s, and a more modern definition is provided by Wilfrid Hodges (1997):
 model theory = algebraic geometry − fields.
In a similar way to proof theory, model theory is situated in an area of interdisciplinarity between mathematics, philosophy, and computer science. The most important professional organization in the field of model theory is the Association for Symbolic Logic.
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 twocardinal theorem, Scott's isomorphism theorem, the omitting types theorem, and the RyllNardzewski 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 pseudofinite 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 uncountably categorical 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 ominimality, 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.
Example
To illustrate the basic relationship involving syntax and semantics in the context of a nontrivial model, one can start, on the syntactic side, with suitable axioms for the natural numbers such as Peano axioms, and the associated theory. Going on to the semantic side, one has the usual counting numbers as a model. In the 1930s, Skolem developed alternative models satisfying the axioms. This illustrates what is meant by interpreting a language or theory in a particular model. A more traditional example is interpreting the axioms of a particular algebraic system such as a group, in the context of a model provided by a specific group.
Universal algebra
Main article: Universal algebraFundamental concepts in universal algebra are signatures σ and σalgebras. Since these concepts are formally defined in the article on structures, the present article can content itself with an informal introduction which consists in examples of how these terms are used.
 The standard signature of rings is σ_{ring} = {×,+,−,0,1}, where × and + are binary, − is unary, and 0 and 1 are nullary.
 The standard signature of semirings is σ_{smr} = {×,+,0,1}, where the arities are as above.
 The standard signature of (multiplicative) groups is σ_{grp} = {×,^{−1},1}, where × is binary, ^{−1} is unary and 1 is nullary.
 The standard signature of monoids is σ_{mnd} = {×,1}.
 A ring is a σ_{ring}structure which satisfies the identities u + (v + w) = (u + v) + w, u + v = v + u, u + 0 = u, u + (−u) = 0, u × (v × w) = (u × v) × w, u × 1 = u, 1 × u = u, u × (v + w) = (u × v) + (u × w) and (v + w) × u = (v × u) + (w × u).
 A group is a σ_{grp}structure which satisfies the identities u × (v × w) = (u × v) × w, u × 1 = u, 1 × u = u, u × u^{−1} = 1 and u^{−1} × u = 1.
 A monoid is a σ_{mnd}structure which satisfies the identities u × (v × w) = (u × v) × w, u × 1 = u and 1 × u = u.
 A semigroup is a {×}structure which satisfies the identity u × (v × w) = (u × v) × w.
 A magma is just a {×}structure.
This is a very efficient way to define most classes of algebraic structures, because there is also the concept of σhomomorphism, which correctly specializes to the usual notions of homomorphism for groups, semigroups, magmas and rings. For this to work, the signature must be chosen well.
Terms such as the σ_{ring}term t(u,v,w) given by (u + (v × w)) + (−1) are used to define identities t = t', but also to construct free algebras. An equational class is a class of structures which, like the examples above and many others, is defined as the class of all σstructures which satisfy a certain set of identities. Birkhoff's theorem states:
 A class of σstructures is an equational class if and only if it is not empty and closed under subalgebras, homomorphic images, and direct products.
An important nontrivial tool in universal algebra are ultraproducts , where I is an infinite set indexing a system of σstructures A_{i}, and U is an ultrafilter on I.
While model theory is generally considered a part of mathematical logic, universal algebra, which grew out of Alfred North Whitehead's (1898) work on abstract algebra, is part of algebra. This is reflected by their respective MSC classifications. Nevertheless model theory can be seen as an extension of universal algebra.
Finite model theory
Main article: Finite model theoryFinite model theory is the area of model theory which has the closest ties to universal algebra. Like some parts of universal algebra, and in contrast with the other areas of model theory, it is mainly concerned with finite algebras, or more generally, with finite σstructures for signatures σ which may contain relation symbols as in the following example:
 The standard signature for graphs is σ_{grph}={E}, where E is a binary relation symbol.
 A graph is a σ_{grph}structure satisfying the sentences and .
A σhomomorphism is a map that commutes with the operations and preserves the relations in σ. This definition gives rise to the usual notion of graph homomorphism, which has the interesting property that a bijective homomorphism need not be invertible. Structures are also a part of universal algebra; after all, some algebraic structures such as ordered groups have a binary relation <. What distinguishes finite model theory from universal algebra is its use of more general logical sentences (as in the example above) in place of identities. (In a modeltheoretic context an identity t=t' is written as a sentence .)
The logics employed in finite model theory are often substantially more expressive than firstorder logic, the standard logic for model theory of infinite structures.
Firstorder logic
Main article: Firstorder logicWhereas universal algebra provides the semantics for a signature, logic provides the syntax. With terms, identities and quasiidentities, even universal algebra has some limited syntactic tools; firstorder logic is the result of making quantification explicit and adding negation into the picture.
A firstorder formula is built out of atomic formulas such as R(f(x,y),z) or y = x + 1 by means of the Boolean connectives and prefixing of quantifiers or . A sentence is a formula in which each occurrence of a variable is in the scope of a corresponding quantifier. Examples for formulas are φ (or φ(x) to mark the fact that at most x is an unbound variable in φ) and ψ defined as follows:
(Note that the equality symbol has a double meaning here.) It is intuitively clear how to translate such formulas into mathematical meaning. In the σ_{smr}structure of the natural numbers, for example, an element n satisfies the formula φ if and only if n is a prime number. The formula ψ similarly defines irreducibility. Tarski gave a rigorous definition, sometimes called "Tarski's definition of truth", for the satisfaction relation , so that one easily proves:
 is a prime number.
 is irreducible.
A set T of sentences is called a (firstorder) theory. A theory is satisfiable if it has a model , i.e. a structure (of the appropriate signature) which satisfies all the sentences in the set T. Consistency of a theory is usually defined in a syntactical way, but in firstorder logic by the completeness theorem there is no need to distinguish between satisfiability and consistency. Therefore model theorists often use "consistent" as a synonym for "satisfiable".
A theory is called categorical if it determines a structure up to isomorphism, but it turns out that this definition is not useful, due to serious restrictions in the expressivity of firstorder logic. The Löwenheim–Skolem theorem implies that for every theory T^{[1]} which has an infinite model and for every infinite cardinal number κ, there is a model such that the number of elements of is exactly κ. Therefore only finite structures can be described by a categorical theory.
Lack of expressivity (when compared to higher logics such as secondorder logic) has its advantages, though. For model theorists the Löwenheim–Skolem theorem is an important practical tool rather than the source of Skolem's paradox. Firstorder logic is in some sense (for which see Lindström's theorem) the most expressive logic for which both the Löwenheim–Skolem theorem and the compactness theorem hold:
 Compactness theorem
 Every unsatisfiable firstorder theory has a finite unsatisfiable subset.
This important theorem, due to Gödel, is of central importance in infinite model theory, where the words "by compactness" are commonplace. One way to prove it is by means of ultraproducts. An alternative proof uses the completeness theorem, which is otherwise reduced to a marginal role in most of modern model theory.
Axiomatizability, elimination of quantifiers, and modelcompleteness
The first step, often trivial, for applying the methods of model theory to a class of mathematical objects such as groups, or trees in the sense of graph theory, is to choose a signature σ and represent the objects as σstructures. The next step is to show that the class is an elementary class, i.e. axiomatizable in firstorder logic (i.e. there is a theory T such that a σstructure is in the class if and only if it satisfies T). E.g. this step fails for the trees, since connectedness cannot be expressed in firstorder logic. Axiomatizability ensures that model theory can speak about the right objects. Quantifier elimination can be seen as a condition which ensures that model theory does not say too much about the objects.
A theory T has quantifier elimination if every firstorder formula φ(x_{1},...,x_{n}) over its signature is equivalent modulo T to a firstorder formula ψ(x_{1},...,x_{n}) without quantifiers, i.e. holds in all models of T. For example the theory of algebraically closed fields in the signature σ_{ring}=(×,+,−,0,1) has quantifier elimination because every formula is equivalent to a Boolean combination of equations between polynomials.
A substructure of a σstructure is a subset of its domain, closed under all functions in its signature σ, which is regarded as a σstructure by restricting all functions and relations in σ to the subset. An embedding of a σstructure into another σstructure is a map f: A → B between the domains which can be written as an isomorphism of with a substructure of . Every embedding is an injective homomorphism, but the converse holds only if the signature contains no relation symbols.
If a theory does not have quantifier elimination, one can add additional symbols to its signature so that it does. Early model theory spent much effort on proving axiomatizability and quantifier elimination results for specific theories, especially in algebra. But often instead of quantifier elimination a weaker property suffices:
A theory T is called modelcomplete if every substructure of a model of T which is itself a model of T is an elementary substructure. There is a useful criterion for testing whether a substructure is an elementary substructure, called the Tarski–Vaught test. It follows from this criterion that a theory T is modelcomplete if and only if every firstorder formula φ(x_{1},...,x_{n}) over its signature is equivalent modulo T to an existential firstorder formula, i.e. a formula of the following form:
 ,
where ψ is quantifier free. A theory that is not modelcomplete may or may not have a model completion, which is a related modelcomplete theory that is not, in general, an extension of the original theory. A more general notion is that of model companions.
Categoricity
As observed in the section on firstorder logic, firstorder theories cannot be categorical, i.e. they cannot describe a unique model up to isomorphism, unless that model is finite. But two famous modeltheoretic theorems deal with the weaker notion of κcategoricity for a cardinal κ. A theory T is called κcategorical if any two models of T that are of cardinality κ are isomorphic. It turns out that the question of κcategoricity depends critically on whether κ is bigger than the cardinality of the language (i.e. + σ, where σ is the cardinality of the signature). For finite or countable signatures this means that there is a fundamental difference between cardinality and κcardinality for uncountable κ.
A few characterizations of categoricity include:
 For a complete firstorder theory T in a finite or countable signature the following conditions are equivalent:
 T is categorical.
 For every natural number n, the Stone space S_{n}(T) is finite.
 For every natural number n, the number of formulas φ(x_{1}, ..., x_{n}) in n free variables, up to equivalence modulo T, is finite.
This result, due independently to Engeler, RyllNardzewski and Svenonius, is sometimes referred to as the RyllNardzewski theorem.
Further, categorical theories and their countable models have strong ties with oligomorphic groups. They are often constructed as Fraïssé limits.
Michael Morley's highly nontrivial result that (for countable languages) there is only one notion of uncountable categoricity was the starting point for modern model theory, and in particular classification theory and stability theory:
 Morley's categoricity theorem
 If a firstorder theory T in a finite or countable signature is κcategorical for some uncountable cardinal κ, then T is κcategorical for all uncountable cardinals κ.
Uncountably categorical (i.e. κcategorical for all uncountable cardinals κ) theories are from many points of view the most wellbehaved theories. A theory that is both categorical and uncountably categorical is called totally categorical.
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 modeltheoretic 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.
Other basic notions of model theory
Reducts and expansions
Main article: ReductA field or a vector space can be regarded as a (commutative) group by simply ignoring some of its structure. The corresponding notion in model theory is that of a reduct of a structure to a subset of the original signature. The opposite relation is called an expansion  e.g. the (additive) group of the rational numbers, regarded as a structure in the signature {+,0} can be expanded to a field with the signature {×,+,1,0} or to an ordered group with the signature {+,0,<}.
Similarly, if σ' is a signature that extends another signature σ, then a complete σ'theory can be restricted to σ by intersecting the set of its sentences with the set of σformulas. Conversely, a complete σtheory can be regarded as a σ'theory, and one can extend it (in more than one way) to a complete σ'theory. The terms reduct and expansion are sometimes applied to this relation as well.
Interpretability
Main article: Interpretation (model theory)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.
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 viceversa. 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. Nonrecursive theories are of little practical use, since it is undecidable if a proposed axiom is indeed an axiom, making proofchecking a supertask.
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 firstorder logic, and many important results (such as the completeness and compactness theorems) fail in secondorder logic or other alternatives. In firstorder 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 has models of all infinite cardinalities (at least that of the language) which agree with on all sentences, i.e. they are 'elementarily equivalent'.
Types
Main article: Type (model theory)Fix an Lstructure 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) ntypes over A, and write S_{n}(A).
Now consider an element . Then the set of all formulae ϕ with parameters in A in free variables so that is consistent and maximal such. It is called the type of m over A.
One can show that for any ntype p, there exists some elementary extension N of M and some 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 ntypes over a subfield A is bijective with the set of prime ideals of the polynomial ring . This is the same set as the spectrum of . 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 or of the form . This is finer than the Zariski topology.
Early history
Model theory as a subject has existed since approximately the middle of the 20th century. However some earlier research, especially in mathematical logic, is often regarded as being of a modeltheoretical nature in retrospect. The first significant result in what is now model theory was a special case of the downward Löwenheim–Skolem theorem, published by Leopold Löwenheim in 1915. The compactness theorem was implicit in work by Thoralf Skolem,^{[2]} but it was first published in 1930, as a lemma in Kurt Gödel's proof of his completeness theorem. The Löwenheim–Skolems theorem and the compactness theorem received their respective general forms in 1936 and 1941 from Anatoly Maltsev.
See also
 Axiomatizable class
 Compactness theorem
 Descriptive complexity
 Elementary equivalence
Notes
References
Canonical textbooks
 Chang, Chen Chung; Keisler, H. Jerome (1990) [1973]. Model Theory. Studies in Logic and the Foundations of Mathematics (3rd ed.). Elsevier. ISBN 9780444880543
 Hodges, Wilfrid (1997). A shorter model theory. Cambridge: Cambridge University Press. ISBN 9780521587136
 Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics 217. Springer. ISBN 0387987606.
Other textbooks
 Bell, John L.; Slomson, Alan B. (2006) [1969]. Models and Ultraproducts: An Introduction (reprint of 1974 ed.). Dover Publications. ISBN 0486449793.
 Ebbinghaus, HeinzDieter; Flum, Jörg; Thomas, Wolfgang (1994). Mathematical Logic. Springer. ISBN 0387942580.
 Hinman, Peter G. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1568812620.
 Manzano, Maria (1989). Teoria de modelos. Alianza editorial. ISBN 8420681261.
 Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 0521304423.
 Manzano, Maria (1999). Model theory. Oxford University Press. ISBN 0198538510.
 Poizat, Bruno (2000). A Course in Model Theory. Springer. ISBN 0387986553.
 Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (3rd ed.). New York: Springer Science+Business Media. doi:10.1007/9781441912213. ISBN 9781441912206. http://www.springerlink.com/content/9781441912206/.
 Rothmaler, Philipp (2000). Introduction to Model Theory (new ed.). Taylor & Francis. ISBN 9056993135.
Free online texts
 Chatzidakis, Zoe (2001). Introduction to Model Theory. pp. 26 pages in DVI format. http://www.logique.jussieu.fr/~zoe/papiers/MTluminy.dvi.
 Pillay, Anand (2002). Lecture Notes – Model Theory. pp. 61 pages. http://www.math.uiuc.edu/People/pillay/lecturenotes_modeltheory.pdf.
 Hodges, Wilfrid, Firstorder Model theory. The Stanford Encyclopedia Of Philosophy, E. Zalta (ed.).
 Simmons, Harold (2004), An introduction to Good old fashioned model theory. Notes of an introductory course for postgraduates (with exercises).
 J. Barwise and S. Feferman (editors), ModelTheoretic Logics, Perspectives in Mathematical Logic, Volume 8, New York: SpringerVerlag, 1985.
Areas of mathematics Areas Arithmetic · Algebra (elementary – linear – multilinear – abstract) · Geometry (Discrete geometry – Algebraic geometry – Differential geometry) · Calculus/Analysis · Set theory · Logic · Category theory · Number theory · Combinatorics · Graph theory · Topology · Lie theory · Differential equations/Dynamical systems · Mathematical physics · Numerical analysis · Computation · Information theory · Probability · Statistics · Optimization · Control theory · Game theory
Divisions Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
model theory — The use of a model to test for the consistency of an axiomatized system is older than modern logic. Descartes s algebraic interpretation of Euclidean geometry provides a way of showing that if the theory of real numbers is consistent, so is the… … Philosophy dictionary
Finite model theory — is a subfield of model theory that focuses on properties of logical languages, such as first order logic, over finite structures, such as finite groups, graphs, databases, and most abstract machines. It focuses in particular on connections… … Wikipedia
Type (model theory) — In model theory and related areas of mathematics, a type is a set of first order formulas in a language L with free variables x1, x2,…, xn which are true of a sequence of elements of an L structure . Loosely speaking, types describe possible… … Wikipedia
Institutional model theory — generalizes a large portion of first order model theory to an arbitrary logical system. The notion of logical system here is formalized as an institution. Institutions constitute a model oriented meta theory on logical systems similar to how the… … Wikipedia
Inner model theory — In set theory, inner model theory is the study of certain models of ZFC or some fragment or strengthening thereof. Ordinarily these models are transitive subsets or subclasses of the von Neumann universe V , or sometimes of a generic extension of … Wikipedia
Actor model theory — In theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an… … Wikipedia
NIP (model theory) — In model theory, a branch of mathematical logic, a complete theory T is said to satisfy NIP (or not the independence property ) if none of its formulae satisfy the independence property, that is if none of its formulae can pick out any given… … Wikipedia
Computable model theory — is a branch of model theory which deals with questions of computability as they apply to model theoretical structures. It was developed almost simultaneously by mathematicians in the West, primarily located in the United States and Australia, and … Wikipedia
Conceptual Model Theory — The Conceptual Model Theory of Human Understanding is a historically distinct theory of knowledge that is the first foundational epistemological theory to be validated by commercial artificial intelligence use (see… … Wikipedia
Interpretation (model theory) — In model theory, interpretation of a structure M in another structure N (typically of a different signature) is a technical notion that approximates the idea of representing M inside N . For example every reduct or definitional expansion of a… … Wikipedia