# 9.3: Cantor’s Theorem and Its Consequences

- Page ID
- 7966

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

Skills to Develop

- Explain Cantor's theorem

Once Cantor showed that there were two types of inﬁnity (countable and uncountable), the following question was natural, “*Do all uncountable sets have the same cardinality?*”

Just like not all “non-dogs” are cats, there is, oﬀ-hand, no reason to believe that all uncountable sets should be the same size. However constructing uncountable sets of diﬀerent sizes is not as easy as it sounds.

For example, what about the line segment represented by the interval \([0,1]\) and the square represented by the set \([0,1] × [0,1] = \{(x,y)|0 ≤ x,y ≤ 1\}\). Certainly the two dimensional square must be a larger inﬁnite set than the one dimensional line segment. Remarkably, Cantor showed that these two sets were the same cardinality. In his 1877 correspondence of this result to his friend and fellow mathematician, Richard Dedekind, even Cantor remarked, “I see it, but I don’t believe it!”

**Figure \(\PageIndex{1}\): **Richard Dedekind

The following gives the original idea of Cantor’s proof. Cantor devised the following function \(f : [0,1]×[0,1] → [0,1]\). First, we represent the coordinates of any point \((x,y) ∈ [0,1]×[0,1]\) by their decimal representations \(x = 0.a_1a_2a_3 ...\) and \(y = 0.b_1b_2b_3....\) Even terminating decimals can be written this way as we could write \(0.5 = 0.5000....\) We can then deﬁne \(f(x,y)\) by

\[f((0.a_1a_2a_3 ...,0.b_1b_2b_3 ...)) = 0.a_1b_1a_2b_2a_3b_3 ....\]

This relatively simple idea has some technical diﬃculties in it related to the following result.

Exercise \(\PageIndex{1}\)

Consider the sequence \((0.9,0.99,0.999,...)\). Determine that this sequence converges and, in fact, it converges to \(1\). This suggests that \(0.999... = 1\).

Similarly, we have \(0.04999... = 0.05000...\), etc. To make the decimal representation of a real number in \([0,1]\) unique, we must make a consistent choice of writing a terminating decimal as one that ends in an inﬁnite string of zeros or an inﬁnite string of nines [with the one exception \(0 = 0.000...\) ]. No matter which choice we make, we could never make this function onto. For example, \(109/1100 = 0.09909090...\) would have as its pre-image \((0.0999...,0.9000...)\) which would be a mix of the two conventions.

Cantor was able to overcome this technicality to demonstrate a one to one correspondence, but instead we will note that in either convention, the function is one-to-one, so this says that the set \([0,1]×[0,1]\) is the same cardinality as some (uncountable) subset of \(\mathbb{R}\). The fact that this has the same cardinality as \(\mathbb{R}\) is something we will come back to. But ﬁrst we’ll try construct an uncountable set which does not have the same cardinality as \(\mathbb{R}\). To address this issue, Cantor proved the following in 1891.

Theorem \(\PageIndex{1}\): Cantor’s Theorem

Let \(S\) be any set. Then there is no one-to-one correspondence between \(S\) and \(P(S)\), the set of all subsets of \(S\).

Since \(S\) can be put into one-to-one correspondence with a subset of \(P(S) (a → \{a\})\), then this says that \(P(S)\) is at least as large as \(S\). In the ﬁnite case \(|P(S)|\) is strictly greater than \(|S|\) as the following problem shows. It also demonstrates why \(P(S)\) is called the power set of \(S\).

Exercise \(\PageIndex{2}\)

Prove: If \(|S| = n\), then \(|P(S)| = 2n\)

**Hint**-
Let \(S = a_1, a_2, ..., a_n\). Consider the following correspondence between the elements of \(P(S)\) and the set \(T\) of all \(n\)-tuples of yes (\(Y\)) or no (\(N\)):

\[\{\}\leftrightarrow {N,N,N,...,N}\\ \{a_1\}\leftrightarrow \{Y,N,N,...,N\}\\ \{a_2\}\leftrightarrow \{N,Y,N,...,N\}\\\vdots \\ S \leftrightarrow \{Y,Y,Y,...,Y\}\]

How many elements are in \(T\)?

Exercise \(\PageIndex{3}\)

Prove Cantor’s Theorem.

**Hint**-
Assume for contradiction, that there is a one-to-one correspondence \(f : S → P(S)\). Consider \(A = \{x ∈ S|x \not {∈} f(x)\}\). Since \(f\) is onto, then there is \(a ∈ A\) such that \(A = f(a)\). Is \(a ∈ A\) or is \(a \not {∈} A\)?

Actually it turns out that \(\mathbb{R}\) and \(P(\mathbb{N})\) have the same cardinality. This can be seen in a roundabout way using some of the above ideas from Exercise \(\PageIndex{2}\). Speciﬁcally, let \(T\) be the set of all sequences of zeros or ones (you can use \(Y\)s or \(N\)s, if you prefer). Then it is straightforward to see that \(T\) and \(P(\mathbb{N})\) have the same cardinality.

If we consider \((0,1]\), which has the same cardinality as \(\mathbb{R}\), then we can see that this has the same cardinality as \(T\) as well. Speciﬁcally, if we think of the numbers in binary, then every real number in \([0,1]\) can be written as \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) where \(a_j ∈ \{0,1\}\). We have to account for the fact that binary representations such as \(0.0111...\) and \(0.1000...\) represent the same real number (say that no representations will end in an inﬁnite string of zeros), then we can see that \([0,1]\) has the same cardinality as \(T - U\), where \(U\) is the set of all sequences ending in an inﬁnite string of zeros. It turns out that \(U\) itself is a countable set.

Exercise \(\PageIndex{4}\)

Let \(U_n = \{(a_1, a_2, a_3,...) | a_j ∈ \{0,1\}\) and \(a_{n+1} = a_{n+2} = ··· = 0\}\). Show that for each \(n\), \(U_n\) is ﬁnite and use this to conclude that \(U\) is countably inﬁnite.

The following two problems show that deleting a countable set from an uncountable set does not change its cardinality.

Exercise \(\PageIndex{5}\)

Let \(S\) be an inﬁnite set. Prove that \(S\) contains a countably inﬁnite subset.

Exercise \(\PageIndex{6}\)

Suppose \(X\) is an uncountable set and \(Y ⊂ X\) is countably inﬁnite. Prove that \(X\) and \(X - Y\) have the same cardinality.

**Hint**-
Let \(Y = Y_0\). If \(X - Y_0\) is an inﬁnite set, then by the previous problem it contains a countably inﬁnite set \(Y_1\). Likewise if \(X - (Y_0 ∪ Y_1)\) is inﬁnite it also contains an inﬁnite set \(Y_2\). Again, if \(X - (Y_0 ∪ Y_1 ∪ Y_2)\) is an inﬁnite set then it contains an inﬁnite set \(Y_3\), etc. For \(n = 1,2,3,...,\) let \(f_n : Y_{n-1} → Y_n\) be a one-to-one correspondence and deﬁne \(f : X → X - Y\) by

\[\begin{cases} f(x) = f_n(x), & \text{ if } x \epsilon Y_n, n = 0,1,2,\cdots \\ f(x) = x, & \text{ if } x \epsilon X - \left ( \bigcup_{n=0}^{\infty }Y_n \right ) \end{cases}\]

Show that \(f\) is one-to-one and onto.

The above problems say that \(R\), \(T - U\), \(T\), and \(P(N)\) all have the same cardinality.

As was indicated before, Cantor’s work on inﬁnite sets had a profound impact on mathematics in the beginning of the twentieth century. For example, in examining the proof of Cantor’s Theorem, the eminent logician Bertrand Russell devised his famous paradox in 1901. Before this time, a set was naively thought of as just a collection of objects. Through the work of Cantor and others, sets were becoming a central object of study in mathematics as many mathematical concepts were being reformulated in terms of sets. The idea was that set theory was to be a unifying theme of mathematics. This paradox set the mathematical world on its ear.

## Russell’s Paradox

Consider the set of all sets which are not elements of themselves. We call this set \(D\) and ask, “*Is \(D ∈ D\)?*” Symbolically, this set is

\[D = \{S | S \not{\epsilon } S\}\]

If \(D ∈ D\), then by deﬁnition, \(D \not {∈} D\). If D 6∈ D, then by deﬁnition, \(D ∈ D\).

If you look back at the proof of Cantor’s Theorem, this was basically the idea that gave us the contradiction. To have such a contradiction occurring at the most basic level of mathematics was scandalous. It forced a number of mathematicians and logicians to carefully devise the axioms by which sets could be constructed. To be honest, most mathematicians still approach set theory from a naive point of view as the sets we typically deal with fall under the category of what we would call “*normal sets*.” In fact, such an approach is oﬃcially called Naive Set Theory (as opposed to Axiomatic Set Theory). However, attempts to put set theory and logic on solid footing led to the modern study of symbolic logic and ultimately the design of computer (machine) logic.

Another place where Cantor’s work had a profound inﬂuence in modern logic comes from something we alluded to before. We showed before that the unit square \([0,1]×[0,1]\) had the same cardinality as an uncountable subset of \(\mathbb{R}\). In fact, Cantor showed that the unit square had the same cardinality as \(\mathbb{R}\) itself and was moved to advance the following in 1878.

Conjecture (The Continuum Hypothesis)

Every uncountable subset of \(\mathbb{R}\) has the same cardinality as \(\mathbb{R}\).

Cantor was unable to prove or disprove this conjecture (along with every other mathematician). In fact, proving or disproving this conjecture, which was dubbed the Continuum Hypothesis, was one of Hilbert’s famous \(23\) problems presented as a challenge to mathematicians at the International Congress of Mathematicians in 1900.

Since \(\mathbb{R}\) has the same cardinality as \(P(N)\), then the Continuum Hypothesis was generalized to the:

Conjecture (The Generalized Continuum Hypothesis)

Given an inﬁnite set \(S\), there is no inﬁnite set which has a cardinality strictly between that of \(S\) and its power set \(P(S)\).

Eﬀorts to prove or disprove this were in vain and with good reason. In 1940, the logician Kurt Gödel showed that the Continuum Hypothesis could not be disproved from the Zermelo-Fraenkel Axioms of set theory ^{1}. In 1963, Paul Cohen showed that the Continuum Hypothesis could not be proved using the Zermelo-Fraenkel Axioms. In other words, the Zermelo-Fraenkel Axioms do not contain enough information to decide the truth of the hypothesis.

We are willing to bet that at this point your head might be swimming a bit with uncertainty. If so, then know that these are the same feelings that the mathematical community experienced in the mid twentieth century. In the past, mathematics was seen as a model of logical certainty. It is disconcerting to ﬁnd that there are statements that are “*undecidable*.” In fact, Gödel proved in 1931 that a consistent ﬁnite axiom system that contained the axioms of arithmetic would always contain undecidable statements which could neither be proved true nor false with those axioms. Mathematical knowledge would always be incomplete.

**Figure \(\PageIndex{2}\):** Kurt Gödel

So by trying to put the foundations of calculus on solid ground, we have come to a point where we can never obtain mathematical certainty. Does this mean that we should throw up our hands and concede defeat? Should we be paralyzed with fear of trying anything? Certainly not! As we mentioned before, most mathematicians do well by taking a pragmatic approach: using their mathematics to solve problems that they encounter. In fact, it is typically the problems that motivate the mathematics. It is true that mathematicians take chances that don’t always pan out, but they still take these chances, often with success. Even when the successes lead to more questions, as they typically do, tackling those questions usually leads to a deeper understanding. At the very least, our incomplete understanding means we will always have more questions to answer, more problems to solve.

What else could a mathematician ask for?

## References

^{1 }One of the formal axiomatic approaches to set theory established by Ernst Zermelo in 1908 and revised by Abraham Fraenkel in 1921.

## Contributor

Eugene Boman (Pennsylvania State University) and Robert Rogers (SUNY Fredonia)