Cantor's theorem

In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A (the power set of A) has a strictly greater cardinality than A itself. For finite sets, Cantor's theorem can be seen to be true by a much simpler proof than that given below. Counting the empty subset, subsets of A with just one member, etc. for a set with $n$ members there are $2 n$ subsets and the cardinality of the set of subsets $n < 2 n$ is clearly larger. But the theorem is true of infinite sets as well. In particular, the power set of a countably infinite set is uncountably infinite. The theorem is named for German mathematician Georg Cantor, who first stated and proved it.

Proof

Two sets are equinumerous (have the same cardinality) if and only if there exists a bijection (a one-to-one correspondence) between them. To establish Cantor's theorem it is enough to show that, for any given set A, no function f from A into the power set of A, can be surjective, i.e. to show the existence of at least one subset of A that is not an element of the image of A under f. Such a subset is given by the following construction, sometimes called the Cantor diagonal set of f:^[1]^[2]

B=\left\{\,x\in A:x\not \in f(x)\,\right\}.

This means, by definition, that for all x in A, x ∈ B if and only if x ∉ f(x). For all x the sets B and f(x) cannot be the same because B was constructed from elements of A whose images (under f) did not include themselves. More specifically, consider any x ∈ A, then either x ∈ f(x) or x ∉ f(x). In the former case, f(x) cannot equal B because x ∈ f(x) by assumption and x ∉ B by the construction of B. In the latter case, f(x) cannot equal B because x ∉ f(x) by assumption and x ∈ B by the construction of B.

Slightly more formally, we just proved that the assumption that there exists x in A such that f(x) = B implies the contradiction:

x\in f(x)\iff x\in B\iff x\notin f(x)\iff x\notin B.

Therefore, by reductio ad absurdum, the assumption must be false.^[3] Thus there is no x such that f(x) = B; in other words, B is not in the image of f. Because B is in the power set of A, the power set of A has a greater cardinality than A itself.

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

Because of the double occurrence of x in the expression "x ∉ f(x)", 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 each row is labelled by a unique x from A = {x₁, x₂, ... }, in this order. A is assumed to admit a linear order so that such table can be constructed. Each column of the table is labelled by a unique y from the power set of A; the columns are ordered by the argument to f, i.e. the column labels are f(x₁), f(x₂), ..., in this order. The intersection of each row x and column y records a true/false bit whether x ∈ y. Given the order chosen for the row and column labels, the main diagonal D of this table thus records whether x ∈ f(x) for all x in A. The set B constructed in the previous paragraphs coincides with the row labels for the subset of entries on this main diagonal D where the table records that x ∈ f(x) is false.^[3] Each column records the values of the indicator function of the set corresponding to the column. The indicator function of B coincides with of the logically negated (true ↔ false) entries of the main diagonal. Thus the indicator function of B does not agree with any column in at least one entry. Consequently, no column represents B.

For a finite set, the proof can also be illustrated using a more prosaic presentation known as the barber paradox.^[4]

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]

A detailed explanation of the proof when X is countably infinite

To understand the proof, let's examine it for the specific case when X is countably infinite. Without loss of generality, we may take X = N = {1, 2, 3,...}, the set of natural numbers.

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

P(\mathbb {N} )=\{\varnothing ,\{1,2\},\{1,2,3\},\{4\},\{1,5\},\{3,4,6\},\{2,4,6,\dots \},\dots \}.

P(N) contains infinite subsets of N, e.g. the set of all even numbers {2, 4, 6,...}, as well as the empty set.

Now that we have an idea of what the elements of P(N) look like, let us attempt to pair off each element of N with each element of P(N) to show that these infinite sets are equinumerous. In other words, we will attempt to pair off each element of N with an element from the infinite set P(N), so that no element from either infinite set remains unpaired. Such an attempt to pair elements would look like this:

\mathbb {N} {\begin{Bmatrix}1&\longleftrightarrow &\{4,5\}\\2&\longleftrightarrow &\{1,2,3\}\\3&\longleftrightarrow &\{4,5,6\}\\4&\longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}P(\mathbb {N} ).

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 D be the set of all non-selfish natural numbers. By definition, the power set P(N) contains all sets of natural numbers, and so it contains this set D as an element. If the mapping is bijective, D must be paired off with some natural number, say d. However, this causes a problem. If d is in D, then d is selfish because it is in the corresponding set, contradicting the definition of "D". If d is not in D, then it is non-selfish and should instead be a member of D. Therefore no such element d which maps to D can exist.

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

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

Through this proof by contradiction we have proven that the cardinality of N and P(N) cannot be equal. We also know that the cardinality of P(N) cannot be less than the cardinality of N because P(N) contains all singletons, by definition, and these singletons form a "copy" of N inside of P(N). Therefore, only one possibility remains, and that is that the cardinality of P(N) is strictly greater than the cardinality of N, 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 theorem that follows immediately from Cantor's theorem, namely to the fact that there is no greatest cardinal number. This result can be stated more "paradoxically" as: the assumption that there is a set containing all sets (which is also called an universal set) leads to a contradiction. However, 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 |P(X)| > |X| for any set X. On the other hand, if all elements of P(X) were contained in X, we would have |P(X)| ≤ |X|.^[1] A closely related consequence of these facts is the definition of the (unbounded) sequence of beth numbers, corresponding to the cardinalities of N, P(N), P(P(N)), ...

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]

R_{A}=\left\{\,x\in A:x\not \in x\,\right\}.

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 R_U leads to the contradiction:

R_{U}\in R_{U}\iff R_{U}\notin R_{U}.

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;^[5] we can conclude from the contradiction obtained that we must reject the hypothesis that R_U∈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 R_A above, which in turn entailed that

R_{U}\in R_{U}\iff (R_{U}\in U\wedge R_{U}\notin R_{U}).

Had we used unrestricted comprehension (as in Frege's system for instance) by defining the Russell set simply as $R=\left\{\,x:x\not \in x\,\right\}$ , then the axiom system itself would have entailed the contradiction, with no further hypotheses needed.^[5]

Despite the syntactical similarities between the Russel 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.^[6]

History

Cantor gave essentially this proof in a paper published in 1891 Über eine elementare Frage der Mannigfaltigkeitslehre, 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. 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

Cantor's theorem has been generalized to any category with products.^[7]

References

^ ^a ^b ^c ^d 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.
^ ^a ^b Lawrence Paulson (1992). Set Theory as a Computational Logic (PDF). University of Cambridge Computer Laboratory. p. 14.
^ ^a ^b Graham Priest (2002). Beyond the Limits of Thought. Oxford University Press. pp. 118–119. ISBN 978-0-19-925405-7.
^ Albert Geoffrey Howson (1990). The Popularization of Mathematics. Cambridge University Press. p. 197. ISBN 978-0-521-40319-1.
^ ^a ^b Heinz-Dieter Ebbinghaus (2007). Ernst Zermelo: An Approach to His Life and Work. Springer Science & Business Media. pp. 86–87. ISBN 978-3-540-49553-6.
^ 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.
^ F. William Lawvere; Stephen H. Schanuel (2009). Conceptual Mathematics: A First Introduction to Categories. 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", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Weisstein, Eric W. "Cantor's Theorem". MathWorld.

[Dasgupta2013-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.

[Paulson1992-2] Lawrence Paulson (1992). Set Theory as a Computational Logic (PDF). University of Cambridge Computer Laboratory. p. 14.

[Priest2002-3] Graham Priest (2002). Beyond the Limits of Thought. Oxford University Press. pp. 118–119. ISBN 978-0-19-925405-7.

[Howson1990-4] Albert Geoffrey Howson (1990). The Popularization of Mathematics. Cambridge University Press. p. 197. ISBN 978-0-521-40319-1.

[Ebbinghaus2007-5] Heinz-Dieter Ebbinghaus (2007). Ernst Zermelo: An Approach to His Life and Work. Springer Science & Business Media. pp. 86–87. ISBN 978-3-540-49553-6.

[6] 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.

[LawvereSchanuel2009-7] F. William Lawvere; Stephen H. Schanuel (2009). Conceptual Mathematics: A First Introduction to Categories. Cambridge University Press. Session 29. ISBN 978-0-521-89485-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy projective Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo