model theory

In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the statements of the theory hold). The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in a model of a theory, and the relationship of such definable sets to each other.
As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954.
Since the 1970s, the subject has been shaped decisively by Saharon Shelah's stability theory.

Compared to other areas of mathematical logic such as proof theory, model theory is often less concerned with formal rigour and closer in spirit to classical mathematics.
This has prompted the comment that ''"if proof theory is about the sacred, then model theory is about the profane"''.
The applications of model theory to algebraic and diophantine geometry reflect this proximity to classical mathematics, as they often involve an integration of algebraic and model-theoretic results and techniques.

The most prominent scholarly organization in the field of model theory is the Association for Symbolic Logic.

Overview

This page focuses on finitary first order model theory of infinite structures.

The relative emphasis placed on the class of models of a theory as opposed to the class of definable sets within a model fluctuated in the history of the subject, and the two directions are summarised by the pithy characterisations from 1973 and 1997 respectively:

:model theory = universal algebra + logic

where universal algebra stands for mathematical structures and logic for logical theories; and

:model theory = algebraic geometry − fields.

where logical formulas are to definable sets what equations are to varieties over a field.

Nonetheless, the interplay of classes of models and the sets definable in them has been crucial to the development of model theory throughout its history. For instance, while stability was originally introduced to classify theories by their numbers of models in a given cardinality, stability theory proved crucial to understanding the geometry of definable sets.

Fundamental notions of first-order model theory

First-order logic

A first-order ''formula'' is built out of atomic formulas such as ''R''(''f''(''x'',''y''),''z'') or ''y'' = ''x'' + 1 by means of the Boolean connectives $\neg,\land,\lor,\rightarrow$ and prefixing of quantifiers $\forall v$ or $\exists v$. 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:

:$\begin \varphi & = & \forall u\forall v(\exists w (x\times w=u\times v)\rightarrow(\exists w(x\times w=u)\lor\exists w(x\times w=v)))\land x\ne 0\land x\ne1, :\\\psi & = & \forall u\forall v((u\times v=x)\rightarrow (u=x)\lor(v=x))\land x\ne 0\land x\ne1. \end$

(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 $\mathcal N$ 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 $\models$, so that one easily proves:

:$\mathcal N\models\varphi(n) \iff n$ is a prime number.
:$\mathcal N\models\psi(n) \iff n$ is irreducible.

A set $T$ of sentences is called a (first-order) theory, which takes the sentences in the set as its axioms. A theory is ''satisfiable'' if it has a ''model'' $\mathcal M\models T$, i.e. a structure (of the appropriate signature) which satisfies all the sentences in the set $T$. A complete theory is a theory that contains every sentence or its negation.
The complete theory of all sentences satisfied by a structure is also called the ''theory of that structure''.

It's a consequence of Gödel's completeness theorem (not to be confused with his incompleteness theorems) that a theory has a model if and only if it is consistent, i.e. no contradiction is proved by the theory.
Therefore, model theorists often use "consistent" as a synonym for "satisfiable".

Basic model-theoretic concepts

A signature or language is a set of non-logical symbols such that each symbol is either a constant symbol, or a function or relation symbol with a specified arity. Note that in some literature, constant symbols are considered as function symbols with zero arity, and hence are omitted. A structure is a set $M$ together with interpretations of each of the symbols of the signature as relations and functions on $M$ (not to be confused with the formal notion of an "interpretation" of one structure in another).

Example: A common signature for ordered rings is $\sigma_=\$, where $0$ and $1$ are 0-ary function symbols (also known as constant symbols), $+$ and $\times$ are binary (= 2-ary) function symbols, $-$ is a unary (= 1-ary) function symbol, and $<$ is a binary relation symbol. Then, when these symbols are interpreted to correspond with their usual meaning on $\Q$ (so that e.g. $+$ is a function from $\Q^2$ to $\Q$ and $<$ is a subset of $\Q^2$), one obtains a structure $(\Q,\sigma_)$.

A structure $\mathcal$ is said to model a set of first-order sentences $T$ in the given language if each sentence in $T$ is true in $\mathcal$ with respect to the interpretation of the signature previously specified for $\mathcal$. (Again, not to be confused with the formal notion of an "interpretation" of one structure in another)

A substructure $\mathcal A$ of a σ-structure $\mathcal B$ 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.
This generalises the analogous concepts from algebra; For instance, a subgroup is a substructure in the signature with multiplication and inverse.

A substructure is said to be ''elementary'' if for any first-order formula φ and any elements ''a''₁, ..., ''a''_''n'' of $\mathcal A$,
:$\mathcal A\models \varphi(a_1, ...,a_n)$ if and only if $\mathcal B\models \varphi(a_1, ...,a_n)$.
In particular, if ''φ'' is a sentence and $\mathcal A$ an elementary substructure of $\mathcal B$, then $\mathcal A\models \varphi$ if and only if $\mathcal B\models \varphi$. Thus, an elementary substructure is a model of a theory exactly when the superstructure is a model.

Example: While the field of algebraic numbers $\overline$ is an elementary substructure of the field of complex numbers $\mathbb$, the rational field $\mathbb$ is not, as we can express "There is a square root of 2" as a first-order sentence satisfied by $\mathbb$ but not by $\mathbb$.

An embedding of a σ-structure $\mathcal A$ into another σ-structure $\mathcal B$ is a map ''f'': ''A'' → ''B'' between the domains which can be written as an isomorphism of $\mathcal A$ with a substructure of $\mathcal B$. If it can be written as an isomorphism with an elementary substructure, it is called an elementary embedding. Every embedding is an injective homomorphism, but the converse holds only if the signature contains no relation symbols, such as in groups or fields.

A 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 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 (in more than one way) to a complete σ'-theory. The terms reduct and expansion are sometimes applied to this relation as well.

Compactness and the Löwenheim-Skolem theorem

The compactness theorem states that a set of sentences S is satisfiable if every finite subset of S is satisfiable. The analogous statement with ''consistent'' instead of ''satisfiable'' is trivial, since every proof can have only a finite number of antecedents used in the proof. The completeness theorem allows us to transfer this to satisfiability. However, there are also several direct (semantic) proofs of the compactness theorem.
As a corollary (i.e., its contrapositive), the compactness theorem says that every unsatisfiable first-order theory has a finite unsatisfiable subset. This theorem is of central importance in model theory, where the words "by compactness" are commonplace.

Another cornerstone of first-order model theory is the Löwenheim-Skolem theorem.
According to the Löwenheim-Skolem Theorem, every infinite structure in a countable signature has a countable elementary substructure. Conversely, for any infinite cardinal κ every infinite structure in a countable signature that is of cardinality less than κ can be elementarily embedded in another structure of cardinality κ (There is a straightforward generalisation to uncountable signatures). In particular, the Löwenheim-Skolem Theorem implies that any theory in a countable signature with infinite models has a countable model as well as arbitrarily large models.

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.

Definability

Definable sets

In model theory, definable sets are important objects of study. For instance, in $\mathbb N$ the formula
:$\forall u\forall v(\exists w (x\times w=u\times v)\rightarrow(\exists w(x\times w=u)\lor\exists w(x\times w=v)))\land x\ne 0\land x\ne1$
defines the subset of prime numbers, while the formula
:$\exists y (2\times y = x)$
defines the subset of even numbers.
In a similar way, formulas with ''n'' free variables define subsets of $$