Skolem's paradox
In mathematical logic and philosophy, Skolem's paradox is a seeming contradiction that arises from the downward Löwenheim–Skolem theorem. Thoralf Skolem (1922) was the first to discuss the seemingly contradictory aspects of the theorem, and to discover the relativity of set-theoretic notions now known as non-absoluteness. Although it is not an actual antinomy like Russell's paradox, the result is typically called a paradox, and was described as a "paradoxical state of affairs" by Skolem (1922: p. 295).
Skolem's paradox is that every countable axiomatisation of set theory in first-order logic, if it is consistent, has a model that is countable. This appears contradictory because it is possible to prove, from those same axioms, a sentence that intuitively says (or that precisely says in the standard model of the theory) that there exist sets that are not countable. Thus the seeming contradiction is that a model that is itself countable, and which therefore contains only countable sets, satisfies the first order sentence that intuitively states "there are uncountable sets".
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 set theory, published by Georg Cantor in 1874, was the existence of uncountable sets, such as the powerset of the natural numbers, the set of real numbers, and the Cantor set. An infinite set X is countable if there is a function that gives a one-to-one correspondence between X and the natural numbers, and is uncountable if there is no such correspondence function. When Zermelo proposed his axioms for set theory in 1908, he proved Cantor's theorem from them to demonstrate their strength.
Löwenheim (1915) and Skolem (1920, 1923) proved the Löwenheim–Skolem theorem. The downward form of this theorem shows that if a countable first-order axiomatisation is satisfied by any infinite structure, then the same axioms are satisfied by some countable structure. In particular, this implies that if the first order versions of Zermelo's axioms of set theory are satisfiable, they are satisfiable in some countable model. The same is true of any consistent first order axiomatisation of set theory.
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.
From an interpretation of the model into our conventional notions of these sets, this means that although u maps to an uncountable set, there are many elements in our intuitive notion of u that don't have a corresponding element in the model. The model, however, is consistent, because the absence of these elements cannot be observed through first-order logic. With u as the reals, these missing elements would correspond to undefinable numbers.
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 is 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 transitive model as absolute. From their point of view, Skolem's paradox simply shows that countability is not an absolute property in first order logic. (Kunen 1980 p. 141; Enderton 2001 p. 152; Burgess 1977 p. 406).
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 categorical, meaning that the axioms would have exactly one model, consisting of all sets. Skolem's result showed this is not possible, creating doubts about the use of set theory as a foundation of mathematics. It took some time for the theory of first-order logic to be developed enough for mathematicians to understand the cause of Skolem's result; no resolution of the paradox was widely accepted during the 1920s. Fraenkel (1928) still described the result as an antinomy:
- "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, von Neumann presented a novel axiomatisation of set theory, which developed into NBG set theory. Very much aware of Skolem's 1922 paper, von Neumann investigated countable models of his axioms in detail. In his concluding remarks, Von Neumann comments that there is no categorical axiomatisation of set theory, or any other theory with an infinite model. Speaking of the impact of Skolem's paradox, he wrote,
- "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. Kleene (1967, p. 324) describes the result as "not a paradox in the sense of outright contradiction, but rather a kind of anomaly". After surveying Skolem's argument that the result is not contradictory, Kleene concludes "there is no absolute notion of countability." Hunter (1971, p. 208) describes the contradiction as "hardly even a paradox". Fraenkel et al. (1973, p. 304) explain that contemporary mathematicians are no more bothered by the lack of categoricity of first-order theories than they are bothered by the conclusion of Gödel's incompleteness theorem that no consistent, effective, and sufficiently strong set of first-order axioms is complete.
Countable models of ZF have become common tools in the study of set theory. Forcing, for example, is often explained in terms of countable models. The fact that these countable models of ZF still satisfy the theorem that there are uncountable sets is not considered a pathology; van Heijenoort (1967) describes it as "a novel and unexpected feature of formal systems." (van Heijenoort 1967, p. 290)
References
- Barwise, Jon (1982) [1977]. "An introduction to first-order logic". In Barwise, Jon (ed.). Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland. 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: Oxford University Press. ISBN 0-19-888087-1. Zbl 0251.02001.
- van Dalen, Dirk; Ebbinghaus, Heinz-Dieter (Jun 2000). "Zermelo and the Skolem Paradox". The Bulletin of Symbolic Logic. 6 (2): 145–161. CiteSeerX 10.1.1.137.3354. doi:10.2307/421203. JSTOR 421203.
- 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. doi:10.2307/2266967. JSTOR 2266967.
- Kanamori, Akihiro (2004), "Zermelo and set theory", The Bulletin of Symbolic Logic, 10 (4): 487–553, doi:10.2178/bsl/1102083759, ISSN 1079-8986, JSTOR 3216738, MR 2136635
- Stephen Cole Kleene, (1952, 1971 with emendations, 1991 10th printing), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam NY. 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.
- Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. Amsterdam: North-Holland. ISBN 978-0-444-85401-8.
- Löwenheim, Leopold (1915). "Über Möglichkeiten im Relativkalkül" (PDF). Mathematische Annalen. 76 (4): 447–470. doi:10.1007/BF01458217. ISSN 0025-5831.
- Moore, A.W. (1985). "Set Theory, Skolem's Paradox and the Tractatus". Analysis. 45 (1): 13–20. doi:10.2307/3327397. JSTOR 3327397.
- Putnam, Hilary (Sep 1980). "Models and Reality" (PDF). The Journal of Symbolic Logic. 45 (3): 464–482. doi:10.2307/2273415. JSTOR 2273415.
- Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (3rd ed.). New York: Springer Science+Business Media. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.
- Skolem, Thoralf (1923). "Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre". Matematikerkongressen i Helsingfors den 4-7 juli 1922; den femte Skandinaviska matematikerkongressen redogörelse. The fifth Scandinavian Mathematical Congress. Helsinki. pp. 217–232. 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.