\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Discussion 2 -- More on Cardinality and Countability}
\centerline{Friday, September 16}
\bigskip
\noindent
{\it Background}
\bigskip
\noindent
In class last time we introduced the following ideas:
\bigskip
\item{$\bullet$}  Two sets $A,B$ have the {\it same cardinality}
(written $A \sim B$) if there is a
1-1 and onto function $f : A\to B$.  (The intuitive meaning of 
this is that the two sets have the ``same number'' of elements.
But of course if the sets are infinite, then we don't actually 
have a usual number that represents the size of the set!  And
moreover, some strange things are possible.  For instance, 
$A\sim B$ while $A \subset B$ but $A \ne B$ is definitely 
possible.  Think of $A = {\bf N}$ and $B = {\bf Z}$.)
\item{$\bullet$}  A set $A$ is {\it countable} if ${\bf N} \sim A$.

\bigskip
\noindent
We also showed that ${\bf N}$ and ${\bf R}$ {\it do not}
have the same cardinality by a proof based on the Nested Interval
Property.  

Today, we will look at a different way to see that ${\bf N}$
and ${\bf R}$ do not have the same cardinality following an
idea of the 19th century German mathematician Georg Cantor.
We will also see another slightly tricky case of sets with 
the same cardinality.

\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
A)  (The ``Cantor Diagonalization Argument'').  In this problem
you will work through a proof that the set of real numbers in 
the open interval $(0,1)$ is not countable.  (This implies that
the whole set of real numbers isn't countable either, of course.)
Here's the basic idea of Cantor's proof.
Again, we argue by contradiction.  Suppose the
set $(0,1)$ was countable.  In other words, suppose we can list
all of the real numbers in $(0,1)$ as $x_n = f(n)$ for $n \in {\bf N}$
for some 1-1, onto function $f$.  Write each $x_n$'s decimal 
expansion in the form 
$$\eqalign{x_1 &= .d_{11} d_{12} d_{13} \cdots \cr
           x_2 &= .d_{21} d_{22} d_{23} \cdots \cr
        \vdots\ &= \qquad \vdots \cr
           x_n &= .d_{n1} d_{n2} d_{n3} \cdots \cr
        \vdots\ &= \qquad \vdots \cr   
           }\leqno(2)$$
(That is, $d_{nm}$ is the $m$th decimal digit in the decimal 
form of the $n$th number in the list:  
$d_{nm} \in \{0,1,2,3,4,5,6,7,8,9\}$ for all $n,m$.) 
Make a new decimal number $x = .b_1 b_2 b_3 \cdots $
from the expansions above by the rule:
$$b_n = \cases{2 & if $d_{nn} \ne 2$\cr
               3 & if $d_{nn} = 2$\cr}$$
(note: the $d_{nn}$ are the {\it diagonal} entries in the big, infinite
array of digits in the table above).
\item{1)}  Suppose the table (2) above looked like
$$\eqalign{x_1 &= .25443523 \cdots \cr
           x_2 &= .13403005 \cdots \cr
           x_3 &= .99893299 \cdots \cr
           x_4 &= .84723464 \cdots \cr}$$
How does the decimal expansion of the number $x$ start out here?
\item{2)} Explain in general why the real number represented by $x$ cannot 
be the same as any of the $x_n$ in the list.  Explain how this 
establishes the statement we are trying to show:  The set of real numbers in 
the open interval $(0,1)$ is not countable
\item{3)} (``Not so fast!'')  Some possible ``objections'' to the proof
sketched above are:
\bigskip
\itemitem{a)}  Some real numbers have more than one decimal expansion.
(For example, what's another way to write
$.31\overline{9} = .31999999\cdots$ ?)  Doesn't that cause a problem?
\itemitem{b)}  Can't we apply the same argument to the set of {\it 
rational} numbers in $(0,1)$ -- $(0,1) \cap {\bf Q}$.  That set
{\it is} countable (it's a subset of a countable set) so we could
list it as the $\{x_1,x_2,x_3,\ldots\}$.  Doesn't
that mean there's something wrong with the proof?
\bigskip
\noindent
These objections in fact {\it don't} invalidate the proof.  Why not?
\bigskip
\noindent
B)  We saw in class that $(0,1) \sim {\bf R}$ via the 1-1, onto function
$f(x) = \cot(\pi x)$ mapping $f: (0,1) \to {\bf R}$.  What if we 
include one of the endpoints of the finite interval?  Do $[0,1)$
${\bf R}$ have the same cardinality?  If so, how can we construct a
1-1, onto function $g: [0,1) \to {\bf R}$?  Some observations:  
\bigskip
\item{$\bullet$} We can try to use the function $f(x) = \cot(\pi x)$ as much as we
can to get $g$.  
\item{$\bullet$} But $g(0)$ must be some real number, so the ``trick''
is to figure out where $g(0)$ goes.  
\item{$\bullet$} Suppose $x_n = 1/(n+1)$  
for $n\in {\bf N}$.  We could try making $g(0) = f(x_1) = f(1/2)$ 
(whatever that number is) and $g(x) = f(x)$ for $x\in (0,1)$.  
But then $g$ is not 1-1 because $g(0)=f(1/2)=g(1/2)$.  What if
we then make $g(1/2) = g(x_1) = f(x_2)$.  That fixes one problem
but it creates another. (Why?)  Can we fix it?
\bye