# Löwenheim–Skolem theorem

# Löwenheim–Skolem theorem

In mathematical logic, the **Löwenheim–Skolem theorem** is a theorem named after Leopold Löwenheim and Thoralf Skolem.

The precise formulation is given below. It implies that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ.

As a consequence, first-order theories are unable to control the cardinality of their infinite models, and that no first-order theory with an infinite model can have a unique 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 first-order logic. In general, the Löwenheim–Skolem theorem does not hold in stronger logics such as second-order logic.

Theorem

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 such that

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**.^{[1]} 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**.^{[2]}

Discussion

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

Concepts

Signatures

`Asignatureconsists of a set of function symbols`

*S*func, a set of relation symbols*S*rel, and a functionrepresenting thearityof 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-order 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.

Structures / Models

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 *n*-ary function symbol *f* is a function from *M**n* to *M*. Similarly, an interpretation of a relation symbol *R* is an *n*-ary 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 first-order sentences as the original structure (its elementary extension).

Consequences

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.

A theory is called **categorical** if it has only one model, up to isomorphism. This term was introduced by Veblen (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 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 first-order and non-first-order properties was not yet understood. One such consequence is the existence of uncountable models of true arithmetic, which satisfy every first-order induction axiom but have non-inductive subsets.

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 first-order 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 first-order.
For example, in the theory of the real numbers, the completeness of a linear order used to characterize **R** as a complete ordered field, is a non-first-order property.

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 first-order-formulatheaxiom of choiceimplies 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 formulasto such functions`

`The family of functionsgives rise to apreclosure operatoron thepower setof`

`for`

`Iteratingcountably many times results in aclosure operatorTaking an arbitrary subsetsuch that, and having definedone can see that alsois an elementary substructure ofby theTarski–Vaught test.`

`The trick used in this proof is essentially due to Skolem, who introduced function symbols for theSkolem functionsinto the language. One could also define theaspartial functionssuch thatis defined if and only ifThe only important point is thatis a preclosure operator such thatcontains a solution for every formula with parameters inwhich has a solution inand 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 first-order 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 paper was actually concerned with the more general Peirce–Schröder *calculus of relatives* (relation algebra with quantifiers).^{[1]} He also used the now antiquated notations of Ernst Schröder. For a summary of the paper in English and using modern notations see Brady (2000, chapter 8).

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

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 (Maltsev 1936). 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ö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).

## References

*A Functorial Model Theory: Newer Applications to Algebraic Topology, Descriptive Sets, and Computing Categories Topos*(Toronto: Apple Academic Press, 2014), pp.160–161.

*The Logic of Infinity*(Cambridge: Cambridge University Press, 2014), p. 372.