                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

Downward Löwenheim-Skolem theorem

In 1915 Löwenheim gave a nearly complete proof of the fact that if a firstorder formula φ has a model, then it has a finite or countable model. A tidy, correct version of this was given by Skolem in 1922. We will give the more general version for arbitrary sets of formulas and arbitrary languages.^{1}

DEFINITION 1 Given a language L and a set of variables X let κ = max(ℵ_{0}, |L|, |X|). κ is called the power of the language L.

THEOREM 2 [Downward Löwenheim-Skolem] If Σ is a set of Lformulas which is satisfiable, and the power of the language L is κ, then Σ can be satisfied by a model (S, λ) where |S| ≤ κ.

Proof. Let (S, λ) ⊧ Σ, and let Σ′ be a Skolemization of Σ. Then expand (S, λ) to a model (S′, λ) of Σ′. Let S′′ be the subset of S generated by the constants and the range of λ. S′′ is closed under the operations of S′; so let S′′ be the structure obtained by restricting the functions and relations of S′ to S′′. One sees that (S′′, λ) ⊧ Σ′, and that |S′′| ≤ κ. By reducing back to the original language we have the desired model of Σ.

A remarkable consequence of this result is the existence of small models of axiomatic first-order set theory (provided any model exists).

COROLLARY 3 [Skolem] If ZF (or ZFC or vNBG) set theory has a model, it must have a countable model.

This seems to pose an obvious problem, because in such set theories one can prove that the power set of a set has strictly greater cardinality than the set — but if we have a countable model then all of our sets are countable. This is called Skolem’s paradox.

1Mal’cev is credited for extending first-order languages to arbitrary cardinalities.

Exercises

Problem 1 Given an arbitrary group G show that there is a countable subgroup H such that Th(H) = Th(G).

References

[1] L. Löwenheim, Über Möglichkeiten im Relativkalkül. Math. Ann. 68 (1915), 169–207. [translated in From Frege to Gödel, van Heijenoort, Harvard Univ. Press, 1971.]

[2] Th. Skolem, Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit und Beweisbarkeit mathematischen Sätze nebst einem Theoreme über dichte Mengen. Videnskabsakademiet i Kristiania, Skrifter I, No. 4, 1919, 1–36. Also in “Selected Works in Logic by Th. Skolem”, ed. by Jens Erik Fenstak, Scand. Univ. Books, Universitetsforlaget, Oslo, 1970, pp. 103–136. [The first section is translated in: From Frege to Gödel, van Heijenoort, Harvard Univ. Press, 1971, 252–263.]

[3] Th. Skolem, Einige Bemerkung zur axiomatischen Begrundung der Mengenlehre. Proc. 5^{th} Scand. Math. Congr. Helsinki, 1922, 217–232. [translation in From Frege to Gödel, van Heijenoort, Harvard Univ. Press, 1971.]