Cantor's theorem

In mathematical set theory, Cantor's theorem is a fundamental

result which states that, for any set , the set of all subsets of
known as the power set of has a strictly greater cardinality than
itself.

For finite sets, Cantor's theorem can be seen to be true by simple

enumeration of the number of subsets. Counting the empty set as a
subset, a set with elements has a total of subsets, and the
theorem holds because for all non-negative integers.
The cardinality of the set {x, y, z}, is
Much more significant is Cantor's discovery of an argument that is three, while there are eight elements
applicable to any set, and shows that the theorem holds for infinite in its power set (3 < 23 = 8), here
ordered by inclusion.
sets also. As a consequence, the cardinality of the real numbers,
which is the same as that of the power set of the integers, is
strictly larger than the cardinality of the integers; see Cardinality of the continuum for details.

The theorem is named for Georg Cantor, who first stated and proved it at the end of the 19th century.
Cantor's theorem had immediate and important consequences for the philosophy of mathematics. For
instance, by iteratively taking the power set of an infinite set and applying Cantor's theorem, we obtain an
endless hierarchy of infinite cardinals, each strictly larger than the one before it. Consequently, the
theorem implies that there is no largest cardinal number (colloquially, "there's no largest infinity").

Proof
Cantor's argument is elegant and remarkably simple. The complete proof is presented below, with
detailed explanations to follow.

Theorem (Cantor) — Let be a map from set to its power set . Then
is not surjective. As a consequence, holds for
any set .

Proof
exists via the axiom schema of specification, and
because .
Assume is surjective.
Then there exists a such that .
From for all in , we deduce via
universal instantiation.
The previous deduction yields a contradiction of the form , since .
 Therefore, is not surjective, via reductio ad absurdum.
We know injective maps from to exist. For example, a function
such that .
Consequently, .∎

By definition of cardinality, we have for any two sets and if and only if there
is an injective function but no bijective function from to . It suffices to show that there is no
surjection from to . This is the heart of Cantor's theorem: there is no surjective function from any set
to its power set. To establish this, it is enough to show that no function (that maps elements in to
subsets of ) can reach every possible subset, i.e., we just need to demonstrate the existence of a subset
of that is not equal to for any . Recalling that each is a subset of , such a subset is
given by the following construction, sometimes called the Cantor diagonal set of :[1][2]

This means, by definition, that for all , if and only if . For all the sets and
cannot be equal because was constructed from elements of whose images under did not
include themselves. For all either or . If then cannot equal
because by assumption and by definition. If then cannot equal
because by assumption and by the definition of .

Equivalently, and slightly more formally, we have just proved that the existence of such that
implies the following contradiction:

Therefore, by reductio ad absurdum, the assumption must be false.[3] Thus there is no such that
; in other words, is not in the image of and does not map onto every element of the
power set of , i.e., is not surjective.

Finally, to complete the proof, we need to exhibit an injective function from to its power set. Finding
such a function is trivial: just map to the singleton set . The argument is now complete, and we
have established the strict inequality for any set that .

Another way to think of the proof is that , empty or non-empty, is always in the power set of . For
to be onto, some element of must map to . But that leads to a contradiction: no element of can map
to because that would contradict the criterion of membership in , thus the element mapping to
must not be an element of meaning that it satisfies the criterion for membership in , another
contradiction. So the assumption that an element of maps to must be false; and cannot be onto.

Because of the double occurrence of in the expression " ", this is a diagonal argument. For a
countable (or finite) set, the argument of the proof given above can be illustrated by constructing a table
in which

1. each row is labelled by a unique from , in this order. is assumed to

admit a linear order so that such table can be constructed.
 2. each column of the table is labelled by a unique from the power set of ; the columns are
ordered by the argument to , i.e. the column labels are , ..., in this order.
3. the intersection of each row and column records a true/false bit whether .
Given the order chosen for the row and column labels, the main diagonal of this table thus records
whether for each . One such table will be the following:

The set constructed in the previous paragraphs coincides with the row labels for the subset of entries
on this main diagonal (which in above example, coloured red) where the table records that is
[3]
false. Each row records the values of the indicator function of the set corresponding to the column. The
indicator function of coincides with the logically negated (swap "true" and "false") entries of the main
diagonal. Thus the indicator function of does not agree with any column in at least one entry.
Consequently, no column represents .

Despite the simplicity of the above proof, it is rather difficult for an automated theorem prover to produce
it. The main difficulty lies in an automated discovery of the Cantor diagonal set. Lawrence Paulson noted
in 1992 that Otter could not do it, whereas Isabelle could, albeit with a certain amount of direction in
terms of tactics that might perhaps be considered cheating.[2]

When A is countably infinite

Let us examine the proof for the specific case when is countably infinite. Without loss of generality, we
may take , the set of natural numbers.

Suppose that is equinumerous with its power set . Let us see a sample of what looks like:

Indeed, contains infinite subsets of , e.g. the set of all positive even numbers
, along with the empty set .

Now that we have an idea of what the elements of are, let us attempt to pair off each element of
with each element of to show that these infinite sets are equinumerous. In other words, we will
attempt to pair off each element of with an element from the infinite set , so that no element from
either infinite set remains unpaired. Such an attempt to pair elements would look like this:
Given such a pairing, some natural numbers are paired with subsets that contain the very same number.
For instance, in our example the number 2 is paired with the subset {1, 2, 3}, which contains 2 as a
member. Let us call such numbers selfish. Other natural numbers are paired with subsets that do not
contain them. For instance, in our example the number 1 is paired with the subset {4, 5}, which does not
contain the number 1. Call these numbers non-selfish. Likewise, 3 and 4 are non-selfish.

Using this idea, let us build a special set of natural numbers. This set will provide the contradiction we
seek. Let be the set of all non-selfish natural numbers. By definition, the power set contains all
sets of natural numbers, and so it contains this set as an element. If the mapping is bijective, must be
paired off with some natural number, say . However, this causes a problem. If is in , then is selfish
because it is in the corresponding set, which contradicts the definition of . If is not in , then it is
non-selfish and it should instead be a member of . Therefore, no such element which maps to can
exist.

Since there is no natural number which can be paired with , we have contradicted our original
supposition, that there is a bijection between and .

Note that the set may be empty. This would mean that every natural number maps to a subset of
natural numbers that contains . Then, every number maps to a nonempty set and no number maps to the
empty set. But the empty set is a member of , so the mapping still does not cover .

Through this proof by contradiction we have proven that the cardinality of and cannot be equal.
We also know that the cardinality of cannot be less than the cardinality of because
contains all singletons, by definition, and these singletons form a "copy" of inside of . Therefore,
only one possibility remains, and that is that the cardinality of is strictly greater than the cardinality
of , proving Cantor's theorem.

Related paradoxes
Cantor's theorem and its proof are closely related to two paradoxes of set theory.

Cantor's paradox is the name given to a contradiction following from Cantor's theorem together with the
assumption that there is a set containing all sets, the universal set . In order to distinguish this paradox
from the next one discussed below, it is important to note what this contradiction is. By Cantor's theorem
for any set . On the other hand, all elements of are sets, and thus contained in ,
therefore . [1]

Another paradox can be derived from the proof of Cantor's theorem by instantiating the function f with
the identity function; this turns Cantor's diagonal set into what is sometimes called the Russell set of a
given set A:[1]
The proof of Cantor's theorem is straightforwardly adapted to show that assuming a set of all sets U
exists, then considering its Russell set RU leads to the contradiction:

This argument is known as Russell's paradox.[1] As a point of subtlety, the version of Russell's paradox
we have presented here is actually a theorem of Zermelo;[4] we can conclude from the contradiction
obtained that we must reject the hypothesis that RU∈U, thus disproving the existence of a set containing
all sets. This was possible because we have used restricted comprehension (as featured in ZFC) in the
definition of RA above, which in turn entailed that

Had we used unrestricted comprehension (as in Frege's system for instance) by defining the Russell set
simply as , then the axiom system itself would have entailed the contradiction, with no
further hypotheses needed.[4]

Despite the syntactical similarities between the Russell set (in either variant) and the Cantor diagonal set,
Alonzo Church emphasized that Russell's paradox is independent of considerations of cardinality and its
underlying notions like one-to-one correspondence.[5]

History
Cantor gave essentially this proof in a paper published in 1891 "Über eine elementare Frage der
Mannigfaltigkeitslehre",[6] where the diagonal argument for the uncountability of the reals also first
appears (he had earlier proved the uncountability of the reals by other methods). The version of this
argument he gave in that paper was phrased in terms of indicator functions on a set rather than subsets of
a set.[7] He showed that if f is a function defined on X whose values are 2-valued functions on X, then the
2-valued function G(x) = 1 − f(x)(x) is not in the range of f.

Bertrand Russell has a very similar proof in Principles of Mathematics (1903, section 348), where he
shows that there are more propositional functions than objects. "For suppose a correlation of all objects
and some propositional functions to have been affected, and let phi-x be the correlate of x. Then "not-phi-
x(x)," i.e. "phi-x does not hold of x" is a propositional function not contained in this correlation; for it is
true or false of x according as phi-x is false or true of x, and therefore it differs from phi-x for every value
of x." He attributes the idea behind the proof to Cantor.

Ernst Zermelo has a theorem (which he calls "Cantor's Theorem") that is identical to the form above in
the paper that became the foundation of modern set theory ("Untersuchungen über die Grundlagen der
Mengenlehre I"), published in 1908. See Zermelo set theory.

Generalizations
Lawvere's fixed-point theorem provides for a broad generalization of Cantor's theorem to any category
with finite products in the following way:[8] let be such a category, and let be a terminal object in .
Suppose that is an object in and that there exists an endomorphism that does not have
any fixed points; that is, there is no morphism that satisfies . Then there is no object
of such that a morphism can parameterize all morphisms . In other words,
for every object and every morphism , an attempt to write maps as maps of
the form must leave out at least one map .

See also
Schröder–Bernstein theorem
Cantor's first uncountability proof
Controversy over Cantor's theory

References
1. Abhijit Dasgupta (2013). Set Theory: With an Introduction to Real Point Sets. Springer
Science & Business Media. pp. 362–363. ISBN 978-1-4614-8854-5.
2. Lawrence Paulson (1992). Set Theory as a Computational Logic (https://www.cl.cam.ac.uk/t
echreports/UCAM-CL-TR-271.pdf) (PDF). University of Cambridge Computer Laboratory.
p. 14.
3. Graham Priest (2002). Beyond the Limits of Thought. Oxford University Press. pp. 118–119.
ISBN 978-0-19-925405-7.
4. Heinz-Dieter Ebbinghaus (2007). Ernst Zermelo: An Approach to His Life and Work (https://a
rchive.org/details/ernstzermeloappr00ebbi_571). Springer Science & Business Media.
pp. 86 (https://archive.org/details/ernstzermeloappr00ebbi_571/page/n97)–87. ISBN 978-3-
540-49553-6.
5. Church, A. [1974] "Set theory with a universal set." in Proceedings of the Tarski Symposium.
Proceedings of Symposia in Pure Mathematics XXV, ed. L. Henkin, Providence RI, Second
printing with additions 1979, pp. 297−308. ISBN 978-0-8218-7360-1. Also published in
International Logic Review 15 pp. 11−23.
6. Cantor, Georg (1891), "Über eine elementare Frage der Mannigfaltigskeitslehre" (http://gdz.
sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002113910&physid=PHYS_0084),
Jahresbericht der Deutschen Mathematiker-Vereinigung (in German), 1: 75–78, also in
Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, E.
Zermelo, 1932.
7. A. Kanamori, "The Empty Set, the Singleton, and the Ordered Pair (https://math.bu.edu/peo
ple/aki/8.pdf)", p.276. Bulletin of Symbolic Logic vol. 9, no. 3, (2003). Accessed 21 August
2023.
8. F. William Lawvere; Stephen H. Schanuel (2009). Conceptual Mathematics: A First
Introduction to Categories (https://archive.org/details/conceptualmathem00lawv). Cambridge
University Press. Session 29. ISBN 978-0-521-89485-2.

Halmos, Paul, Naive Set Theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted
by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
Reprinted by Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (Paperback edition).
 Jech, Thomas (2002), Set Theory, Springer Monographs in Mathematics (3rd
millennium ed.), Springer, ISBN 3-540-44085-2

External links
"Cantor theorem" (https://www.encyclopediaofmath.org/index.php?title=Cantor_theorem),
Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Weisstein, Eric W. "Cantor's Theorem" (https://mathworld.wolfram.com/CantorsTheorem.ht
ml). MathWorld.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Cantor%27s_theorem&oldid=1261800743"