In set theory, Cantor's paradox describes what happens under naive set theory when one defines a set that contains all sets. Let's call this set , since this set contains all sets, it would need to contain , the power set of itself, and also , the power set of the power set of . This goes on for infinity: there is always the power set of itself that it doesn't contain. Suppose such infinite set is to exist and that it contain all these power sets, it would have to be the power set of itself. Then by Cantor's theorem, its cardinality, , would have to be bigger than itself, admitting that and thus it is a paradox.
For that reason, in ZF, the universe of sets is not closed (the set of all sets does not exist). Other axiomatic set theories resolve this by declaring that such collection is not a set but a proper class; In von Neumann–Bernays–Gödel set theory it follows from this and the axiom of limitation of size that this proper class must be in bijection with the class of all sets. Thus, not only are there infinitely many infinities, but this infinity is larger than any of the infinities it enumerates.
This paradox is named after Georg Cantor, who is often credited with first identifying it in 1899 (or between 1895 and 1897). Like a number of "paradoxes" it is not actually contradictory but merely indicative of a mistaken intuition, in this case about the nature of infinity and the notion of a set. Put another way, it is paradoxical within the confines of naïve set theory and therefore demonstrates that a careless axiomatization of this theory is inconsistent.
Statements and proofs
In order to state the paradox it is necessary to understand that the cardinal numbers admit an ordering, so that one can speak about one being greater or less than another. Then Cantor's paradox is:
- Theorem: There is no greatest cardinal number.
- Proof: Assume the contrary, and let C be the largest cardinal number. Then (in the von Neumann formulation of cardinality) C is a set and therefore has a power set 2C which, by Cantor's theorem, has cardinality strictly larger than that of C. Demonstrating a cardinality (namely that of 2C) larger than C, which was assumed to be the greatest cardinal number, falsifies the definition of C. This contradiction establishes that such a cardinal cannot exist.
Another consequence of Cantor's theorem is that the cardinal numbers constitute a proper class. That is, they cannot all be collected together as elements of a single set. Here is a somewhat more general result.
- Theorem: If S is any set then S cannot contain elements of all cardinalities. In fact, there is a strict upper bound on the cardinalities of the elements of S.
- Proof: Let S be a set, and let T be the union of the elements of S. Then every element of S is a subset of T, and hence is of cardinality less than or equal to the cardinality of T. Cantor's theorem then implies that every element of S is of cardinality strictly less than the cardinality of 2T.
Discussion and consequences
Since the cardinal numbers are well-ordered by indexing with the ordinal numbers (see Cardinal number, formal definition), this also establishes that there is no greatest ordinal number; conversely, the latter statement implies Cantor's paradox. By applying this indexing to the Burali-Forti paradox we obtain another proof that the cardinal numbers are a proper class rather than a set, and (at least in ZFC or in von Neumann–Bernays–Gödel set theory) it follows from this that there is a bijection between the class of cardinals and the class of all sets. Since every set is a subset of this latter class, and every cardinality is the cardinality of a set (by definition!) this intuitively means that the "cardinality" of the collection of cardinals is greater than the cardinality of any set: it is more infinite than any true infinity. This is the paradoxical nature of Cantor's "paradox".
While Cantor is usually credited with first identifying this property of cardinal sets, some mathematicians award this distinction to Bertrand Russell, who defined a similar theorem in 1899 or 1901.
- Anellis, I.H. (1991). Drucker, Thomas, ed. "The first Russell paradox," Perspectives on the History of Mathematical Logic. Cambridge, Mass.: Birkäuser Boston. pp. 33–46.
- Moore, G.H. and Garciadiego, A. (1981). "Burali-Forti's paradox: a reappraisal of its origins". Historia Math 8 (3): 319–350. doi:10.1016/0315-0860(81)90070-7.
- An Historical Account of Set-Theoretic Antinomies Caused by the Axiom of Abstraction: report by Justin T. Miller, Department of Mathematics, University of Arizona.