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 ...
expressing statements about a
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 ...
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 and prefixing of quantifiers or . A sentence is a formula in which each occurrence of a variable is in the scope of a corresponding quantifier. Examples for formulas are φ (or φ(x) to mark the fact that at most x is an unbound variable in φ) and ψ defined as follows:
:
(Note that the equality symbol has a double meaning here.) It is intuitively clear how to translate such formulas into mathematical meaning. In the σsmr-structure of the natural numbers, for example, an element ''n'' ''satisfies'' the formula φ if and only if ''n'' is a prime number. The formula ψ similarly defines
irreducibility
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 , so that one easily proves:
: is a prime number.
: is irreducible.
A set 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'' , i.e. a structure (of the appropriate signature) which satisfies all the sentences in the set . 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 together with interpretations of each of the symbols of the signature as relations and functions on (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 , where and are 0-ary function symbols (also known as constant symbols), and 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 (so that e.g. is a function from to and is a subset of ), one obtains a structure .
A structure is said to model a set of first-order sentences in the given language if each sentence in is true in with respect to the interpretation of the signature previously specified for . (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 of a σ-structure is a subset of its domain, closed under all functions in its signature σ, which is regarded as a σ-structure by restricting all functions and relations in σ to the subset.
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 ,
: if and only if .
In particular, if ''φ'' is a sentence and an elementary substructure of , then if and only if . Thus, an elementary substructure is a model of a theory exactly when the superstructure is a model.
Example: While the field of algebraic numbers is an elementary substructure of the field of complex numbers , the rational field is not, as we can express "There is a square root of 2" as a first-order sentence satisfied by but not by .
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 into another σ-structure is a map ''f'': ''A'' → ''B'' between the domains which can be written as an isomorphism of with a substructure of . 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 the formula
:
defines the subset of prime numbers, while the formula
:
defines the subset of even numbers.
In a similar way, formulas with ''n'' free variables define subsets of . For example, in a field, the formula
:
defines the curve of all such that .
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 , the formula
:
uses the parameter from 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. 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:
:,
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
:.
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 is called minimal if every subset definable with parameters from 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 of real numbers is not minimal: Consider, for instance, the definable set
:.
This defines the subset of non-negative real numbers, which is neither finite nor cofinite.
One can in fact use to define arbitrary intervals on the real number line.
It turns out that these suffice to represent every definable subset of .
This generalisation of minimality has been very useful in the model theory of ordered structures.
A densely totally ordered structure in a signature including a symbol for the order relation is called o-minimal if every subset definable with parameters from 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 , ''n''-ary relations can also be definable. Functions are definable if the function graph is a definable relation, and constants are definable if there is a formula such that ''a'' is the only element of such that 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 interprets another whose theory is undecidable, then itself is undecidable.
Types
Basic notions
For a sequence of elements of a structure and a subset ''A'' of , one can consider the set of all first-order formulas with parameters in ''A'' that are satisfied by . This is called the ''complete (n-)type realised by'' ''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 that is constant on ''A'' and sends to respectively, then and realise the same complete type over ''A''.
The real number line , viewed as a structure with only the order relation , will serve as a running example in this section.
Every element 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 depends on their order: either , or .
Over the subset 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 is a structure and ''A'' a subset of , 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 of .
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 . If ''A'' is the empty set, then the type space only depends on the theory of . The notation is commonly used for the set of types over the empty set consistent with .
If there is a single formula such that the theory of implies for every formula in ''p'', then ''p'' is called ''isolated''.
Since the real numbers 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 that is not realised in the real number line .
A subset of that can be expressed as exactly those elements of realising a certain type over ''A'' is called ''type-definable'' over ''A''.
For an algebraic example, suppose 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 -types over a subfield 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 ...