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 countable first-order language has an elementarily equivalent countable submodel.
The paradox is an apparent inconsistency in Zermelo-Fraenkel (ZF) set theory. One of the earliest results of set theory was Cantor's proof, in 1874, of the existence of uncountable sets, such as the powerset of the natural numbers, the set of real numbers, and the Cantor set. These sets exist in any model of ZF set theory, since their existence follows from the axioms. Using the Löwenheim-Skolem Theorem, we can get a model of ZF set theory which contains only a countable number of objects. However, it must contain the aforementioned uncountable sets. This appears to be a contradiction, since the uncountable sets are subsets of the (countable) domain of the model. The sets in question are uncountable in the sense that, within the model, there are no bijections from the natural numbers to any of the uncountable sets. It is entirely possible that bijections exist in another model. Indeed, models with such bijections can be constructed using the techniques of forcing.
Contents |
[edit] Is it a paradox?
The "paradox" is viewed by most logicians as something intriguing, 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. Peter Suber on the contrary argues there are a number of contradictions that result from the skolem paradox and that mathematicians claim skolems paradox is not a contradiction but they dont know how to prove it is not a contradiction
Most mathematicians agree that the Skolem paradox creates no contradiction. But that does not mean they agree on how to resolve it. [The Löwenheim-Skolem Theorem, http://www.earlham.edu/~peters/courses/logsys/low-skol.htm#amb3]
In agreement with Suber B.Bunch in "Mathematical fallacies and paradoxes” Dover 1982" notes p.167
“no one has any idea of how to re-construct axiomatic set theory so that this paradox does not occur”
However, some philosophers, notably Hilary Putnam and the Oxford philosopher A.W. Moore, have argued that it is in some sense a paradox.
Peter Suber argues that the skolem paradox is a paradox in the ancient sense [ibid]
Insofar as this is a paradox it is called Skolem's paradox. It is at least a paradox in the ancient sense: an astonishing and implausible result. Is it a paradox in the modern sense, making contradiction apparently unavoidable?
Now Suber shows that a reading of LST gives us a serious contradiction
One reading of LST holds that it proves that the cardinality of the real numbers is the same as the cardinality of the rationals, namely, countable. (The two kinds of number could still differ in other ways, just as the naturals and rationals do despite their equal cardinality.) On this reading, the Skolem paradox would create a serious contradiction, for we have Cantor's proof, whose premises and reasoning are at least as strong as those for LST, that the set of reals has a greater cardinality than the set of rationals. [ibid]
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).
But Skolem admitted that his relativism destroyed the notion that set theory was a foundation of mathematics
"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]"The Bulletin of symbolic logic" Vol.6, no 2. June 2000, pp. 147 http://www.math.ucla.edu/~asl/bsl/0602/0602-001.ps
Even John von Neumann noted that Skolems relativism was one more reason to upset set theory and destroy it
"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]"The Bulletin of symbolic logic" Vol.6, no 2. June 2000, pp. 148 http://www.math.ucla.edu/~asl/bsl/0602/0602-001.ps.
Abraham Fraenkel noted that Skolems relativism did not satisfactoraly disprove the antinomy and that there was no agreement as to his relativist solution
"Neither have the books yet been closed on the antinomy, nor has agreement on its significance and possible solution yet been reached." – ([[Abraham Fraenkel] in "Einleitung in die Mengenlehre" 3rd ed p. 333, 1928, quoted in "The Bulletin of symbolic logic"" Vol.6, no 2. June 2000, pp. 147 http://www.math.ucla.edu/~asl/bsl/0602/0602-001.ps
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.
Peter Suber points out the problem with Skolems relativism
This means that there simply are no sets whose cardinality is absolutely uncountable. For many, this view guts set theory, arithmetic, and analysis. It is also clearly incompatible with mathematical Platonism which holds that the real numbers exist, and are really uncountable, independently of what can be proved about them. [ibid]
Suber goes on to pount out contradictions due to Skolems paradox in non-relativistic accounts
If we want to insist on the non-relativity of our set theoretic notions, and if we hold that our formal systems to date fail fully to capture the secret of the real numbers, then we must choose between the unattractive options (1) that the theory of real numbers is inconsistent, hence has no model, and (2) that the secret of the real numbers cannot be captured by any first-order formal system, i.e. that every attempt will fail either by having no model or by "incurring" a merely countable model. LST puts us to the choice between inconsistency and non-categoricity. If we discard the first of these, then we are left with a view that implies that our notions of uncountable infinities, including the continuum, cannot be fully formalized. As John Myhill put it, in LST we have proved an insurmountable limitation of formalization itself. [ibid]
There are a number of contradictions that result from the skolem paradox as pointed out by suber
If all the models of a system are isomorphic with one another, we call the system categorical. LST proves that systems with uncountable models also have countable models; this means that the domains of the two models have different cardinalities, which is enough to prevent isomorphism. Hence, consistent first-order systems, including systems of arithmetic, are non-categorical. We might have thought that, even if a vast system of uninterpreted marks on paper were susceptible of two or more coherent interpretations, or even two or more models, at least they would all be "equivalent" or "isomorphic" to each other, in effect using different terms for the same things. But non-categoricity upsets this expectation. Consistent systems will always have non-isomorphic or qualitatively different models. LST proves in a very particular way that no first-order formal system of any size can specify the reals uniquely. It proves that no description of the real numbers (in a first-order theory) is categorical. Very Very Serious Incurable Ambiguity: Upward and Downward LST If the intended model of a first-order theory has a cardinality of 1, then we have to put up with its "shadow" model with a cardinality of 0. But it could be worse. These are only two cardinalities. The range of the ambiguity from this point of view is narrow. Let us say that degree of non-categoricity is 2, since there are only 2 different cardinalities involved. But it is worse. A variation of LST called the "downward" LST proves that if a first-order theory has a model of any transfinite cardinality, x, then it also has a model of every transfinite cardinal y, when y > x. Since there are infinitely many infinite cardinalities, this means there are first-order theories with arbitrarily many LST shadow models. The degree of non-categoricity can be any countable number. There is one more blow. A variation of LST called the "upward" LST proves that if a first-order theory has a model of any infinite cardinality, then it has models of any arbitrary infinite cardinality, hence every infinite cardinality. The degree of non-categoricity can be any infinite number. A variation of upward LST has been proved for first-order theories with identity: if such a theory has a "normal" model of any infinite cardinality, then it has normal models of any, hence every, infinite cardinality. [ibid]
Suber notes that mathematician claim skolems paradox is not a contradiction but they dont know how to prove it is not a contradiction
Most mathematicians agree that the Skolem paradox creates no contradiction. But that does not mean they agree on how to resolve it. [ibid]
[edit] Quotations
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 (what he considered to be) 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. His response relied, however, on his understanding of the foundations of set theory as essentially second-order (in particular, on interpreting his axiom of separation as guaranteeing not merely the existence of first-order definable subsets, but also arbitrary unions of such). Skolem's result applies only to the first-order interpretation of Zermelo-Fraenkel set theory, but Zermelo considered this first-order interpretation to be flawed and fraught with "finitary prejudice". Other authorities on set theory were more sympathetic to the first-order interpretation, but still found Skolem's 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]"The Bulletin of symbolic logic" Vol.6, no 2. June 2000, pp. 148 http://www.math.ucla.edu/~asl/bsl/0602/0602-001.ps. ])[citation needed]
- "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)[citation needed]
- "Neither have the books yet been closed on the antinomy, nor has agreement on its significance and possible solution yet been reached." – ([[Abraham Fraenkel] in "Einleitung in die Mengenlehre" 3rd ed p. 333, 1928, quoted in "The Bulletin of symbolic logic"" Vol.6, no 2. June 2000, pp. 147 http://www.math.ucla.edu/~asl/bsl/0602/0602-001.ps ])[citation needed]
- "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]"The Bulletin of symbolic logic" Vol.6, no 2. June 2000, pp. 147 http://www.math.ucla.edu/~asl/bsl/0602/0602-001.ps.])[citation needed]
[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.
