Last revised 11feb16
\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}
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.
Question 8: How many different binimals have the form $0.d_1 d_2 ... d_{42} 1 1 1 1 1 ... $?
\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>