Skolem's paradox

Skolem's paradox is the mathematical fact that every countable axiomatisation of set theory in first-order logic, if consistent, has a model that is countable, even if it is possible to prove, from those same axioms, the existence of sets that are not countable. The existence of these structures is a consequence of 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 not an actual antinomy like Russell's paradox, the result has been called a paradox, and was described as a "paradoxical state of affairs" by Skolem (1922: p. 295). Skolem's work was harshly received by Ernst Zermelo, who argued against the limitations of first-order logic, but quickly came to be accepted by the mathematical community. 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 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 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 finite positive integers?" (Skolem 1922, p. 295, translation by Bauer-Mengelberg)

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 is it possible to recognize that a particular set "X" 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 "X" and the natural numbers in that model.

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. (Kunen 1980 p. 141; Enderton 2001 p. 152; Burgess 1977 p. 406).

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" - it would have exactly one model, consisting of all sets. Skolem's result showed this is not possible. (Godel's incompleteness theorem would later show that, even if the requirement for being categorical is replaced by the weaker requirement of completeness, it is not possible to find a recursively enumerable set of axioms for set theory.)

Zermelo at first considered the Skolem paradox a hoax (van Dalen and Ebbinghaus, 2000, p. 137, 154 ff.), and spoke against it. Skolem's result applies only to what is now called first-order logic, but Zermelo argued against the finitary metamathematics that underly 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 axiomatization 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 formalization of infinitary logic (van Dalen and Ebbinghaus, note 11).

Von Neumann (1925) presented a novel axiomatization 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 axiomatization of set theory, or any other theory with an infinite model.

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 "hardly even a paradox".

Putnam's argument

Interest in Skolem's paradox was renewed by the paper "Models and Reality" published by Hilary Putnam in 1980. Putnam claimed that although Skolem's paradox is not an antinomy in mathematics, it leads to an antinomy in the philosophy of language that discredits realism. Putnam argues that it is possible to extend Skolem's paradox from set theory to language itself.

References

* Barwise, Jon (1977), "An introduction to first-order logic", in Citation | editor1-last=Barwise | editor1-first=Jon | title=Handbook of Mathematical Logic | publisher=North-Holland | location=Amsterdam | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-86388-1 | year=1982
* Van Dalen, Dirk and Heinz-Dieter Ebbinghaus, "Zermelo and the Skolem Paradox", "The Bulletin of Symbolic Logic" Volume 6, Number 2, June 2000.
*springer|id=S/s085750|first=A.G.|last= Dragalin
*Citation | last1=Kanamori | first1=Akihiro | title=Zermelo and set theory | url=http://www.math.ucla.edu/~asl/bsl/1004-toc.htm | id=MathSciNet | id = 2136635 | year=2004 | journal=The Bulletin of Symbolic Logic | issn=1079-8986 | volume=10 | issue=4 | pages=487–553
* Kleene, Stephen Cole (1967). "Mathematical Logic".
*Citation | last1=Kunen | first1=Kenneth | author1-link=Kenneth Kunen | title= | publisher=North-Holland | location=Amsterdam | isbn=978-0-444-85401-8 | year=1980
*
* Moore, A.W. "Set Theory, Skolem's Paradox and the Tractatus", "Analysis" 1985, 45.
* Hilary Putnam, "Models and Reality", The Journal of Symbolic Logic, Vol. 45, No. 3 (Sep., 1980), pp. 464-482
* Skolem, Thoralf (1922). "Axiomatized set theory". Reprinted in "From Frege to Gödel", van Heijenoort, 1967, in English translation by Stefan Bauer-Mengelberg, pp. 291–301.

External links

* [http://www.nd.edu/~tbays/papers/pthesis.pdf Bays's Ph.D. thesis on the paradox]
* [http://boole.stanford.edu/skolem Vaughan Pratt's celebration of his ancestor Skolem's 120th birthday]
* [http://uk.geocities.com/frege@btinternet.com/cantor/skolem_moore.htm Extract from Moore's discussion of the paradox]