Previous: Calculus of classes: II

Next: First-order arithmetic

Up: Supplementary Text Topics


Downward Löwenheim-Skolem theorem

In 1915 Löwenheim gave a nearly complete proof of the fact that if a first-order 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. gif

PROOF. Let , and let be a Skolemization of . Then expand to a model of . Let be the subset of S generated by the constants and the range of . is closed under the operations of ; so let be the structure obtained by restricting the functions and relations of to . One sees that , and that . 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).

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.

EXERCISES


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. Scand. Math. Congr. Helsinki, 1922, 217-232. [translation in From Frege to Gödel, van Heijenoort, Harvard Univ. Press, 1971.]


Previous: Calculus of classes: II

Next: First-order arithmetic

Up: Supplementary Text Topics


Fri Jan 31 11:57:38 EST 1997
© Stanley Burris