Skolem's paradox
From Wikipedia, the free encyclopedia
In mathematical logic, specifically set theory, Skolem's paradox is a direct result of the (downward) Löwenheim-Skolem theorem, which states that every model of a sentence of a first-order language has an elementarily equivalent countable submodel.
The paradox is seen in Zermelo-Fraenkel set theory. One of the earliest results, 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 well-known Cantor set. These sets exist in any Zermelo-Fraenkel universe, since their existence follows from the axioms. Using the Löwenheim-Skolem Theorem, we can get a model of set theory which only contains a countable number of objects. However, it must contain the fore-mentioned uncountable sets, which appears to be a contradiction. However, the sets in question are only uncountable in the sense that there does not exist within the model a bijection from the natural numbers onto the sets. It is entirely possible that there is a bijection outside the model.
Contents |
[edit] Is it a paradox?
The "paradox" is viewed by most logicians as something puzzling, but not a paradox in the sense of being a logical contradiction (i.e., a paradox in the same sense as the Banach–Tarski paradox rather than the sense in Russell's paradox). Timothy Bays has argued in detail that there is nothing in the Löwenheim-Skolem theorem, or even "in the vicinity" of the theorem, that is self-contradictory.
However, some philosophers, notably Hilary Putnam and the Oxford philosopher A.W. Moore, have argued that it is in some sense a paradox.
The difficulty lies in the notion of "relativism" that underlies the theorem. Skolem says:
- In the axiomatization "set" does not mean an arbitrarily defined collection; the sets are nothing but objects that are connected with one another through certain relations expressed by the axioms. Hence there is no contradiction at all if a set M of the domain B is nondenumerable in the sense of the axiomatization; for this means merely that within B there occurs no one-to-one mapping of M onto Z0 (Zermelo's number sequence). Nevertheless there exists the possibility of numbering all objects in B, and therefore also the elements of M, by means of the positive integers; of course, such an enumeration too is a collection of certain pairs, but this collection is not a "set" (that is, it does not occur in the domain B).
Moore (1985) has argued that if such relativism is to be intelligible at all, it has to be understood within a framework that casts it as a straightforward error. This, he argues, is Skolem's Paradox.
If Skolem's explanation is true, ideas such as countability and uncountability are inherently relative. Our belief that the power set of the natural numbers, P(w), as uncountable, is correct, but must be understood relative to our own current "viewpoint". From another viewpoint this set may in fact be countable. But then it should be possible to make this relativisation explicit. We can do so this only so far as our discourse about sets is intelligible as about a particular collection of objects to which such claims must be relativized. But this in turn is not possible unless we endorse the error that there is a set containing all the sets we mean to talk about.
"When it is claimed that P(w) is not unconditionally uncountable, we have no way of understanding this except as the demonstrably false claim that it is not uncountable at all."
We cannot view P(w) from two different points of view at once; that would be incoherent. Nor can we view it simply from this point of view, then the supposed relativity is unintelligible. "But if it were possible to view it from an absolute standpoint, then relativism itself would lose its rationale and there could be no objection to saying that P(w) contained all of w's subsets and that it was unconditionally uncountable."
[edit] Quotes
Zermelo at first declared the Skolem paradox a hoax. In 1937 he wrote a small note entitled "Relativism in Set Theory and the So-Called Theorem of Skolem" in which he gives a refutation of "Skolem's paradox", i.e. the fact that Zermelo-Fraenkel set theory --guaranteeing the existence of uncountably many sets-- has a countable model. Other authorities on set theory also found the result astounding.
- 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. (John von Neumann)
- Skolem's work implies "no categorical axiomatisation of set theory (hence geometry, arithmetic [and any other theory with a set-theoretic model]...) seems to exist at all". (John von Neumann)
- Neither have the books yet been closed on the antinomy, nor has agreement on its significance and possible solution yet been reached. (Abraham Fraenkel)
- I believed that it was so clear that axiomatization 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. (Skolem)
[edit] References
- van Dalen, Dirk and Heinz-Dieter Ebbinghaus, "Zermelo and the Skolem Paradox", The Bulletin of Symbolic Logic Volume 6, Number 2, June 2000.
- Moore, A.W. "Set Theory, Skolem's Paradox and the Tractatus", Analysis 1985, 45.
