Löwenheim–Skolem theorem

In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, 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 are 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.
Contents
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 function symbols 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 shattered completely by Gödel's incompleteness theorem.
Many consequences of the Löwenheim–Skolem theorem 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
For each firstorder formula the axiom of choice implies the existence of a function
such that, for all , either
or
Applying the axiom of choice again we get a function from the first order formulas φ to such functions
The family of functions f_{φ} gives rise to a preclosure operator on the power set of
for
Iterating countably many times results in a closure operator Taking an arbitrary subset such that , and having defined one can see that also is an elementary substructure of by the Tarski–Vaught test.
The trick used in this proof is essentially due to Skolem, who introduced function symbols for the Skolem functions f_{φ} into the language. One could also define the f_{φ} as partial functions such that f_{φ} is defined if and only if The only important point is that is a preclosure operator such that contains a solution for every formula with parameters in which has a solution in 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öwenheim–Skolem 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, JSTOR 1986462
 Löwenheim, Leopold (1915), "Über Möglichkeiten im Relativkalkül", Mathematische Annalen 76 (4): 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
Categories: Model theory
 Theorems in the foundations of mathematics
 Metatheorems
Wikimedia Foundation. 2010.
Look at other dictionaries:
LöwenheimSkolemTheorem — Das Löwenheim Skolem Theorem besagt, dass eine Menge von Aussagen der Prädikatenlogik erster Stufe, die in einem Modell mit einer überabzählbar unendlich großen Domäne erfüllt ist, immer auch in einem Modell mit einer abzählbar unendlich großen… … Deutsch Wikipedia
Löwenheim–Skolem theorem — See Skolem–Löwenheim theorem … Philosophy dictionary
LöwenheimSkolem — Das Löwenheim Skolem Theorem besagt, dass eine Menge von Aussagen der Prädikatenlogik erster Stufe, die in einem Modell mit einer überabzählbar unendlich großen Domäne erfüllt ist, immer auch in einem Modell mit einer abzählbar unendlich großen… … Deutsch Wikipedia
Satz von LöwenheimSkolem — Das Löwenheim Skolem Theorem besagt, dass eine Menge von Aussagen der Prädikatenlogik erster Stufe, die in einem Modell mit einer überabzählbar unendlich großen Domäne erfüllt ist, immer auch in einem Modell mit einer abzählbar unendlich großen… … Deutsch Wikipedia
Skolem's paradox — is the mathematical fact that every countable axiomatisation of set theory in first order logic, if consistent, has a model that is countable, even if it is possible to prove, from those same axioms, the existence of sets that are not countable.… … Wikipedia
Löwenheim — oder Loewenheim ist der Familienname folgender Personen: Leopold Löwenheim (1878–1957), deutscher Logiker und Mathematiker Ulrich Loewenheim (* 1934), deutscher Rechtswissenschaftler Walter Loewenheim (1896–1977; auch Walter Lowe, Pseudonyme… … Deutsch Wikipedia
SkolemParadox — Das Löwenheim Skolem Theorem besagt, dass eine Menge von Aussagen der Prädikatenlogik erster Stufe, die in einem Modell mit einer überabzählbar unendlich großen Domäne erfüllt ist, immer auch in einem Modell mit einer abzählbar unendlich großen… … Deutsch Wikipedia
Löwenheim number — In mathematical logic the Löwenheim number of an abstract logic is the smallest cardinal number for which a weak downward Löwenheim–Skolem theorem holds.[1] They are named after Leopold Löwenheim, who proved that these exist for a very broad… … Wikipedia
Skolem , Thoralf Albert — (1887–1963) Norwegian mathematician The son of a teacher, Skolem was born at Sandsvaer in Norway and educated at the University of Oslo. He joined the faculty in 1911 and was appointed professor of mathematics in 1938, a post he held until his… … Scientists
Theorem — The Pythagorean theorem has at least 370 known proofs[1] In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements … Wikipedia