Problem 11.2.2.
Consider the sequence \((0.9,0.99,0.999,\ldots)\text{.}\) Determine that this sequence converges and, in fact, it converges to \(1\text{.}\) This suggests that \(0.999\ldots=1\text{.}\)
Section 11.2 Cantor’s Theorem and Its Consequences
Once Cantor showed that there were two types of infinity (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, offhand, no reason to believe that all uncountable sets should be the same size. However constructing uncountable sets of different 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]\times[0,1]=\left\{(x,y)|0\leq x,y\leq 1\right\}\text{.}\) Certainly the two dimensional square must be a larger infinite 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!”
The following gives the original idea of Cantor’s proof. Cantor devised the following function \(f:[0,1]\times[0,1]\rightarrow [0,1]\text{.}\) First, we represent the coordinates of any point \((x,y)\in [0,1]\times[0,1]\) by their decimal representations \(x=0.a_1 a_2 a_3\ldots\) and \(y=0.b_1 b_2 b_3\ldots\text{.}\) Even terminating decimals can be written this way as we could write \(0.5=0.5000\ldots\text{.}\) We can then define \(f(x,y)\) by
\begin{equation*}
f((0.a_1 a_2 a_3\ldots ,0.b_1 b_2 b_3\ldots))=0.a_1 b_1 a_2 b_2 a_3 b_3\ldots\text{.}
\end{equation*}
This relatively simple idea has some technical difficulties in it related to the following result.
Similarly, we have \(0.04999\ldots=0.05000\ldots\text{,}\) 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 infinite string of zeros or an infinite string of nines [with the one exception \(0=0.000\ldots\) ]. No matter which choice we make, we could never make this function onto. For example, \(109/1100=0.09909090\ldots\) would have as its pre-image \((0.0999\ldots,0.9000\ldots)\) 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]\times[0,1]\) is the same cardinality as some (uncountable) subset of \(\RR\text{.}\) The fact that this has the same cardinality as \(\RR\) is something we will come back to. But first we’ll try construct an uncountable set which does not have the same cardinality as \(\RR\text{.}\) To address this issue, Cantor proved the following in 1891.
Theorem 11.2.3.
Cantor’s Theorem
Let \(S\) be any set. Then there is no one-to-one correspondence between \(S\) and \(P(S)\text{,}\) the set of all subsets of \(S\text{.}\)
Since \(S\) can be put into one-to-one correspondence with a subset of \(P(S)\) (\(a\rightarrow \left\{a\right\}\)), then this says that \(P(S)\) is at least as large as S. In the finite case \(\abs{P(S)}\) is strictly greater than \(\abs{S}\) as the following problem shows. It also demonstrates why \(P(S)\) is called the power set of \(S\text{.}\)
Problem 11.2.4.
Prove: If \(\abs{S}=n\text{,}\) then \(\abs{ P(S)}=2^n\text{.}\)
Hint.
Let \(S=\left\{a_1,a_2,\ldots,a_n\right\}\text{.}\) Consider the following correspondence between the elements of \(P(S)\) and the set \(T\) of all \(n\)-tuples of yes (Y) or no (N):
\begin{align*}
\{ \} \amp \leftrightarrow \{N,N,N,\ldots,N\}\\
\{a_1\}\amp \leftrightarrow \{Y,N,N,\ldots ,N\}\\
\{a_2\}\amp \leftrightarrow \{N,Y,N,\ldots,N\}\\
\amp \vdots\\
S\amp \leftrightarrow \{Y,Y,Y,\ldots,Y\}
\end{align*}
How many elements are in \(T?\)
Problem 11.2.5.
Prove Cantor’s Theorem 11.2.3.
Hint.
Assume for contradiction, that there is a one-to-one correspondence \(f:S\rightarrow P(S)\text{.}\) Consider \(A=\left\{x\in S|x\not\in f(x)\right\}\text{.}\) Since \(f\) is onto, then there is \(a\in A\) such that \(A=f(a)\text{.}\) Is \(a\in A\) or is \(a\not\in
A?\)
Actually it turns out that \(\RR\) and \(P(\NN)\) have the same cardinality. This can be seen in a roundabout way using some of the above ideas from Problem 11.2.4. Specifically, 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(\NN)\) have the same cardinality.
If we consider \((0,1]\text{,}\) which has the same cardinality as \(\RR\text{,}\) then we can see that this has the same cardinality as \(T\) as well. Specifically, 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} =0.a_1a_2a_3\ldots\) where \(a_j\in\left\{0,1\right\}\text{.}\) We have to account for the fact that binary representations such as \(0.0111\ldots\) and \(0.1000\ldots\) represent the same real number (say that no representations will end in an infinite string of zeros), then we can see that \([0,1]\) has the same cardinality as \(T-U\text{,}\) where \(U\) is the set of all sequences ending in an infinite string of zeros. It turns out that \(U\) itself is a countable set.
Problem 11.2.6.
Let \(U_n=\{(a_1,a_2,a_3,\ldots)\ |\ a_j\in \{0,1\} \text{ and } a_{n+1}=a_{n+2}=\cdots=0\}\text{.}\) Show that for each \(n\text{,}\) \(U_n\) is finite and use this to conclude that \(U\) is countably infinite.
The above problems say that \(\RR\text{,}\) \(T-U\text{,}\) \(T\text{,}\) and \(P(N)\) all have the same cardinality. The following two problems show that deleting a countable set from an uncountable set does not change its cardinality.
Problem 11.2.7.
Let \(S\) be an infinite set. Prove that \(S\) contains a countably infinite subset.
Problem 11.2.8.
Suppose \(X\) is an uncountable set and \(Y\subset X\) is countably infinite.
(a)
Prove that \(X\) and \(X-Y\) are both uncountable sets.
(b)
Prove that \(X\) and \(X-Y\) have the same cardinality.
Hint.
Let \(Y=Y_0\text{.}\) If \(X-Y_0\) is an infinite set, then by the previous problem it contains a countably infinite set \(Y_1\text{.}\) Likewise if \(X-(Y_0\cup Y_1)\) is infinite it also contains an infinite set \(Y_2\text{.}\) Again, if \(X-(Y_0\cup Y_1\cup Y_2)\) is an infinite set then it contains an infinite set \(Y_3\text{,}\) etc. For \(n=1, 2, 3,\ldots \text{,}\) let \(f_n:Y_{n-1}\rightarrow Y_n\) be a one-to-one correspondence and define \(f:X\rightarrow X-Y\) by
\begin{equation*}
f(x) =
\begin{cases}
f_n(x), \amp \text{ if } x\in Y_n, n=0,1,2,\ldots\\
x, \amp \text{ if } x\in X-(\cup_{n=0}^\infty Y_n ) \end{cases}\text{.}
\end{equation*}
Show that \(f\) is one-to-one and onto.
As we indicated before, Cantor’s work on infinite 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\in D?\)” Symbolically, this set is
\begin{equation*}
D=\{S\ |\ S\not \in S\}\text{.}
\end{equation*}
If \(D\in D\text{,}\) then by definition, \(D\not\in D\text{.}\) If \(D\not\in D\text{,}\) then by definition, \(D\in D\text{.}\)
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 officially 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 influence in modern logic comes from something we alluded to before. We showed before that the unit square \([0,1]\times [0,1]\) had the same cardinality as an uncountable subset of \(\RR\text{.}\) In fact, Cantor showed that the unit square had the same cardinality as \(\RR\) itself and was moved to advance the following in 1878.
Conjecture 11.2.9. The Continuum Hypothesis.
Every uncountable subset of \(\RR\) has the same cardinality as \(\RR\text{.}\)
Cantor was unable to prove or disprove this conjecture (along with every other mathematician). In fact, proving or disproving 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 \(\RR\) has the same cardinality as \(P(\NN)\text{,}\) then the Continuum Hypothesis was generalized to the:
Conjecture 11.2.10. The Generalized Continuum Hypothesis.
Given an infinite set \(S\text{,}\) there is no infinite set which has a cardinality strictly between that of \(S\) and its power set \(P(S)\text{.}\)
Efforts 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. 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 find that there are statements that are “undecidable.” In fact, Gödel proved in 1931 that a consistent finite 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.
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?
