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 formal ...
, and particularly in its subfield
model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the ...
, a saturated model ''M'' is one that realizes as many
complete type
In model theory and related areas of mathematics, a type is an object that describes how a (real or possible) element or finite collection of elements in a mathematical structure might behave. More precisely, it is a set of first-order formulas in ...
s as may be "reasonably expected" given its size. For example, an
ultrapower model of the
hyperreals
In mathematics, the system of hyperreal numbers is a way of treating infinite and infinitesimal (infinitely small but non-zero) quantities. The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains numbe ...
is
-saturated, meaning that every descending nested sequence of
internal sets has a nonempty intersection.
Definition
Let ''κ'' be a
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb
Traditionally, a finite verb (from la, fīnītus, past partici ...
or
infinite
Infinite may refer to:
Mathematics
*Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
*Infinite (group)
Infinite ( ko, 인피니트; stylized as INFINITE) is a South Ko ...
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. T ...
and ''M'' a model in some
first-order language
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantif ...
. Then ''M'' is called ''κ''-saturated if for all subsets ''A'' ⊆ ''M'' of
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 ...
less than ''κ'', the model ''M'' realizes all
complete types over ''A''. The model ''M'' is called saturated if it is , ''M'', -saturated where , ''M'', denotes the cardinality of ''M''. That is, it realizes all complete types over sets of parameters of size less than , ''M'', . According to some authors, a model ''M'' is called countably saturated if it is
-saturated; that is, it realizes all complete types over countable sets of parameters. According to others, it is countably saturated if it is countable and saturated.
[Chang and Keisler 1990]
Motivation
The seemingly more intuitive notion—that all complete types of the language are realized—turns out to be too weak (and is appropriately named weak saturation, which is the same as 1-saturation). The difference lies in the fact that many structures contain elements that are not definable (for example, any
transcendental
Transcendence, transcendent, or transcendental may refer to:
Mathematics
* Transcendental number, a number that is not the root of any polynomial with rational coefficients
* Algebraic element or transcendental element, an element of a field exten ...
element of R is, by definition of the word, not definable in the language of
fields). However, they still form a part of the structure, so we need types to describe relationships with them. Thus we allow sets of parameters from the structure in our definition of types. This argument allows us to discuss specific features of the model that we may otherwise miss—for example, a bound on a ''specific'' increasing sequence ''c
n'' can be expressed as realizing the type which uses countably many parameters. If the sequence is not definable, this fact about the structure cannot be described using the base language, so a weakly saturated structure may not bound the sequence, while an ℵ
1-saturated structure will.
The reason we only require parameter sets that are strictly smaller than the model is trivial: without this restriction, no infinite model is saturated. Consider a model ''M'', and the type Each finite subset of this type is realized in the (infinite) model ''M'', so by compactness it is consistent with ''M'', but is trivially not realized. Any definition that is universally unsatisfied is useless; hence the restriction.
Examples
Saturated models exist for certain theories and cardinalities:
* (Q, <)—the set of
rational number
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 ...
s with their usual ordering—is saturated. Intuitively, this is because any type consistent with the
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 ...
is implied by the order type; that is, the order the variables come in tells you everything there is to know about their role in the structure.
* (R, <)—the set of
real number
In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s with their usual ordering—is ''not'' saturated. For example, take the type (in one variable ''x'') that contains the formula
for every natural number ''n'', as well as the formula
. This type uses ω different parameters from R. Every finite subset of the type is realized on R by some real ''x'', so by compactness the type is consistent with the structure, but it is not realized, as that would imply an upper bound to the sequence −1/''n'' that is less than 0 (its least upper bound). Thus (R,<) is ''not'' ω
1-saturated, and not saturated. However, it ''is'' ω-saturated, for essentially the same reason as Q—every finite type is given by the order type, which if consistent, is always realized, because of the density of the order.
*A dense totally ordered set without endpoints is a
ηα set if and only if it is ℵ
α-saturated.
* The
countable random graph
In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whet ...
, with the only non-logical symbol being the edge existence relation, is also saturated, because any complete type is isolated (implied) by the finite subgraph consisting of the variables and parameters used to define the type.
Both the theory of Q and the theory of the countable random graph can be shown to be
ω-categorical through the
back-and-forth method. This can be generalized as follows: the unique model of cardinality ''κ'' of a countable ''κ''-categorical theory is saturated.
However, the statement that every model has a saturated
elementary extension is not provable in
ZFC. In fact, this statement is equivalent to the existence of a proper class of cardinals ''κ'' such that ''κ''
<''κ'' = ''κ''. The latter identity is equivalent to for some ''λ'', or ''κ'' is
strongly inaccessible
In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal is strongly inaccessible if it is uncountable, it is not a sum of f ...
.
Relationship to prime models
The notion of saturated model is dual to the notion of
prime model in the following way: let ''T'' be a countable theory in a first-order language (that is, a set of mutually consistent sentences in that language) and let ''P'' be a prime model of ''T''. Then ''P'' admits an
elementary embedding 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 ofte ...
into any other model of ''T''. The equivalent notion for saturated models is that any "reasonably small" model of ''T'' is elementarily embedded in a saturated model, where "reasonably small" means cardinality no larger than that of the model in which it is to be embedded. Any saturated model is also
homogeneous
Homogeneity and heterogeneity are concepts often used in the sciences and statistics relating to the uniformity of a substance or organism. A material or image that is homogeneous is uniform in composition or character (i.e. color, shape, siz ...
. However, while for countable theories there is a unique prime model, saturated models are necessarily specific to a particular cardinality. Given certain set-theoretic assumptions, saturated models (albeit of very large cardinality) exist for arbitrary theories. For ''λ''-
stable theories, saturated models of cardinality ''λ'' exist.
Notes
References
*
Chang, C. C.;
Keisler, H. J. Model theory. Third edition. Studies in Logic and the Foundations of Mathematics, 73. North-Holland Publishing Co., Amsterdam, 1990. xvi+650 pp.
* R. Goldblatt (1998). Lectures on the hyperreals. An introduction to nonstandard analysis. Springer.
* Marker, David (2002). ''Model Theory: An Introduction''. New York: Springer-Verlag.
* Poizat, Bruno; Trans: Klein, Moses (2000), ''A Course in Model Theory'', New York: Springer-Verlag.
*
{{Mathematical logic
Mathematical logic
Model theory
Nonstandard analysis