TheInfoList

OR:

In
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
, model theory is the study of the relationship between
formal theories Formal, formality, informal or informality imply the complying with, or not complying with, some set of requirements (forms, in Ancient Greek). They may refer to: Dress code and events * Formal wear, attire for formal events * Semi-formal atti ...
(a collection of
sentences ''The Four Books of Sentences'' (''Libri Quattuor Sententiarum'') is a book of theology written by Peter Lombard in the 12th century. It is a systematic compilation of theology, written around 1150; it derives its name from the '' sententiae'' ...
in a
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sym ...
mathematical structure In mathematics, a structure is a set endowed with some additional features on the set (e.g. an operation, relation, metric, or topology). Often, the additional features are attached or related to the set, so as to provide it with some additiona ...
), 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 Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by
Saharon Shelah Saharon Shelah ( he, שהרן שלח; born July 3, 1945) is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey. Biography Shelah was born in Jerusalem on July 3, ...
's
stability theory In mathematics, stability theory addresses the stability of solutions of differential equations and of trajectories of dynamical systems under small perturbations of initial conditions. The heat equation, for example, is a stable partial diffe ...
. Compared to other areas of mathematical logic such as
proof theory Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Barwise (1978) consists of four corresponding part ...
, 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 Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Barwise (1978) consists of four corresponding part ...
is about the sacred, then model theory is about the profane"''. The applications of model theory to
algebraic Algebraic may refer to any subject related to algebra in mathematics and related branches like algebraic number theory and algebraic topology. The word algebra itself has several meanings. Algebraic may also refer to: * Algebraic data type, a data ...
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 The Association for Symbolic Logic (ASL) is an international organization of specialists in mathematical logic and philosophical logic. The ASL was founded in 1936, and its first president was Alonzo Church. The current president of the ASL is ...
.

# Overview

first order In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of hi ...
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 Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular groups as the object of study ...
+
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from prem ...
where universal algebra stands for mathematical structures and logic for logical theories; and :model theory =
algebraic geometry Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
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 In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
, 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\left(\exists w \left(x\times w=u\times v\right)\rightarrow\left(\exists w\left(x\times w=u\right)\lor\exists w\left(x\times w=v\right)\right)\right)\land x\ne 0\land x\ne1, :\\\psi & = & \forall u\forall v\left(\left(u\times v=x\right)\rightarrow \left(u=x\right)\lor\left(v=x\right)\right)\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 In philosophy, systems theory, science, and art, emergence occurs when an entity is observed to have properties its parts do not have on their own, properties or behaviors that emerge only when the parts interact in a wider whole. Emergen ...
. 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\left(n\right) \iff n$ is a prime number. :$\mathcal N\models\psi\left(n\right) \iff n$ is irreducible. A set $T$ of sentences is called a (first-order)
theory A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may ...
, 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 A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...
or
language Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...
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 Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
. Note that in some literature, constant symbols are considered as function symbols with zero arity, and hence are omitted. A
structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such a ...
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 Interpretation may refer to: Culture * Aesthetic interpretation, an explanation of the meaning of a work of art * Allegorical interpretation, an approach that assumes a text should not be interpreted literally * Dramatic Interpretation, an event ...
" 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 $\left(\Q,\sigma_\right)$. 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 Interpretation may refer to: Culture * Aesthetic interpretation, an explanation of the meaning of a work of art * Allegorical interpretation, an approach that assumes a text should not be interpreted literally * Dramatic Interpretation, an event ...
" 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''1, ..., ''a''''n'' of $\mathcal A$, :$\mathcal A\models \varphi\left(a_1, ...,a_n\right)$ if and only if $\mathcal B\models \varphi\left(a_1, ...,a_n\right)$. 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 In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is g ...
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 In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
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 In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
, 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 In mathematical logic, Lindström's theorem (named after Swedish logician Per Lindström, who published it in 1969) states that first-order logic is the '' strongest logic'' (satisfying certain conditions, e.g. closure under classical negation) h ...
, 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\left(\exists w \left(x\times w=u\times v\right)\rightarrow\left(\exists w\left(x\times w=u\right)\lor\exists w\left(x\times w=v\right)\right)\right)\land x\ne 0\land x\ne1$ defines the subset of prime numbers, while the formula :$\exists y \left(2\times y = x\right)$ defines the subset of even numbers. In a similar way, formulas with ''n'' free variables define subsets of $\mathcal^n$. For example, in a field, the formula :$y = x \times x$ defines the curve of all $\left(x,y\right)$ such that $y = x^2$. Both of the definitions mentioned here are ''parameter-free'', that is, the defining formulas don't mention any fixed domain elements. However, one can also consider definitions ''with parameters from the model''. For instance, in $\mathbb$, the formula :$y = x \times x + \pi$ uses the parameter $\pi$ from $\mathbb$ to define a curve.

## Eliminating quantifiers

In general, definable sets without quantifiers are easy to describe, while definable sets involving possibly nested quantifiers can be much more complicated. This makes quantifier elimination a crucial tool for analysing definable sets: A theory ''T'' has quantifier elimination if every first-order formula φ(''x''1, ..., ''x''''n'') over its signature is equivalent modulo ''T'' to a first-order formula ψ(''x''1, ..., ''x''''n'') without quantifiers, i.e. $\forall x_1\dots\forall x_n\left(\phi\left(x_1,\dots,x_n\right)\leftrightarrow \psi\left(x_1,\dots,x_n\right)\right)$ holds in all models of ''T''. If the theory of a structure has quantifier elimination, every set definable in a structure is definable by a quantifier-free formula over the same parameters as the original definition. For example, the theory of algebraically closed fields in the signature σring = (×,+,−,0,1) has quantifier elimination. This means that in an algebraically closed field, every formula is equivalent to a Boolean combination of equations between polynomials. If a theory does not have quantifier elimination, one can add additional symbols to its signature so that it does. Axiomatisability and quantifier elimination results for specific theories, especially in algebra, were among the early landmark results of model theory. But often instead of quantifier elimination a weaker property suffices: A theory ''T'' is called
model-complete In model theory, a first-order theory is called model complete if every embedding of its models is an elementary embedding. Equivalently, every first-order formula is equivalent to a universal formula. This notion was introduced by Abraham Robinso ...
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 In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature ''σ'' are called elementarily equivalent if they satisfy the same first-order ''σ''-sentences. If ''N'' is a substructure of ''M'', one of ...
. It follows from this criterion that a theory ''T'' is model-complete if and only if every first-order formula φ(''x''1, ..., ''x''''n'') over its signature is equivalent modulo ''T'' to an existential first-order formula, i.e. a formula of the following form: :$\exists v_1\dots\exists v_m\psi\left(x_1,\dots,x_n,v_1,\dots,v_m\right)$, where ψ is quantifier free. A theory that is not model-complete may have a model completion, which is a related model-complete theory that is not, in general, an extension of the original theory. A more general notion is that of a
model companion In model theory, a first-order theory is called model complete if every embedding of its models is an elementary embedding. Equivalently, every first-order formula is equivalent to a universal formula. This notion was introduced by Abraham Robinso ...
.

## Minimality

In every structure, every finite subset $\$ is definable with parameters: Simply use the formula :$x = a_1 \vee \dots \vee x = a_n$. Since we can negate this formula, every cofinite subset (which includes all but finitely many elements of the domain) is also always definable. This leads to the concept of a ''minimal structure''. A structure $\mathcal$ is called minimal if every subset $A \subseteq \mathcal$ definable with parameters from $\mathcal$ is either finite or cofinite. The corresponding concept at the level of theories is called ''strong minimality'': A theory ''T'' is called strongly minimal if every model of ''T'' is minimal. A structure is called ''strongly minimal'' if the theory of that structure is strongly minimal. Equivalently, a structure is strongly minimal if every elementary extension is minimal. Since the theory of algebraically closed fields has quantifier elimination, every definable subset of an algebraically closed field is definable by a quantifier-free formula in one variable. Quantifier-free formulas in one variable express Boolean combinations of polynomial equations in one variable, and since a nontrivial polynomial equation in one variable has only a finite number of solutions, the theory of algebraically closed fields is strongly minimal. On the other hand, the field $\mathbb$ of real numbers is not minimal: Consider, for instance, the definable set :$\varphi \left(x\right) \;=\; \exists y \left(y \times y = x\right)$. This defines the subset of non-negative real numbers, which is neither finite nor cofinite. One can in fact use $\varphi$ to define arbitrary intervals on the real number line. It turns out that these suffice to represent every definable subset of $\mathbb$. This generalisation of minimality has been very useful in the model theory of ordered structures. A densely totally ordered structure $\mathcal$ in a signature including a symbol for the order relation is called o-minimal if every subset $A \subseteq \mathcal$ definable with parameters from $\mathcal$ is a finite union of points and intervals.

## Definable and interpretable structures

Particularly important are those definable sets that are also substructures, i. e. contain all constants and are closed under function application. For instance, one can study the definable subgroups of a certain group. However, there is no need to limit oneself to substructures in the same signature. Since formulas with ''n'' free variables define subsets of $\mathcal^n$, ''n''-ary relations can also be definable. Functions are definable if the function graph is a definable relation, and constants $a \in \mathcal$ are definable if there is a formula $\varphi\left(x\right)$ such that ''a'' is the only element of $\mathcal$ such that $\varphi\left(a\right)$ is true. In this way, one can study definable groups and fields in general structures, for instance, which has been important in geometric stability theory. One can even go one step further, and move beyond immediate substructures. 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 $\mathcal$ interprets another whose theory is undecidable, then $\mathcal$ itself is undecidable.

# Types

## Basic notions

For a sequence of elements $a_1, \dots, a_n$ of a structure $\mathcal$ and a subset ''A'' of $\mathcal$, one can consider the set of all first-order formulas $\varphi\left(x_1, \dots, x_n\right)$ with parameters in ''A'' that are satisfied by $a_1, \dots, a_n$. This is called the ''complete (n-)type realised by'' $a_1, \dots, a_n$ ''over A''. If there is an
automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphis ...
of $\mathcal$ that is constant on ''A'' and sends $a_1, \dots, a_n$ to $b_1, \dots, b_n$ respectively, then $a_1, \dots, a_n$ and $b_1, \dots, b_n$ realise the same complete type over ''A''. The real number line $\mathbb$, viewed as a structure with only the order relation , will serve as a running example in this section. Every element $a \in \mathbb$ satisfies the same 1-type over the empty set. This is clear since any two real numbers ''a'' and ''b'' are connected by the order automorphism that shifts all numbers by ''b-a''. The complete 2-type over the empty set realised by a pair of numbers $a_1, a_2$ depends on their order: either $a_1 < a_2$, $a_1 = a_2$ or $a_2 < a_1$. Over the subset $\mathbb \subseteq \mathbb$ of integers, the 1-type of a non-integer real number ''a'' depends on its value rounded down to the nearest integer. More generally, whenever $\mathcal$ is a structure and ''A'' a subset of $\mathcal$, a (partial) ''n-type over A'' is a set of formulas ''p'' with at most ''n'' free variables that are realised in an elementary extension $\mathcal$ of $\mathcal$. If ''p'' contains every such formula or its negation, then ''p'' is ''complete''. The set of complete ''n''-types over ''A'' is often written as $S_n^\left(A\right)$. If ''A'' is the empty set, then the type space only depends on the theory $T$ of $\mathcal$. The notation $S_n\left(T\right)$ is commonly used for the set of types over the empty set consistent with $T$. If there is a single formula $\varphi$ such that the theory of $\mathcal$ implies $\varphi \rightarrow \psi$ for every formula $\psi$ in ''p'', then ''p'' is called ''isolated''. Since the real numbers $\mathbb$ are Archimedean, there is no real number larger than every integer. However, a compactness argument shows that there is an elementary extension of the real number line in which there is an element larger than any integer. Therefore, the set of formulas $\$ is a 1-type over $\mathbb \subseteq \mathbb$ that is not realised in the real number line $\mathbb$. A subset of $\mathcal^n$ that can be expressed as exactly those elements of $\mathcal^n$ realising a certain type over ''A'' is called ''type-definable'' over ''A''. For an algebraic example, suppose $M$ is an
algebraically closed field In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in . Examples As an example, the field of real numbers is not algebraically closed, because ...
. The theory has quantifier elimination . This allows us to show that a type is determined exactly by the polynomial equations it contains. Thus the set of complete $n$-types over a subfield $A$ corresponds to the set of
prime ideal In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together wi ...
s of the
polynomial ring In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...

## Structures and types

While not every type is realised in every structure, every structure realises its isolated types. If the only types over the empty set that are realised in a structure are the isolated types, then the structure is called ''atomic''. On the other hand, no structure realises every type over every parameter set; if one takes all of $\mathcal$ as the parameter set, then every 1-type over $\mathcal$ realised in $\mathcal$ is isolated by a formula of the form ''a = x'' for an $a \in \mathcal$. However, any proper elementary extension of $\mathcal$ contains an element that is ''not'' in $\mathcal$. Therefore a weaker notion has been introduced that captures the idea of a structure realising all types it could be expected to realise. A structure is called ''saturated'' if it realises every type over a parameter set $A \subset \mathcal$ that is of smaller cardinality than $\mathcal$ itself. While an automorphism that is constant on ''A'' will always preserve types over ''A'', it is generally not true that any two sequences $a_1, \dots, a_n$ and $b_1, \dots, b_n$ that satisfy the same type over ''A'' can be mapped to each other by such an automorphism. A structure $\mathcal$ in which this converse does holds for all ''A'' of smaller cardinality than $\mathcal$ is called homogeneous. The real number line is atomic in the language that contains only the order $<$, since all ''n''-types over the empty set realised by $a_1, \dots, a_n$ in $\mathbb$ are isolated by the order relations between the $a_1, \dots, a_n$. It is not saturated, however, since it does not realise any 1-type over the countable set $\mathbb$ that implies ''x'' to be larger than any integer. The rational number line $\mathbb$ is saturated, in contrast, since $\mathbb$ is itself countable and therefore only has to realise types over finite subsets to be saturated.

## Stone spaces

The set of definable subsets of $\mathcal^n$ over some parameters $A$ is a
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
. By
Stone's representation theorem for Boolean algebras In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a certain field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first hal ...
there is a natural dual
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
, which consists exactly of the complete $n$-types over $A$. The topology generated by sets of the form $\$ for single formulas $\varphi$. This is called the ''Stone space of n-types over A''. This topology explains some of the terminology used in model theory: The compactness theorem says that the Stone space is a compact topological space, and a type ''p'' is isolated if and only if ''p'' is an isolated point in the Stone topology. While types in algebraically closed fields correspond to the spectrum of the polynomial ring, the topology on the type space is the
constructible topology In commutative algebra, the constructible topology on the spectrum \operatorname(A) of a commutative ring A is a topology where each closed set is the image of \operatorname (B) in \operatorname(A) for some algebra ''B'' over ''A''. An important fe ...
: a set of types is basic
open Open or OPEN may refer to: Music * Open (band), Australian pop/rock band * The Open (band), English indie rock band * Open (Blues Image album), ''Open'' (Blues Image album), 1969 * Open (Gotthard album), ''Open'' (Gotthard album), 1999 * Open (C ...
iff it is of the form $\$ or of the form $\$. This is finer than the
Zariski topology In algebraic geometry and commutative algebra, the Zariski topology is a topology which is primarily defined by its closed sets. It is very different from topologies which are commonly used in the real or complex analysis; in particular, it is n ...
.

# Constructing models

## Realising and omitting types

Constructing models that realise certain types and do not realise others is an important task in model theory. Not realising a type is referred to as ''omitting'' it, and is generally possible by the ''(Countable) Omitting types theorem'': :Let $\mathcal$ be a theory in a countable signature and let $\Phi$ be a countable set of non-isolated types over the empty set. :Then there is a model $\mathcal$ of $\mathcal$ which omits every type in $\Phi$. This implies that if a theory in a countable signature has only countably many types over the empty set, then this theory has an atomic model. On the other hand, there is always an elementary extension in which any set of types over a fixed parameter set is realised: :Let $\mathcal$ be a structure and let $\Phi$ be a set of complete types over a given parameter set $A \subset \mathcal.$ :Then there is an elementary extension $\mathcal$ of $\mathcal$ which realises every type in $\Phi$. However, since the parameter set is fixed and there is no mention here of the cardinality of $\mathcal$, this does not imply that every theory has a saturated model. In fact, whether every theory has a saturated model is independent of the Zermelo-Fraenkel axioms of set theory, and is true if the
generalised continuum hypothesis In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that or equivalently, that In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent t ...
holds.

## Ultraproducts

Ultraproducts are used as a general technique for constructing models that realise certain types. An ''ultraproduct'' is obtained from the
direct product In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...
of a set of structures over an index set ''I'' by identifying those tuples that agree on almost all entries, where ''almost all'' is made precise by an ultrafilter ''U'' on ''I''. An ultraproduct of copies of the same structure is known as an ''ultrapower''. The key to using ultraproducts in model theory is ''Łoś's theorem'': : Let $\mathcal_i$ be a set of $\sigma$-structures indexed by an index set ''I'' and ''U'' an ultrafilter on ''I''. Then any $\sigma$-formula $\varphi\left($
a_i)_ A, or a, is the first letter and the first vowel of the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''a'' (pronounced ), plural ''aes'' ...
is true in the ultraproduct of the $\mathcal_i$ by $U$ if the set of all $i \in I$ for which $\mathcal_i \models \varphi\left(a_i\right)$ lies in ''U''. In particular, any ultraproduct of models of a theory is itself a model of that theory, and thus if two models have isomorphic ultrapowers, they are elementarily equivalent. The ''Keisler-Shelah theorem'' provides a converse: :If $\mathcal$ and $\mathcal$ are elementary equivalent, then there is a set ''I'' and an ultrafilter ''U'' on ''I'' such that the ultrapowers by ''U'' of $\mathcal$ and :$\mathcal$ are isomorphic. Therefore, ultraproducts provide a way to talk about elementary equivalence that avoids mentioning first-order theories at all. Basic theorems of model theory such as the compactness theorem have alternative proofs using ultraproducts, and they can be used to construct saturated elementary extensions if they exist.

# Categoricity

A theory was originally called ''categorical'' if it determines a structure up to isomorphism. 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 if a theory ''T'' has an infinite model for some infinite
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. ...
, then it has a model of size κ for any sufficiently large
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. ...
κ. Since two models of different sizes cannot possibly be isomorphic, only finite structures can be described by a categorical theory. However, the weaker notion of κ-categoricity for a cardinal κ has become a key concept in model theory. 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. $\aleph_0$ + , σ, , where , σ, is the cardinality of the signature). For finite or countable signatures this means that there is a fundamental difference between $\omega$-cardinality and κ-cardinality for uncountable κ.

## ω-categoricity

$\omega$-categorical theories can be characterised by properties of their type space: :For a complete first-order theory ''T'' in a finite or countable signature the following conditions are equivalent: :#''T'' is $\omega$-categorical. :#Every type in ''Sn''(''T'') is isolated. :#For every natural number ''n'', ''Sn''(''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. The theory of $\left(\mathbb,<\right)$, which is also the theory of $\left(\mathbb,<\right)$, is $\omega$-categorical, as every ''n''-type $p\left(x_1, \dots, x_n\right)$ over the empty set is isolated by the pairwise order relation between the $x_i$. This means that every countable dense linear order is order-isomorphic to the rational number line. On the other hand, the theories of $\mathbb$, $\mathbb$ and $\mathbb$ as fields are not $\omega$-categorical. This follows from the fact that in all those fields, any of the infinitely many natural numbers can be defined by a formula of the form $x = 1 + \dots + 1$. $\aleph_0$-categorical theories and their countable models also have strong ties with
oligomorphic group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...
s: :A complete first-order theory ''T'' in a finite or countable signature is $\omega$-categorical if and only if its automorphism group is oligomorphic. The equivalent characterisations of this subsection, due independently to Engeler, Ryll-Nardzewski and Svenonius, are sometimes referred to as the Ryll-Nardzewski theorem. In combinatorial signatures, a common source of $\omega$-categorical theories are
Fraïssé limit In mathematical logic, specifically in the discipline of model theory, the Fraïssé limit (also called the Fraïssé construction or Fraïssé amalgamation) is a method used to construct (infinite) mathematical structures from their (finite) su ...
s, which are obtained as the limit of amalgamating all possible configurations of a class of finite relational structures.

## Uncountable categoricity

Michael Morley showed in 1963 that there is only one notion of ''uncountable categoricity'' for theories in countable languages. :
Morley's categoricity theorem In mathematical logic, a theory is categorical if it has exactly one model ( up to isomorphism). Such a theory can be viewed as ''defining'' its model, uniquely characterizing the model's structure. In first-order logic, only theories with a ...
:If a first-order theory ''T'' in a finite or countable signature is κ-categorical for some uncountable cardinal κ, then ''T'' is κ-categorical for all uncountable cardinals κ. Morley's proof revealed deep connections between uncountable categoricity and the internal structure of the models, which became the starting point of classification theory and stability theory. Uncountably categorical theories are from many points of view the most well-behaved theories. In particular, complete strongly minimal theories are uncountably categorical. This shows that the theory of algebraically closed fields of a given characteristic is uncountably categorical, with the transcendence degree of the field determining its isomorphism type. A theory that is both $\omega$-categorical and uncountably categorical is called ''totally categorical''.

# Stability theory

A key factor in the structure of the class of models of a first-order theory is its place in the ''stability hierarchy''. :A complete theory ''T'' is called ''$\lambda$-stable'' for a cardinal $\lambda$ if for any model $\mathcal$ of ''T'' and any parameter set $A \subset \mathcal$ of :cardinality not exceeding $\lambda$, there are at most $\lambda$ complete ''T''-types over ''A''. A theory is called ''stable'' if it is $\lambda$-stable for some infinite cardinal $\lambda$. Traditionally, theories that are $\aleph_0$-stable are called ''$\omega$-stable''.

## The stability hierarchy

A fundamental result in stability theory is the '' stability spectrum theorem'', which implies that every complete theory ''T'' in a countable signature falls in one of the following classes: # There are no cardinals $\lambda$ such that ''T'' is $\lambda$-stable. # ''T'' is $\lambda$-stable if and only if $\lambda^ = \lambda$ (see Cardinal exponentiation for an explanation of $\lambda^$). # ''T'' is $\lambda$-stable for any $\lambda \geq 2^$ (where $2^$ is the cardinality of the continuum). A theory of the first type is called ''unstable'', a theory of the second type is called ''strictly stable'' and a theory of the third type is called ''superstable''. Furthermore, if a theory is $\omega$-stable, it is stable in every infinite cardinal, so $\omega$-stability is stronger than superstability. Many construction in model theory are easier when restricted to stable theories; for instance, every model of a stable theory has a saturated elementary extension, regardless of whether the generalised continuum hypothesis is true. Shelah's original motivation for studying stable theories was to decide how many models a countable theory has of any uncountable cardinality. If a theory is uncountably categorical, then it is $\omega$-stable. More generally, the '' Main gap theorem'' implies that if there is an uncountable cardinal $\lambda$ such that a theory ''T'' has less than $2^$ models of cardinality $\lambda$, then ''T'' is superstable.

## Geometric stability theory

The stability hierarchy is also crucial for analysing the geometry of definable sets within a model of a theory. In $\omega$-stable theories, ''
Morley rank In mathematical logic, Morley rank, introduced by , is a means of measuring the size of a subset of a model of a theory, generalizing the notion of dimension in algebraic geometry. Definition Fix a theory ''T'' with a model ''M''. The Morley ran ...
'' is an important dimension notion for definable sets ''S'' within a model. It is defined by
transfinite induction Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for ...
: *The Morley rank is at least 0 if ''S'' is non-empty. *For ''α'' a successor ordinal, the Morley rank is at least ''α'' if in some elementary extension ''N'' of ''M'', the set ''S'' has infinitely many disjoint definable subsets, each of rank at least ''α'' − 1. *For ''α'' a non-zero limit ordinal, the Morley rank is at least ''α'' if it is at least ''β'' for all ''β'' less than ''α''. A theory ''T'' in which every definable set has well-defined Morley Rank is called ''totally transcendental''; if ''T'' is countable, then ''T'' is totally transcendental if and only if ''T'' is $\omega$-stable. Morley Rank can be extended to types by setting the Morley Rank of a type to be the minimum of the Morley ranks of the formulas in the type. Thus, one can also speak of the Morley rank of an element ''a'' over a parameter set ''A'', defined as the Morley rank of the type of ''a'' over ''A''. There are also analogues of Morley rank which are well-defined if and only if a theory is superstable (
U-rank In model theory, a branch of mathematical logic, U-rank is one measure of the complexity of a (complete) type, in the context of stable theories. As usual, higher U-rank indicates less restriction, and the existence of a U-rank for all types over ...
) or merely stable (Shelah's $\infty$-rank). Those dimension notions can be used to define notions of independence and of generic extensions. More recently, stability has been decomposed into simplicity and "not the independence property" (NIP). Simple theories are those theories in which a well-behaved notion of independence can be defined, while NIP theories generalise o-minimal structures. They are related to stability since a theory is stable if and only if it is NIP and simple, and various aspects of stability theory have been generalised to theories in one of these classes.

# Non-elementary model theory

Model-theoretic results have been generalised beyond elementary classes, that is, classes axiomatisable by a first-order theory. Model theory in higher-order logics or infinitary logics is hampered by the fact that completeness and
compactness In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
do not in general hold for these logics. This is made concrete by Lindstrom's theorem, stating roughly that first-order logic is essentially the strongest logic in which both the Löwenheim-Skolem theorems and compactness hold. However, model theoretic techniques have been developed extensively for these logics too. It turns out, however, that much of the model theory of more expressive logical languages is independent of Zermelo-Fraenkel set theory. More recently, alongside the shift in focus to complete stable and categorical theories, there has been work on classes of models defined semantically rather than axiomatised by a logical theory. One example is ''homogeneous model theory'', which studies the class of substructures of arbitrarily large homogeneous models. Fundamental results of stability theory and geometric stability theory generalise to this setting. As a generalisation of strongly minimal theories, quasiminimally excellent classes are those in which every definable set is either countable or co-countable. They are key to the model theory of the
complex exponential function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, al ...
. The most general semantic framework in which stability is studied are abstract elementary classes, which are defined by a ''strong substructure'' relation generalising that of an elementary substructure. Even though its definition is purely semantic, every abstract elementary class can be presented as the models of a first-order theory which omit certain types. Generalising stability-theoretic notions to abstract elementary classes is an ongoing research program.

# Selected applications

Among the early successes of model theory are Tarski's proofs of quantifier elimination for various algebraically interesting classes, such as the
real closed field In mathematics, a real closed field is a field ''F'' that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers. D ...
s, Boolean algebras and
algebraically closed field In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in . Examples As an example, the field of real numbers is not algebraically closed, because ...
s of a given characteristic. Quantifier elimination allowed Tarski to show that the first-order theories of real-closed and algebraically closed fields as well as the first-order theory of Boolean algebras are decidable, classify the Boolean algebras up to elementary equivalence and show that the theories of real-closed fields and algebraically closed fields of a given characteristic are unique. Furthermore, quantifier elimination provided a precise description of definable relations on algebraically closed fields as algebraic varieties and of the definable relations on real-closed fields as
semialgebraic sets In mathematics, a semialgebraic set is a subset ''S'' of ''Rn'' for some real closed field ''R'' (for example ''R'' could be the field of real numbers) defined by a finite sequence of polynomial equations (of the form P(x_1,...,x_n) = 0) and inequ ...
In the 1960s, the introduction of the ultraproduct construction led to new applications in algebra. This includes Ax's work on
pseudofinite field In mathematics, a pseudo-finite field ''F'' is an infinite model of the first-order theory of finite fields. This is equivalent to the condition that ''F'' is quasi-finite (perfect with a unique extension of every positive degree) and pseudo al ...
s, proving that the theory of finite fields is decidable, and Ax and Kochen's proof of as special case of Artin's conjecture on diophantine equations, the Ax-Kochen theorem. The ultraproduct construction also led to Abraham Robinson's development of nonstandard analysis, which aims to provide a rigorous calculus of
infinitesimals In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero. The word ''infinitesimal'' comes from a 17th-century Modern Latin coinage ''infinitesimus'', which originally refe ...
. More recently, the connection between stability and the geometry of definable sets led to several applications from algebraic and diophantine geometry, including Ehud Hrushovski's 1996 proof of the geometric Mordell-Lang conjecture in all characteristics In 2001, similar methods were used to prove a generalisation of the Manin-Mumford conjecture. In 2011,
Jonathan Pila Jonathan Solomon Pila (born 1962) FRS One or more of the preceding sentences incorporates text from the royalsociety.org website where: is an Australian mathematician at the University of Oxford. Education Pila earned his bachelor's degree at ...
applied techniques around
o-minimality In mathematical logic, and more specifically in model theory, an infinite structure (''M'',<,...) which is totally ordered by < is called an o-minimal structure if and only if every André-Oort conjecture for products of Modular curves. In a separate strand of inquiries that also grew around stable theories, Laskowski showed in 1992 that NIP theories describe exactly those definable classes that are PAC-learnable in machine learning theory. This has led to several interactions between these separate areas. In 2018, the correspondence was extended as Hunter and Chase showed that stable theories correspond to online learnable classes.

# History

Model theory as a subject has existed since approximately the middle of the 20th century, and the name was coined by
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
, a member of the Lwów–Warsaw school, in 1954. However some earlier research, especially in
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
, 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 Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imm ...
'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 Anatoly Ivanovich Maltsev (also: Malcev, Mal'cev; Russian: Анато́лий Ива́нович Ма́льцев; 27 November N.S./14 November O.S. 1909, Moscow Governorate – 7 June 1967, Novosibirsk) was born in Misheronsky, near Moscow, an ...
. The development of model theory as an independent discipline was brought on by Alfred Tarski during the
interbellum In the history of the 20th century, the interwar period lasted from 11 November 1918 to 1 September 1939 (20 years, 9 months, 21 days), the end of the First World War to the beginning of the Second World War. The interwar period was relative ...
. Tarski's work included
logical consequence Logical consequence (also entailment) is a fundamental concept in logic, which describes the relationship between statements that hold true when one statement logically ''follows from'' one or more statements. A valid logical argument is on ...
,
deductive system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A for ...
s, 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. In the further history of the discipline, different strands began to emerge, and the focus of the subject shifted. In the 1960s, techniques around ultraproducts became a popular tool in model theory. At the same time, researchers such as James Ax were investigating the first-order model theory of various algebraic classes, and others such as H. Jerome Keisler were extending the concepts and results of first-order model theory to other logical systems. Then, inspired by Morley's problem, Shelah developed
stability theory In mathematics, stability theory addresses the stability of solutions of differential equations and of trajectories of dynamical systems under small perturbations of initial conditions. The heat equation, for example, is a stable partial diffe ...
. His work around stability changed the complexion of model theory, giving rise to a whole new class of concepts. This is known as the paradigm shift Over the next decades, it became clear that the resulting stability hierarchy is closely connected to the geometry of sets that are definable in those models; this gave rise to the subdiscipline now known as geometric stability theory. An example of an influential proof from geometric model theory is Hrushovski's proof of the Mordell–Lang conjecture for function fields.

# Connections to related branches of mathematical logic

## Finite model theory

Finite model theory Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to inte ...
, which concentrates on finite structures, diverges significantly from the study of infinite structures in both the problems studied and the techniques used. In particular, many central results of classical model theory that fail when restricted to finite structures. This includes the compactness theorem, Gödel's completeness theorem, and the method of ultraproducts for first-order logic. At the interface of finite and infinite model theory are algorithmic or
computable model theory Computable model theory is a branch of model theory which deals with questions of computability as they apply to model-theoretical structures. Computable model theory introduces the ideas of computable and decidable models and theories and one of ...
and the study of 0-1 laws, where the infinite models of a generic theory of a class of structures provide information on the distribution of finite models. Prominent application areas of FMT are descriptive complexity theory, database theory and formal language theory.

## Set theory

Any
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
(which is expressed in a
countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
language), 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 In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that or equivalently, that In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
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 Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
; for example in
Kurt Gödel Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imm ...
'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 Independence is a condition of a person, nation, country, or state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independence is the stat ...
of the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
and the continuum hypothesis from the other axioms of set theory. In the other direction, model theory is itself formalised within Zermelo-Fraenkel set theory. For instance, the development of the fundamentals of model theory (such as the compactness theorem) rely on the axiom of choice, and is in fact equivalent over Zermelo-Fraenkel set theory without choice to 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 (in its own cardinality). 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 (such as compactness for infinitary logics) have been shown to be equivalent to large cardinal axioms.

*
Abstract model theory In mathematical logic, abstract model theory is a generalization of model theory that studies the general properties of extensions of first-order logic and their models. Abstract model theory provides an approach that allows us to step back and stu ...
* Algebraic theory *
Axiomatizable class In model theory, a branch of mathematical logic, an elementary class (or axiomatizable class) is a class consisting of all structures satisfying a fixed first-order theory. Definition A class ''K'' of structures of a signature σ is called an ...
* Compactness theorem *
Descriptive complexity ''Descriptive Complexity'' is a book in mathematical logic and computational complexity theory by Neil Immerman. It concerns descriptive complexity theory, an area in which the expressibility of mathematical properties using different types of l ...
*
Elementary equivalence In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature ''σ'' are called elementarily equivalent if they satisfy the same first-order ''σ''-sentences. If ''N'' is a substructure of ''M'', one of ...
*
First-order theories In first-order logic, a first-order theory is given by a Set (mathematics), set of axioms in some language. This entry lists some of the more common examples used in model theory and some of their properties. Preliminaries For every natural mat ...
* Hyperreal number *
Institutional model theory :''This page is about the concept in mathematical logic. For the concepts in sociology, see Institutional theory and Institutional logic''. In mathematical logic, institutional model theory generalizes a large portion of first-order model theory t ...
* Kripke semantics *
Löwenheim–Skolem theorem In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. It implies that if a countable first-ord ...
*
Model-theoretic grammar Model-theoretic grammars, also known as constraint-based grammars, contrast with generative grammars in the way they define sets of sentences: they state constraints on syntactic structure rather than providing operations for generating syntactic ...
*
Proof theory Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Barwise (1978) consists of four corresponding part ...
*
Saturated model In mathematical logic, and particularly in its subfield model theory, a saturated model ''M'' is one that realizes as many complete types as may be "reasonably expected" given its size. For example, an ultrapower model of the hyperreals is ...
* Skolem normal form

# References

* * * *

## Other textbooks

* * * * * * * * * *

## Free online texts

* * * * Hodges, Wilfrid,
Model theory
'. The Stanford Encyclopedia Of Philosophy, E. Zalta (ed.). * Hodges, Wilfrid,
First-order 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)
Model-Theoretic Logics
Perspectives in Mathematical Logic, Volume 8, New York: Springer-Verlag, 1985. {{Authority control Model