Skolem's paradox
![]() | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (December 2020) |
In
Skolem's paradox is that every
A mathematical explanation of the paradox, showing that it is not a contradiction in mathematics, was given by Skolem (1922). Skolem's work was harshly received by Ernst Zermelo, who argued against the limitations of first-order logic, but the result quickly came to be accepted by the mathematical community.
The philosophical implications of Skolem's paradox have received much study. One line of inquiry questions whether it is accurate to claim that any first-order sentence actually states "there are uncountable sets". This line of thought can be extended to question whether any set is uncountable in an absolute sense. More recently, the paper "Models and Reality" by Hilary Putnam, and responses to it, led to renewed interest in the philosophical aspects of Skolem's result.
Background
One of the earliest results in
Löwenheim (1915) and Skolem (1920, 1923) proved the
The paradoxical result and its mathematical implications
Skolem (1922) pointed out the seeming contradiction between the Löwenheim–Skolem theorem on the one hand, which implies that there is a countable model of Zermelo's axioms, and Cantor's theorem on the other hand, which states that uncountable sets exist, and which is provable from Zermelo's axioms. "So far as I know," Skolem writes, "no one has called attention to this peculiar and apparently paradoxical state of affairs. By virtue of the axioms we can prove the existence of higher cardinalities... How can it be, then, that the entire domain B [a countable model of Zermelo's axioms] can already be enumerated by means of the finite positive integers?" (Skolem 1922, p. 295, translation by Bauer-Mengelberg).
More specifically, let B be a countable model of Zermelo's axioms. Then there is some set u in B such that B satisfies the first-order formula saying that u is uncountable. For example, u could be taken as the set of real numbers in B. Now, because B is countable, there are only countably many elements c such that c ∈ u according to B, because there are only countably many elements c in B to begin with. Thus it appears that u should be countable. This is Skolem's paradox.
Skolem went on to explain why there was no contradiction. In the context of a specific model of set theory, the term "set" does not refer to an arbitrary set, but only to a set that is actually included in the model. The definition of countability requires that a certain one-to-one correspondence, which is itself a set, must exist. Thus it is possible to recognise that a particular set u is countable, but not countable in a particular model of set theory, because there is no set in the model that gives a one-to-one correspondence between u and the natural numbers in that model.[1]
In
Skolem used the term "relative" to describe this state of affairs, where the same set is included in two models of set theory, is countable in one model and not countable in the other model. He described this as the "most important" result in his paper. Contemporary set theorists describe concepts that do not depend on the choice of a
Skolem described his work as a critique of (first-order) set theory, intended to illustrate its weakness as a foundational system:
- "I believed that it was so clear that axiomatisation in terms of sets was not a satisfactory ultimate foundation of mathematics that mathematicians would, for the most part, not be very much concerned with it. But in recent times I have seen to my surprise that so many mathematicians think that these axioms of set theory provide the ideal foundation for mathematics; therefore it seemed to me that the time had come for a critique." (Ebbinghaus and van Dalen, 2000, p. 147)
Reception by the mathematical community
A central goal of early research into set theory was to find a first-order axiomatisation for set theory which was
- "Neither have the books yet been closed on the antinomy, nor has agreement on its significance and possible solution yet been reached." (van Dalen and Ebbinghaus, 2000, p. 147).
In 1925,
- "At present we can do no more than note that we have one more reason here to entertain reservations about set theory and that for the time being no way of rehabilitating this theory is known." (Ebbinghaus and van Dalen, 2000, p. 148)
Zermelo at first considered the Skolem paradox a hoax (van Dalen and Ebbinghaus, 2000, p. 148 ff.) and spoke against it starting in 1929. Skolem's result applies only to what is now called first-order logic, but Zermelo argued against the finitary metamathematics that underlie first-order logic (Kanamori 2004, p. 519 ff.). Zermelo argued that his axioms should instead be studied in second-order logic, a setting in which Skolem's result does not apply. Zermelo published a second-order axiomatisation in 1930 and proved several categoricity results in that context. Zermelo's further work on the foundations of set theory after Skolem's paper led to his discovery of the cumulative hierarchy and formalisation of infinitary logic (van Dalen and Ebbinghaus, 2000, note 11).
Fraenkel et al. (1973, pp. 303–304) explain why Skolem's result was so surprising to set theorists in the 1920s. Gödel's completeness theorem and the compactness theorem were not proved until 1929. These theorems illuminated the way that first-order logic behaves and established its finitary nature, although Gödel's original proof of the completeness theorem was complicated. Leon Henkin's alternative proof of the completeness theorem, which is now a standard technique for constructing countable models of a consistent first-order theory, was not presented until 1947. Thus, in 1922, the particular properties of first-order logic that permit Skolem's paradox to go through were not yet understood. It is now known that Skolem's paradox is unique to first-order logic; if set theory is studied using higher-order logic with full semantics, then it does not have any countable models, due to the semantics being used.
Current mathematical opinion
Current mathematical logicians do not view Skolem's paradox as any sort of fatal flaw in set theory.
Countable models of ZF have become common tools in the study of set theory.
See also
References
- ^ R. L. Goodstein, The Significance of the Incompleteness Theorems (1963), p.209. The British Journal for the Philosophy of Science, Vol. 14. Accessed 8 March 2023.
- ^ Timothy Bays, The Mathematics of Skolem's Paradox (PDF)
- ISBN 978-0-444-86388-1.
- Bays, Timothy (2000). Reflections on Skolem's Paradox (PDF) (Ph.D. thesis). UCLA Philosophy Department.
- Crossley, J.N.; Ash, C.J.; Brickhill, C.J.; Stillwell, J.C.; Williams, N.H. (1972). What is mathematical logic?. London-Oxford-New York: Zbl 0251.02001.
- S2CID 8530810.
- Dragalin, A.G. (2001) [1994], "Skolem's paradox", Encyclopedia of Mathematics, EMS Press
- Enderton, Herbert B. (2001). A Mathematical Introduction to Logic (2nd ed.). Elsevier. ISBN 978-0-08-049646-7.
- Fraenkel, Abraham; Bar-Hillel, Yehoshua; Levy, Azriel; van Dalen, Dirk (1973). Foundations of Set Theory. North-Holland.
- Henkin, L. (1950). "Completeness in the theory of types". The Journal of Symbolic Logic. 15 (2): 81–91. S2CID 36309665.
- S2CID 231795240
- ISBN 0-444-10088-1. cf pages 420-432: § 75. Axiom systems, Skolem's paradox, the natural number sequence.
- Stephen Cole Kleene, (1967). Mathematical Logic.
- ISBN 978-0-444-85401-8.
- S2CID 116581304.
- Moore, A.W. (1985). "Set Theory, Skolem's Paradox and the Tractatus". Analysis. 45 (1): 13–20. JSTOR 3327397.
- Putnam, Hilary (Sep 1980). "Models and Reality" (PDF). The Journal of Symbolic Logic. 45 (3): 464–482. S2CID 18831300.
- ISBN 978-1-4419-1220-6.
- OCLC 23550016. English translation: Skolem, Thoralf(1961) [1922]. "Some remarks on axiomatized set theory". In van Heijenoort (ed.). From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Translated by Stefan Bauer-Mengelberg. pp. 290–301.