Löwenheim-Skolem theorem the result that for any set of sentences of standard predicate logic, if there is any interpretation in which they are all true, there there is also an interpretation whose domain consists of natural numbers and in which they are all true. Leopold Löwenheim proved in 1915 that for finite sets of sentences of standard predicate logic, if there is any interpretation in which they are true, there is also an interpretation that makes them true and where the domain is a subset of the domain of the first interpretation, and the new domain can be mapped one-to-one onto a set of natural numbers. Löwenheim’s proof contained some gaps and made essential but implicit use of the axiom of choice, a principle of set theory whose truth was, and is, a matter of debate. In fact, the Löwenheim-Skolem theorem is equivalent to the axiom of choice. Thoralf Skolem, in 1920, gave a more detailed proof that made explicit the appeal to the axiom of choice and that extended the scope of the theorem to include infinite sets of sentences. In 1922 he gave an essentially different proof that did not depend on the axiom of choice and in which the domain consisted of natural numbers rather than being of the same size as a set of natural numbers. In most contemporary texts, Skolem’s result is proved by methods later devised by Gödel, Herbrand, or Henkin for proving other results. If the language does not include an identity predicate, then Skolem’s result is that the second domain consists of the entire set of natural numbers; if the language includes an identity predicate, then the second domain may be a proper subset of the natural numbers. (See van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic 1879–1931, 1967, for translations of the original papers.) The original results were of interest because they showed that in many cases unexpected interpretations with smaller infinite domains than those of the initially given interpretation could be constructed. It was later shown – and this is the Upward Löwenheim-Skolem theorem – that interpretations with larger domains could also be constructed that rendered true the same set of sentences. Hence the theorem as stated initially is sometimes referred to as the Downward Löwenheim-Skolem theorem.
The theorem was surprising because it was believed that certain sets of axioms characterized domains, such as the continuum of real numbers, that were larger than the set of natural numbers. This surprise is called Skolem’s paradox, but it is to be emphasized that this is a philosophical puzzle rather than a formal contradiction. Two main lines of response to the paradox developed early. The realist, who believes that the continuum exists independently of our knowledge or description of it, takes the theorem to show either that the full truth about the structure of the continuum is ineffable or at least that means other than standard first-order predicate logic are required. The constructivist, who believes that the continuum is in some sense our creation, takes the theorem to show that size comparisons among infinite sets is not an absolute matter, but relative to the particular descriptions given. Both positions have received various more sophisticated formulations that differ in details, but they remain the two main lines of development.
See also SET THEORY. R.E.G.