Inmathematical logic, theLöwenheim–Skolem theorem is a theorem on the existence andcardinality ofmodels, named afterLeopold Löwenheim andThoralf Skolem.

The precise formulation is given below. It implies that if acountablefirst-ordertheory has an infinitemodel, then for every infinitecardinal numberκ it has a model of sizeκ, and that no first-order theory with an infinite model can have a unique modelup to isomorphism. As a consequence, first-order theories are unable to control the cardinality of their infinite models.

The (downward) Löwenheim–Skolem theorem is one of the two key properties, along with thecompactness theorem, that are used inLindström's theorem to characterizefirst-order logic. In general, the Löwenheim–Skolem theorem does not hold in stronger logics such assecond-order logic.

In its general form, theLöwenheim–Skolem Theorem states that for everysignatureσ, every infiniteσ-structureM and every infinite cardinal numberκ ≥ |σ|, there is aσ-structureN such that|N| =κ and such that

• ifκ < |M| thenN is an elementary substructure ofM;
• ifκ ≥ |M| thenN is an elementary extension ofM.

The theorem is often divided into two parts corresponding to the two cases above. The part of the theorem asserting that a structure has elementary substructures of all smaller infinite cardinalities is known as thedownward Löwenheim–Skolem Theorem.^{[1]: 160–162} The part of the theorem asserting that a structure has elementary extensions of all larger cardinalities is known as theupward Löwenheim–Skolem Theorem.^[2]

Below we elaborate on the general concept of signatures and structures.

Asignature consists of a set of function symbolsS_func, a set of relation symbolsS_rel, and a function${\displaystyle \mathrm{ar}:S_{\mathrm{func}}\cup S_{\mathrm{rel}}\to {\mathbb{N}}_0}$ representing thearity of function and relation symbols. (A nullary function symbol is called a constant symbol.) In the context of first-order 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 first-ordertheory consists of a fixed signature and a fixed set of sentences (formulas with no free variables) in that signature.^[3]: 40 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σ-structureMis 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σ inM is simply an element ofM. More generally, an interpretation of ann-ary function symbolf is a function fromMⁿ toM. Similarly, an interpretation of a relation symbolR is ann-ary relation onM, i.e. a subset of Mⁿ.

A substructure of aσ-structureM is obtained by taking a subsetN ofM 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 toN. Anelementary substructure is a very special case of this; in particular an elementary substructure satisfies exactly the same first-order sentences as the original structure (its elementary extension).

The statement given in the introduction follows immediately by takingM 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.^[1]

A theory is calledcategorical if it has only one model, up to isomorphism. This term was introduced byVeblen (1904), and for some time thereafter mathematicians hoped they could put mathematics on a solid foundation by describing a categorical first-order theory of some version of set theory. The Löwenheim–Skolem theorem dealt a first blow to this hope, as it implies that a first-order theory which has an infinite model cannot be categorical. Later, in 1931, the hope was shattered completely byGödel's incompleteness theorem.^[1]

Many consequences of the Löwenheim–Skolem theorem seemed counterintuitive to logicians in the early 20th century, as the distinction between first-order and non-first-order properties was not yet understood. One such consequence is the existence of uncountable models oftrue arithmetic, which satisfy every first-orderinduction axiom but have non-inductive subsets.

LetN denote the natural numbers andR the reals. It follows from the theorem that the theory of (N, +, ×, 0, 1) (the theory of true first-order arithmetic) has uncountable models, and that the theory of (R, +, ×, 0, 1) (the theory ofreal 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 first-order. For example, in the theory of the real numbers, the completeness of a linear order used to characterizeR as a complete ordered field, is anon-first-order property.^[1]: 161

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.Cantor's theorem states that some sets are uncountable. This counterintuitive situation came to be known asSkolem's paradox; it shows that the notion of countability is notabsolute.^[4]

For each first-order${\displaystyle \sigma }$-formula${\displaystyle \phi (y,x_1,\dots ,x_n)}$, theaxiom of choice implies the existence of a function

${\displaystyle f_{\phi }:M^n\to M}$

such that, for all${\displaystyle a_1,\dots ,a_n\in M}$, either

${\displaystyle M\models \phi (f_{\phi }(a_1,\dots ,a_n),a_1,\dots ,a_n)}$

or

${\displaystyle M\models \mathrm{\neg }\mathrm{\exists }y\phi (y,a_1,\dots ,a_n)}$.

Applying the axiom of choice again we get a function from the first-order formulas${\displaystyle \phi }$ to such functions${\displaystyle f_{\phi }}$.

The family of functions${\displaystyle f_{\phi }}$ gives rise to apreclosure operator${\displaystyle F}$ on thepower set of${\displaystyle M}$

${\displaystyle F(A)=\{f_{\phi }(a_1,\dots ,a_n)\in M\mid \phi \in \sigma ;a_1,\dots ,a_n\in A\}}$

for${\displaystyle A\subseteq M}$.

Iterating${\displaystyle F}$ countably many times results in aclosure operator${\displaystyle F^{\omega }}$. Taking an arbitrary subset${\displaystyle A\subseteq M}$ such that${\displaystyle \left|A\right|=\kappa }$, and having defined${\displaystyle N=F^{\omega }(A)}$, one can see that also${\displaystyle \left|N\right|=\kappa }$. Then${\displaystyle N}$ is an elementary substructure of${\displaystyle M}$ by theTarski–Vaught test.

The trick used in this proof is essentially due to Skolem, who introduced function symbols for theSkolem functions${\displaystyle f_{\phi }}$ into the language. One could also define the${\displaystyle f_{\phi }}$ aspartial functions such that${\displaystyle f_{\phi }}$ is defined if and only if${\displaystyle M\models \mathrm{\exists }y\phi (y,a_1,\dots ,a_n)}$. The only important point is that${\displaystyle F}$ is a preclosure operator such that${\displaystyle F(A)}$ contains a solution for every formula with parameters in${\displaystyle A}$ which has a solution in${\displaystyle M}$ and that

${\displaystyle \left|F(A)\right|\le \left|A\right|+\left|\sigma \right|+{\mathrm{\aleph }}_0}$.

First, one extends the signature by adding a new constant symbol for every element of${\displaystyle M}$. The complete theory of${\displaystyle M}$ for the extended signature${\displaystyle {\sigma }^{\prime }}$ is called theelementary diagram of${\displaystyle M}$. In the next step one adds${\displaystyle \kappa }$ many new constant symbols to the signature and adds to the elementary diagram of${\displaystyle M}$ the sentences${\displaystyle c\ne c^{\prime }}$ for any two distinct new constant symbols${\displaystyle c}$ and${\displaystyle c^{\prime }}$. Using thecompactness theorem, the resulting theory is easily seen to be consistent. Since its models must have cardinality at least${\displaystyle \kappa }$, the downward part of this theorem guarantees the existence of a model${\displaystyle N}$ which has cardinality exactly${\displaystyle \kappa }$. It contains an isomorphic copy of${\displaystyle M}$ as an elementary substructure.^{[5][6]: 100–102}

Although the (classical) Löwenheim–Skolem theorem is tied very closely to first-order logic, variants hold for other logics. For example, every consistent theory insecond-order logic has a model smaller than the firstsupercompact cardinal (assuming one exists). The minimum size at which a (downward) Löwenheim–Skolem–type theorem applies in a logic is known as the Löwenheim number, and can be used to characterize that logic's strength. Moreover, if we go beyond first-order logic, we must give up one of three things: countable compactness, the downward Löwenheim–Skolem Theorem, or the properties of anabstract logic.^[7]: 134

This account is based mainly onDawson (1993). To understand the early history of model theory one must distinguish betweensyntactical consistency (no contradiction can be derived using the deduction rules for first-order logic) andsatisfiability (there is a model). Somewhat surprisingly, even before thecompleteness theorem made the distinction unnecessary, the termconsistent was used sometimes in one sense and sometimes in the other.

The first significant result in what later becamemodel theory wasLöwenheim's theorem inLeopold Löwenheim's publication "Über Möglichkeiten im Relativkalkül" (1915):

For every countable signatureσ, everyσ-sentence that is satisfiable is satisfiable in a countable model.

Löwenheim's paper was actually concerned with the more generalPeirce–Schrödercalculus of relatives (relation algebra with quantifiers).^[1] He also used the now antiquated notations ofErnst Schröder. For a summary of the paper in English and using modern notations seeBrady (2000, chapter 8).

According to the received historical view, Löwenheim's proof was faulty because it implicitly usedKőnig's lemma without proving it, although the lemma was not yet a published result at the time. In arevisionist account,Badesa (2004) considers that Löwenheim's proof was complete.

Skolem (1920) gave a (correct) proof using formulas in what would later be calledSkolem normal form and relying on the axiom of choice:

Every countable theory which is satisfiable in a modelM, is satisfiable in a countable substructure ofM.

Skolem (1922) 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) simplifiedSkolem (1920). Finally,Anatoly Ivanovich Maltsev (Анато́лий Ива́нович Ма́льцев, 1936) proved the Löwenheim–Skolem theorem in its full generality (Maltsev 1936). He cited a note by Skolem, according to which the theorem had been proved byAlfred Tarski in a seminar in 1928. Therefore, the general theorem is sometimes known as theLöwenheim–Skolem–Tarski theorem. But Tarski did not remember his proof, and it remains a mystery how he could do it without thecompactness 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öwenheim-Skolem 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öwenheim-Skolem 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).

The Löwenheim–Skolem theorem is treated in all introductory texts onmodel theory ormathematical logic.

• Löwenheim, Leopold (1915),"Über Möglichkeiten im Relativkalkül"(PDF),Mathematische Annalen,76 (4):447–470,doi:10.1007/BF01458217,ISSN 0025-5831,S2CID 116581304
  • Löwenheim, Leopold (1977), "On possibilities in the calculus of relatives",From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, pp. 228–251,ISBN 0-674-32449-8 (online copy, p. 228, atGoogle Books)
• Maltsev, Anatoly Ivanovich (1936),"Untersuchungen aus dem Gebiete der mathematischen Logik",Matematicheskii Sbornik, Novaya Seriya, 1(43) (3):323–336
• Skolem, Thoralf (1920), "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen",Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse,4:1–36
  • Skolem, Thoralf (1977), "Logico-combinatorical investigations in the satisfiability or provability of mathematical propositions: A simplified proof of a theorem by L. Löwenheim and generalizations of the theorem",From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, pp. 252–263,ISBN 0-674-32449-8 (online copy, p. 252, atGoogle Books)
• Skolem, Thoralf (1922), "Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre",Mathematikerkongressen I Helsingfors den 4–7 Juli 1922, den Femte Skandinaviska Matematikerkongressen, Redogörelse:217–232
  • Skolem, Thoralf (1977), "Some remarks on axiomatized set theory",From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, pp. 290–301,ISBN 0-674-32449-8 (online copy, p. 290, atGoogle Books)
• Skolem, Thoralf (1929), "Über einige Grundlagenfragen der Mathematik",Skrifter Utgitt av Det Norske Videnskaps-Akademi I Oslo, I. Matematisk-naturvidenskabelig Klasse,7:1–49
• Veblen, Oswald (1904), "A System of Axioms for Geometry",Transactions of the American Mathematical Society,5 (3):343–384,doi:10.2307/1986462,ISSN 0002-9947,JSTOR 1986462

• 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 978-0-691-05853-5; A more concise account appears in chapter 9 ofLeila Haaparanta, ed. (2009),The Development of Modern Logic, Oxford University Press,ISBN 978-0-19-513731-6
• Brady, Geraldine (2000),From Peirce to Skolem: A Neglected Chapter in the History of Logic, Elsevier,ISBN 978-0-444-50334-3
• Crossley, J. N.; Ash, C. J.; Brickhill, C. J.; Stillwell, J. C.; Williams, N. H. (1972),What is mathematical logic?, London/Oxford/New York:Oxford University Press, pp. 59–60,ISBN 0-19-888087-1,Zbl 0251.02001
• Dawson, John W. Jr. (1993), "The compactness of First-Order 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 978-0-521-30442-9
• Poizat, Bruno (2000),A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Berlin, New York: Springer,ISBN 978-0-387-98655-5

• Sakharov, A.;Weisstein, E. W."Löwenheim-Skolem Theorem".MathWorld.
• Burris, Stanley N.,Contributions of the Logicians, Part II, From Richard Dedekind to Gerhard Gentzen
• Burris, Stanley N.,Downward Löwenheim–Skolem theorem
• Simpson, Stephen G. (1998),Model Theory

• Mathematical logic
• Metatheorems
• Model theory
• Theorems in the foundations of mathematics

• Articles with short description
• Short description is different from Wikidata
• CS1: long volume value