Cantor's Paradox - Statements and Proofs

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.

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 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 2lTl.

Read more about this topic:  Cantor's Paradox

Famous quotes containing the words proofs and/or statements:

    Would you convey my compliments to the purist who reads your proofs and tell him or her that I write in a sort of broken-down patois which is something like the way a Swiss waiter talks, and that when I split an infinitive, God damn it, I split it so it will stay split, and when I interrupt the velvety smoothness of my more or less literate syntax with a few sudden words of bar- room vernacular, that is done with the eyes wide open and the mind relaxed but attentive.
    Raymond Chandler (1888–1959)

    We assume that politicians are without honor. We read their statements trying to crack the code. The scandals of their politics: not so much that men in high places lie, only that they do so with such indifference, so endlessly, still expecting to be believed. We are accustomed to the contempt inherent in the political lie.
    Adrienne Rich (b. 1929)