From Wikipedia, the free encyclopedia
In mathematical logic, the
Löwenheim–Skolem theorem states that if a
countable firstorder theory has an infinite model, then for every
infinite cardinal number κ it has a model of
size κ. The result implies that firstorder theories are unable to
control the cardinality of their infinite models, and that no
firstorder theory with an infinite model can have exactly one
model up to isomorphism.
The (downward) Löwenheim–Skolem theorem is one of the two key
properties, along with the compactness theorem, that is used
in Lindström's theorem to characterize
firstorder logic. In general, the Löwenheim–Skolem theorem does
not hold in stronger logics such as secondorder logic.
Background
A signature consists of a set of
function symbols S_{func}, a set of relation
symbols S_{rel}, and a function
representing the arity of
function and relation symbols. (A nullary function symbol is called
a constant symbol.) In the context of firstorder logic, a
signature is sometimes called a language. It is
called countable if the set of function and relation symbols in it
is countable, and in general the cardinality of a signature is the
cardinality of the set of all the symbols it contains.
A firstorder theory consists of
a fixed signature and a fixed set of sentences (formulas with no
free variables) in that signature. Theories are often specified by
giving a list of axioms that generate the theory, or by giving a
structure and taking the theory to consist of the sentences
satisfied by the structure.
Given a signature σ, a σstructure M is
a concrete interpretation of the symbols in σ. It consists of an
underlying set (often also denoted by "M") together with
an interpretation of the function and relation symbols of σ. An
interpretation of a constant symbol of σ in M is simply an
element of M. More generally, an interpretation of an
nary function symbol f is a function from
M^{n} to M. Similarly, an
interpretation of a relation symbol R is an nary
relation on M, i.e. a subset of
M^{n}.
A substructure of a σstructure M is
obtained by taking a subset N of M which is
closed under the interpretations of all the functions in σ (hence
includes the interpretations of all constant symbols in σ), and
then restricting the interpretations of the relation symbols to
N. An elementary
substructure is a very special case of this; in particular an
elementary substructure satisfies exactly the same firstorder
sentences as the original structure (its elementary
extension).
Precise
statement
The modern statement of the theorem is both more general and
stronger than the version for countable signatures stated in the
introduction.
In its general form, the Löwenheim–Skolem
Theorem states that for every signature σ, every infinite σstructure M and
every infinite cardinal number κ ≥ σ there is a σstructure
N such that N = κ and
 if κ < M then N is an elementary
substructure of M;
 if κ > M then N is an elementary
extension of M.
The theorem is often divided into two parts corresponding to the
two bullets above. The part of the theorem asserting that a
structure has elementary substructures of all smaller infinite
cardinalities is known as the downward Löwenheim–Skolem
Theorem. The part of the theorem asserting that a
structure has elementary extensions of all larger cardinalities is
known as the upward Löwenheim–Skolem Theorem.
The statement given in the introduction follows immediately by
taking M to be an infinite model of the theory. The proof
of the upward part of the theorem also shows that a theory with
arbitrarily large finite models must have an infinite model;
sometimes this is considered to be part of the theorem. For
historical variants of the theorem, see the notes below.
Examples and
consequences
Let N denote the natural numbers and
R the reals. It follows from the theorem that the
theory of (N, +, ×, 0, 1) (the theory of true
firstorder arithmetic) has uncountable models, and that the theory
of (R, +, ×, 0, 1) (the theory of real closed
fields) has a countable model. There are, of course,
axiomatizations characterizing (N, +, ×, 0, 1) and
(R, +, ×, 0, 1) up to isomorphism. The
Löwenheim–Skolem theorem shows that these axiomatizations cannot be
firstorder. For example, the completeness of a linear order, which
is used to characterize the real numbers as a complete ordered
field, is a nonfirstorder property.
A theory is called categorical if it has only
one model, up to isomorphism. This term was introduced by Oswald Veblen in
1904, and for some time thereafter mathematicians hoped they could
put mathematics on a solid foundation by describing a categorical
firstorder theory of some version of set theory. The
Löwenheim–Skolem theorem dealt a first blow to this hope, as it
implies that a firstorder theory which has an infinite model
cannot be categorical. Later, in 1931, the hope was scattered
completely by Gödel's
incompleteness theorem.
Many consequences of the Löwenheim–Skolem seemed
counterintuitive to logicians in the early 20th century, as the
distinction between firstorder and nonfirstorder properties was
not yet understood. One such consequence is the existence of
uncountable models of true arithmetic, which satisfy every
firstorder induction
axiom but have noninductive subsets. Another consequence that
was considered particularly troubling is the existence of a
countable model of set theory, which nevertheless must satisfy the
sentence saying the real numbers are uncountable. This
counterintuitive situation came to be known as Skolem's
paradox; it shows that the notion of countability is not absolute.
Proof
sketch
Downward
part
Fix a firstorder σformula .
By the axiom of
choice, there is a function
such that, for all ,
either

or
The family of functions
gives rise to a finitary preclosure operator F on the power set of M:
Iterating F countably many
times results in a closure operator F^{ω}. Taking an arbitrary
subset
such that ,
and having defined N =
F^{ω}(A), one can see that also
.
N is an elementary
substructure of M by the Tarski–Vaught test.
The trick used in this proof is essentially due to Skolem, who
introduced function symbols for the Skolem functions
into the language. One could also define the
as partial
functions such that
is defined if and only if
The only important point is that F is a preclosure operator such
that F(A) contains a
solution for every formula with parameters in A which has a solution in M, and that .
Upward
part
First, one extends the signature by adding a new constant symbol
for every element of M. The complete theory of M
for the extended signature σ' is called the elementary
diagram of M. In the next step one adds κ many new
constant symbols to the signature and adds to the elementary
diagram of M the sentences c ≠ c' for
any two distinct new constant symbols c and c'.
Using the compactness theorem, the resulting
theory is easily seen to be consistent. Since its models must have
cardinality at least κ, the downward part of this theorem
guarantees the existence of a model N which has
cardinality exactly κ. It contains an isomorphic copy of M
as an elementary substructure.
Historical
notes
This account is based mainly on Dawson (1993). To understand the
early history of model theory one must distinguish between
syntactical consistency (no contradiction can be derived
using the deduction rules for firstorder logic) and
satisfiability (there is a model). Somewhat surprisingly,
even before the completeness theorem made
the distinction unnecessary, the term consistent was used
sometimes in one sense and sometimes in the other.
The first significant result in what later became model theory was
Löwenheim's theorem in Leopold Löwenheim's publication "Über
Möglichkeiten im Relativkalkül" (1915):
 For every countable signature σ, every σsentence which is
satisfiable is satisfiable in a countable model.
Löwenheim's proof, however, was faulty. Thoralf Skolem
(1920) gave a correct proof using formulas in what would later be
called Skolem normal form and relying on the axiom of
choice:
 Every countable theory which is satisfiable in a model
M, is satisfiable in a countable substructure of
M.
Skolem (1923) also proved the following weaker version without
the axiom of choice:
 Every countable theory which is satisfiable in a model is also
satisfiable in a countable model.
Skolem (1929) simplified Skolem (1920). Finally, Anatoly Ivanovich
Maltsev (Анато́лий Ива́нович Ма́льцев, 1936) proved the
Löwenheim–Skolem theorem in its full generality. He cited a note by
Skolem, according to which the theorem had been proved by Alfred Tarski in a
seminar in 1928. Therefore the general theorem is sometimes known
as the Löwenheim–Skolem–Tarski theorem. But Tarski did not
remember his proof, and it remains a mystery how he could do it
without the compactness theorem.
It is somewhat ironic that Skolem's name is connected with the
upward direction of the theorem as well as with the downward
direction:
 "I follow custom in calling Corollary 6.1.4 the upward
LöwenheimSkolem theorem. But in fact Skolem didn't even believe
it, because he didn't believe in the existence of uncountable
sets." – Hodges (1993).
 "Skolem [...] rejected the result as meaningless; Tarski
[...] very reasonably responded that Skolem's formalist viewpoint
ought to reckon the downward LöwenheimSkolem theorem meaningless
just like the upward." – Hodges (1993).
 "Legend has it that Thoralf Skolem, up until the end of his
life, was scandalized by the association of his name to a result of
this type, which he considered an absurdity, nondenumerable sets
being, for him, fictions without real existence." – Poizat
(2000).
References
The LöwenheimSkolem theorem is treated in all introductory
texts on model
theory or mathematical logic.
Historical publications
 Veblen, Oswald
(1904), "A System of Axioms for Geometry", Transactions of the
American Mathematical Society 5 (3): 343–384,
doi:10.2307/1986462, ISSN 00029947
 Löwenheim,
Leopold (1915), "Über Möglichkeiten im Relativkalkül",
Mathematische Annalen 76: 447–470, doi:10.1007/BF01458217, ISSN 00255831
 Skolem, Thoralf
(1920), "Logischkombinatorische Untersuchungen über die
Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem
Theoreme über dichte Mengen", Videnskapsselskapet Skrifter, I.
Matematisknaturvidenskabelig Klasse 6:
1–36
 Skolem,
Thoralf (1923) Einige Bemerkungen zu axiomatischen Begründung
der Mengenlehre, Mathematikerkongressen i Helsingfors 4.–7.
Juli 1922, Den femte skandinaviska matematikerkongressen,
Redogoerelse, 217–232.
 Skolem, Thoralf
(1929), "Über einige Grundlagenfragen der Mathematik", Skrifter
utgitt av det Norske VidenskapsAkademi i Oslo, I.
Matematisknaturvidenskabelig Klasse 7:
1–49
 Maltsev, Anatoly
Ivanovich (1936), "Untersuchungen aus dem Gebiete der
mathematischen Logik", Matematicheskii Sbornik, n.s.
1: 323–336
Secondary
sources
 Badesa, Calixto
(2004), The Birth of Model Theory: Löwenheim's Theorem in the
Frame of the Theory of Relatives, Princeton, NJ: Princeton
University Press, ISBN
9780691058535
 Burris, Stanley N., Contributions of the
Logicians, Part II, From Richard Dedekind to Gerhard
Gentzen
 Burris, Stanley N., Downward Löwenheim–Skolem
theorem
 Dawson, John W.,
Jr. (1993), "The compactness of FirstOrder Logic: From Gödel to
Lindström", History and Philosophy of Logic
14: 15–37, doi:10.1080/01445349308837208
 Hodges, Wilfrid
(1993), Model theory, Cambridge: Cambridge Univ. Pr., ISBN
9780521304429
 Poizat, Bruno
(2000), A Course in Model Theory: An Introduction to
Contemporary Mathematical Logic, Berlin, New York: Springer,
ISBN
9780387986555
 Simpson, Stephen G. (1998), Model Theory