Cantor's paradox

<h2 id="statements-and-proofs">Statements and proofs</h2>
In order to state the paradox it is necessary to understand that the cardinal numbers are <a href="/facts/Total_order/xnTtmuYJ">totally ordered</a>, 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 <a href="/facts/Cantor%27s_theorem/kGNIBpjL">Cantor's theorem</a> on the cardinality of the <a href="/facts/Power_set/FVuf8PDD">power set</a> of a set.

Proof: Assume the contrary, and let C be the largest cardinal number. Then (in the <a href="/facts/John_von_Neumann/aUk6urof">von Neumann</a> formulation of cardinality) C is a set and therefore has a power set 2C which, by Cantor's theorem, has cardinality strictly larger than 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 <a href="/facts/Cantor%27s_theorem/kGNIBpjL">Cantor's theorem</a> is that the cardinal numbers constitute a <a href="/facts/Proper_class/F5EmDd9b">proper class</a>. 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. <a href="/facts/Cantor%27s_theorem/kGNIBpjL">Cantor's theorem</a> then implies that every element of S is of cardinality strictly less than the cardinality of 2T.
<h2 id="discussion-and-consequences">Discussion and consequences</h2>
Since the cardinal numbers are well-ordered by indexing with the <a href="/facts/Ordinal_numbers/GelFLjJt">ordinal numbers</a> (see <a href="/facts/Cardinal_number/ccoKwU4R">Cardinal number, formal definition</a>), this also establishes that there is no greatest ordinal number; conversely, the latter statement implies Cantor's paradox. By applying this indexing to the <a href="/facts/Burali-Forti_paradox/NQusk9Ik">Burali-Forti paradox</a> we obtain another proof that the cardinal numbers are a <a href="/facts/Proper_class/F5EmDd9b">proper class</a> rather than a set, and (at least in <a href="/facts/ZFC/UYIsPbXw">ZFC</a> or in <a href="/facts/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory/5wLhAIMz">von Neumann–Bernays–Gödel set theory</a>) 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".

<h2 id="historical-notes">Historical notes</h2>
While Cantor is usually credited with first identifying this property of cardinal sets, some mathematicians award this distinction to <a href="/facts/Bertrand_Russell/SRpwNX2U">Bertrand Russell</a>, who defined a similar theorem in 1899 or 1901.

<ul><li><a href="/facts/Irving_Anellis/SJz7vQyM">Anellis, I.H.</a> (1991). Drucker, Thomas (ed.). "The first Russell paradox," Perspectives on the History of Mathematical Logic. Cambridge, Mass.: Birkäuser Boston. pp. 33–46.</li>
<li>Moore, G.H.; Garciadiego, A. (1981). <a href="https://doi.org/10.1016%2F0315-0860%2881%2990070-7">"Burali-Forti's paradox: a reappraisal of its origins"</a>. Historia Math. 8 (3): 319–350. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0315-0860%2881%2990070-7">10.1016/0315-0860(81)90070-7</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.3986">An Historical Account of Set-Theoretic Antinomies Caused by the Axiom of Abstraction</a>: report by Justin T. Miller, Department of Mathematics, University of Arizona.</li>
<li><a href="https://web.archive.org/web/20051211160822/http://planetmath.org/encyclopedia/CantorsParadox.html">PlanetMath.org</a>: article.</li></ul>

Cantor's paradox open-in-new

Cantor's paradox