Cantor's paradox

This paradox is named for 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 are totally ordered, 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.

This fact is a direct consequence of Cantor's theorem on the cardinality of the power set of a set.

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 2^C which, by Cantor's theorem, has cardinality strictly larger than C. Demonstrating a cardinality (namely that of 2^C) 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 2^T.