Model theory


In mathematics, model theory is the study of classes of mathematical structures from the perspective of mathematical logic. The objects of study are models of theories in a formal language. A set of sentences in a formal language is one of the components that form a theory. A model of a theory is a structure that satisfies the sentences of that theory.
Model theory recognizes and is intimately concerned with a duality: it examines semantical elements by means of syntactical elements of a corresponding language. In a summary definition, dating from 1973:
Model theory developed rapidly during the 1990s, and a more modern definition is provided by Wilfrid Hodges :
Other nearby areas of mathematics include combinatorics, number theory, arithmetic dynamics, analytic functions, and non-standard analysis.
In a similar way to proof theory, model theory is situated in an area of interdisciplinarity among mathematics, philosophy, and computer science. The most prominent professional organization in the field of model theory is the Association for Symbolic Logic.

Branches

This page 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 higher-order logics or infinitary logics is hampered by the fact that completeness and compactness do not in general hold for these logics. However, a great deal of study has also been done in such logics.
Informally, model theory can be divided 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-Nardzewski 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 non-standard analysis. An important step in the evolution of classical model theory occurred with the birth of stability theory, 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. An example of a proof 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.

Universal algebra

Fundamental concepts in [|universal algebra] are signatures σ and σ-algebras. Since these concepts are formally defined in the article on structures, the present article is an informal introduction which consists of examples of the way these terms are used.
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 given by are used to define identities 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:
An important non-trivial tool in universal algebra are ultraproducts, where I is an infinite set indexing a system of σ-structures Ai, 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 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

Finite 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:
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 in place of identities.
The logics employed in finite model theory are often substantially more expressive than [|first-order logic], the standard logic for model theory of infinite structures.

First-order logic

Whereas universal algebra provides the semantics for a signature, logic provides the syntax. With terms, identities and quasi-identities, even universal algebra has some limited syntactic tools; first-order logic is the result of making quantification explicit and adding negation into the picture.
A first-order formula is built out of atomic formulas such as R 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 φ and ψ defined as follows:
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:
A set T of sentences is called a theory. A theory is satisfiable if it has a model, i.e. a structure which satisfies all the sentences in the set T. Consistency of a theory is usually defined in a syntactical way, but in first-order 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 first-order logic. The Löwenheim–Skolem theorem implies that for every theory T having a countable signature which has an infinite model for some infinite cardinal number, then it has a model of size κ for any infinite cardinal number κ. Since two models of different sizes cannot possibly be isomorphic, only finitary structures can be described by a categorical theory.
Lack of expressivity 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. In a certain sense made precise by Lindström's theorem, first-order logic is the most expressive logic for which both the Löwenheim–Skolem theorem and the compactness theorem hold.
As a corollary, the compactness theorem says that every unsatisfiable first-order theory has a finite unsatisfiable subset. This theorem 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.

Categoricity

As observed in the section on first-order logic, first-order theories cannot be categorical, i.e. they cannot describe a unique model up to isomorphism, unless that model is finite. But two famous model-theoretic 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. 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:
This result, due independently to Engeler, Ryll-Nardzewski and Svenonius, is sometimes referred to as the Ryll-Nardzewski 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 non-trivial result that there is only one notion of uncountable categoricity was the starting point for modern model theory, and in particular classification theory and stability theory:
Uncountably categorical theories are from many points of view the most well-behaved theories. A theory that is both -categorical and uncountably categorical is called totally categorical.

Set theory

, if it is consistent, 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 independence of the axiom of choice and the continuum hypothesis from the other axioms of set theory.
In the other direction, model theory itself can be formalized within ZFC set theory. The development of the fundamentals of model theory rely on the axiom of choice, or more exactly the Boolean prime ideal theorem. Other results in model theory depend on set-theoretic axioms beyond the standard ZFC framework. For example, if the Continuum Hypothesis holds then every countable model has an ultrapower which is saturated. Similarly, if the Generalized Continuum Hypothesis holds then every model has a saturated elementary extension. Neither of these results are provable in ZFC alone. Finally, some questions arising from model theory have been shown to be equivalent to large cardinal axioms.

Other basic notions

Reducts and expansions

A field or a vector space can be regarded as a 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 group of the rational numbers, regarded as a structure in the signature can be expanded to a field with the signature or to an ordered group with the signature.
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 to a complete σ'-theory. The terms reduct and expansion are sometimes applied to this relation as well.

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.

Using the compactness and completeness 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 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 and one by Malcev.
Model theory is usually concerned with first-order logic, and many important results 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 has models of all infinite cardinalities which agree with on all sentences, i.e. they are 'elementarily equivalent'.

Types

Fix an -structure, and a natural number. The set of definable subsets of over some parameters 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. We call this the space of -types over, and write.
Now consider an element. Then the set of all formulae with parameters in in free variables so that is consistent and maximal such. It is called the type of over.
One can show that for any -type, there exists some elementary extension of and some so that is the type of over.
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 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 -types over a subfield 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.

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 model-theoretical 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, but it was first published in 1930, as a lemma in Kurt Gödel's proof of his completeness theorem. The Löwenheim–Skolem theorem and the compactness theorem received their respective general forms in 1936 and 1941 from Anatoly Maltsev.
The development of model theory can be traced to Alfred Tarski, a member of the Lwów–Warsaw school during the interbellum. Tarski's work included logical consequence, deductive systems, the algebra of logic, the theory of definability, and the semantic definition of truth, among other topics. His semantic methods culminated in the model theory he and a number of his Berkeley students developed in the 1950s and '60s. These modern concepts of model theory influenced Hilbert's program and modern mathematics.

Canonical textbooks