Löwenheim–Skolem theorem

As a consequence, first-order theories are unable to control the cardinality of their infinite models.

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 The theorem is often divided into two parts corresponding to the two cases above.

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.

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 Mn to M. Similarly, an interpretation of a relation symbol R is an n-ary relation on M, i.e. a subset of Mn.

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).

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.

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.

[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 of true arithmetic, which satisfy every first-order induction axiom but have non-inductive subsets.

[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.

This counterintuitive situation came to be known as Skolem's paradox; it shows that the notion of countability is not absolute.

, either or Applying the axiom of choice again we get a function from the first-order formulas

and that First, one extends the signature by adding a new constant symbol for every element of

many new constant symbols to the signature and adds to the elementary diagram of

Using the compactness theorem, the resulting theory is easily seen to be consistent.

, the downward part of this theorem guarantees the existence of a model

For example, every consistent theory in second-order logic has a model smaller than the first supercompact cardinal (assuming one exists).

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.

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.

He cited a note by Skolem, according to which the theorem had been proved by Alfred Tarski in a seminar in 1928.

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: The Löwenheim–Skolem theorem is treated in all introductory texts on model theory or mathematical logic.