Last revised 11feb16

The Cantor Cardinality Theorems

\begin{document} \maketitle \section{Introduction} In this lesson we study Georg Cantor's two famous theorems: that the rational numbers are countable and that the real numbers are not countable. Both proofs use a \textit{ diagonal argument } which are quite ingenious. In the case of the first, we take the opportunity to study an example of Julius Koenig's proof of the CBS-theorem. We make every part of of the CBS-theorem explicit. In the second case, we revisit the issue of n-ary expansion of real numbers. Rather than a decimal expansion we shall use a binary expansion, because it makes the argument clearer. \section{Some housekeeping first} In both theorems one says that "without loss of generality" we shall prove the theorem for the positive rational numbers, respectively for the real numbers between 0 and 1. Here are some tricks that bridge these gaps usually left to the reader. \subsection{The shuffling trick} We prove the theorem for the positive rationals because once proved, the theorem for all rationals is a corollary. The argument for this is a generalization of the argument that $\mathbb{Z}$ is countable by interleaving. Indeed, the argument goes in three steps: \begin{itemize} \item Given a bijection $f: \mathbb{N} \rightarrow \mathbb{Z} $. \item Given names to all positive rationals $\{p_1,p_2,p_3,.... \}$ \item We relable the negative rationals by using negative subscripts, $ p_{-i} := -p_i $. \item Then the function $F(p_i) = p_{f(i)}$ is a bijection from the positive rationals to (almost) all rationals. \end{itemize}
Question 1: Which rational number is missed by $F$?
\subsection{Erdos's Hotel} The Hungarian mathematician Paul Erdos was the greatest number theorist of the twentieth century. He was also very generous is working with others. Mathematicians prize their \textit{ Erdos Number}, the distance they have to coauthoring a paper with a coauthor of .... of Erdos. He solved the post-WWII housing problems in Hungary as follows. Begin by building a countable number of homes. Then, whenever a new family needs a home, ask all the current occupants to move into the next house, leaving the first one free. This in-joke is also told in terms of a hotel that never turns a new guest away. It has countably many rooms. So even if it is full, a new guest can move into the room vacated by the same procedure. Mathematically speaking, this is equivalent to the bijection \[ f: \mathbb{N} \rightarrow \{0\} \cup \mathbb{N}: f(n) = n-1 \]
Question 2: Use finite induction and Erdos's Hotel to show that the union of a finite and a countable set is countable.
\section{The positive rationals, $\mathbb{Q}^*$ are countable.} \subsection{Counting lattices} We start by counting up the integral lattice points in the first quadrant, carefully. Denote this set by \[ \Lambda := \{ (x,y) \in \mathbb{Z}\times \mathbb{Z}\ |\ x,y \ge 0 \} \] Note that the sum of the two coordinates are constant for lattice points on the same slope -1 diagonals. Let's call this the \textit{file-number} $x+y$ of the pair $(x,y)$. Consider this function. \[ f : \Lambda \rightarrow \mathbb{ N} : f(x,y) = 2^{x+y} + y. \] Thus $f(0,0)=1, f(1,0)= 2^1+0=2 , f(0,1)= 3, f(2,0)=4, f(1,1)=5, ... $, and it is not hard to see geometrically why $f$ is an injection, for instance as follows. If two different lattice points $(x_i,y_i), i=1,2$ are on the same file, so that their file-numbers are the same $s=x_1+y_1 = x_2 + y_2$ , then \[ f(x_1,y_1) = 2^s + y_1 \ne 2^s + y_2 = f(x_2,y_2)\]. Between files, the last $f$-value at the end of the $b$th-file is, by definition, $2^b+b$. And the first in the next file is $2^{b+1}$, which is larger. (Why?) So the $f$-values are strictly increasing, hence $f$ is one-to-one (injective).
Question 3: What is $f(7,11) = $?
Just to make make sure you understand, let's see why this is not a bijection. The inverse of this function cannot always be computed. We would have to solve $ n=2^{x+y}+y$ for $n\in \mathbb{ N}$. We always can find the largest power of $2$ no greater that $n$, $2^e \le n < 2^{e+1}$. Let's set $y=n-2^e$, and solve $x+y= e$ for $x = e - y$.
Question 4: What's wrong with that? Try it for $n=7$.
\subsection{Matching this up with the parts of the CBS-theorem} Let $A := \mathbb{ N}$ and $B := \mathbb{Q}^*$. We define the injection $\beta : A \rightarrow B : \beta(n) = \frac{n}{1} $. Since every rational number $q\in B=\mathbb{ Q}^*$ can be written uniquely in lowest terms as $\frac{n}{d}$ (i.e. the numerator and denominator have no common factor), we define $ \alpha(q) = f(n,d) $. Since $f$ is injective, so is $\beta$. In Koenig's proof of the CBS-Theorem, we take the disjoint union $C=A \cup B$. Note that in $C$, $7$ and $\frac{7}{1}$ are two different objects, even though they have the same numerical value. And that $\frac{14}{2}$, which has the same numerical value, is also not an object in $C$. Note that the successor function is unusual. For example, $\sigma(3) = \beta(3)= \frac{3}{1}$ is succeeded by $\alpha(\frac{3}{1}) = f(3,1) = 2^4+1 = 17$. The predecessor of $3$ would have to be a fraction $\frac{n}{d}$ for which $f(n,d)=3=2^1 + 1 = f(0,1)$ and $\frac{0}{1}$ is not a positive rational number. So the succession sequence is, in this case, \[\Sigma(3) =\{ 3, \frac{3}{1}, 2^4+1=17, \frac{17}{1}, 262145, ... \}. \] Note that it does stop at the left. But since it stops in $A=\mathbb{N}$ we can shift to the right to biject $\Sigma(3)\cap A \rightarrow \Sigma(3)\cap B $.
Question 5: Calculate the predecssors in $\Sigma(\frac{34}{1})$ to see where they stop.
In this case we must shift to the left to biject $\Sigma(\frac{34}{1}) \cap A \rightarrow \Sigma(\frac{34}{1})\cap B $. \subsection{Comment} \begin{itemize} \item Of course one example is not the proof of a general theorem. In this example there is no succession sequence that doesn't have a first element. \item Do you recognize something like Erdos's Hotel Trick operating here? \end{itemize} \section{The reals $\mathbb{R}$ are not countable.} Without loss of generality, we only consider the positive reals between up to, and including $1$, written $(0,1].$ This is called a \textit{ half-open interval} of the reals.. And to practice base 2, we shall use their binary expansions, call them "binimals" in analogy to decimals. For example $0.101 = \frac{1}{2}+\frac{1}{8} = \frac{5}{8}\ $. Every terminating binimal is numerically equivalent to a non-terminating one, for example $0.011111... =0.1 $. So every number $(0,1]$ has a unique non-terminating binimal expansion.
Question 6: Why can't $(0,1]$ be a finite set?
If we assume (although we know better, right?) that $(0,1]$ is countably inifinite, then we can list them all and consider their non-terminating binary expansion: \begin{eqnarray*} q_1&=&0.d_1^1 d_2^1 d_3^1 .... \\ q_2&=&0.d_1^2 d_2^2 d_3^2 .... \\ q_3&=&0.d_1^3 d_2^3 d_3^3 .... \\ ...&=&... \\ q_n&=&0.d_1^n d_2^n d_3^n .... \\ ...&=&... \\ \end{eqnarray*} With Cantor, we next construct a binimimal that isn't already in this list so: \begin{eqnarray*} q_\infty & := & 0.d_1 d_2 d_3 .... \mbox{ where } d_n =1-d_n^n \\ \end{eqnarray*}
Question 7: How does $q_\infty$ differ from every $q_n$?
We're not quite done yet.The binimal for $q_\infty$ we found could terminate, say with $0=d_n=d_{n+1}= ... $. This terminating binimal is equivalent to a nonterminating one. But how do we know that's not already in the list? The way we chose, that would mean all of the $q_i$ have an uninterrupted string of $1$s past the $n$-th binimal place. This could only be if the list is actually finite.

\subsection{Conclusion} We have shown that for every countably infinite set of numbers in $(0,1]$ we can, using Cantor's diagonal process, find another not already in the list. Therefore, $(0,1]$ is not countable. Since it is a subset of $\mathbb{R}$, the latter can't be countable either.

Do you see any similarities between the argument above, and our earlier discussion about proving the list of primes to be infinite?

In the literature, and especially on the web, you will find proofs of Cantor's theorem using decimals instead of binimals. In those arguments, one obtains non-terminating decimals by replacing a terminating one by its numerically equivalent which ends in a solid list of 9's rather than 1's. When you create Cantor's counterexample, by making its n-th digit different from the n-th digit of the n-th decimal in the list, how do you know Cantor's decimal won't terminate (i.e. have a solid string of 0's a the end)? \end{document}<\div><\pre><\body>