\documentclass[11pt,twoside]{article}
\usepackage{macros-course-lectures}

\begin{document}

\mainlylecture
\lecture{notes18}{Infinite Sets}{November 9, 2000}

\noindent
Topics for today:
\begin{itemize}
\item
Finite vs. infinite Sets
\item
Countable sets
\item
Uncountable sets
\item
Cardinalities of infinite sets
\item
Even bigger infinite sets
\end{itemize}

\reading{Velleman Chapter 7; Rosen 1.7}

The topic of this lecture is infinite sets.

Infinite sets can be tricky to think about.  For for example,
previously we saw the Pigeonhole Principle, which says that if a big
set is mapped to a small set, then some two items of the big set must
be mapped to the same item in the small set.  We also saw that the
Pigeonhole Principle appears to break down for infinite sets.  In
particular, the ``big'' set $\{ 0, 1, 2, 3, 4, \ldots \}$ of all
natural numbers is mapped one-to-one to the ``small'' set $\{ 0, 2, 4,
6, 8, \ldots \}$ of even numbers by the function $f(n) = 2n$.  This
raises confusion about what is meant by ``big'' and ``small'' infinite
sets.  One of the key points of this lecture is sorting out the
relative ``bigness'' of various infinite sets.

This subject is more abstract than others in 6.042.  
The techniques we develop for dealing with infinite sets will be 
useful later on in 6.045 when you learn about computability.

\section{Finite Sets vs. Infinite Sets}

Let's start by defining what it means for a set to be ``infinite''.
\begin{defin*}
  A set $S$ is {\em finite} if there exists an $n \in {\cal N}$ such that
  $|S| = n$.
\end{defin*}
\begin{defin*}
A set $S$ is {\em infinite} if it is not finite.
\end{defin*}
These definitions imply that every set is either finite or infinite.

Let's make sure we know what these definitions really mean.
They depend on the definition of ``cardinality'' for finite sets,
which we review here
\def\seto#1{\set{1,\ldots,#1}}
\begin{defin*}
We say that set $S$ has \emph{size}, or \emph{cardinality}, $n$, and
write $|S|=n$, if and only if there is a bijection from $S$ to the set
of integers $\seto{n}$.
\end{defin*}

This definition is unambiguous, as can be seen from the following
lemma:
\begin{lemma}
There is at most one $n$ such that $|S|=n$.
\end{lemma}
\begin{proof}
  Suppose $|S|=n$ and $|S|=m$.  Then there is a bijection $f$ from $S$
  to $\seto{n}$ and a bijection $g$ from $S$ to
  $\seto{m}$.  
  It follows that $h = g \circ f^{-1}$ is a bijection
  from $\seto{n}$ to $\seto{m}$.
% [[[Using the definition of composition in Rosen.]]]
  If $n > m$ then by the Pigeonhole Principle, $h$ maps two elements of
  $\seto{n}$ to the same element of $\seto{m}$, so is
  not a bijection.  This is a contradiction.  
  Similarly, if $m>m$, then $h^{-1}$ (also a bijection) maps two elements of
  $\seto{m}$ to the same element of $\seto{n}$.  This
  is also a contradiction.  The only remaining possibility is that
  $m=n$.
\end{proof}

We just used the Pigeonhole Principle in a rather formal proof.  In
fact, we never really proved the Pigeonhole Principle.  Here is a
proof.
\begin{theorem}
(Pigeonhole Principle) \\
  If $n>m$, then there is no injection (and thus no bijection) from
  $\seto{n}$ to $\seto{m}$
\end{theorem}

\begin{proof}
  By well ordering on $m$.  Suppose for contradiction that the claim
  is not always true, and consider the smallest $m$ for which it
  fails---that is, there is some injection
  $f:\seto{n}\rightarrow\seto{m}$.
\begin{description}
\item[Case 1.  There is no $i$ such that $f(i)=m$.]
  Then in fact $f:\seto{n}\rightarrow\seto{m-1}$ so $m$ is not the smallest
  counterexample---a contradiction.
\item[Case 2.  For some $i$ we have $f(i)=m$.] 

\begin{description}
\item[Case 2a. $i=n$.]  Consider the function
  $g:\seto{n-1}\rightarrow\seto{m-1}$ defined by $g(i)=f(i)$.  Since
  $f$ is an injection, no element of $\seto{n-1}$ other than $n$ is
  mapped by $f$ to $m$, so every other element of $\set{n-1}$ is
  mapped to a number less than $m$.  Therefore, $g$ does indeed map
  $\seto{n-1}$ to $\seto{m-1}$.  And since $f$ is an injection,
  and $g$ has the same mapping, $g$ is also an injection.  But
  $n-1>m-1$, so $g$ is a counterexample for $m-1$, which shows $m$ was
  not the smallest counterexample---another contradiction.
\item[Case 2b. $i \ne n$.]
We define a slightly different $g$ and argue as in case 2a.  The
function $g$ is given by $g(j)=f(j)$ for $j \ne i$, but $g(i)=f(n)$.
Since $f(i)=m$ and $f$ is a bijection, we know that $f(n) \ne m$, and
thus $f(n) < m$.  It follows that $g(j)<m$ for every $j<n$.  And once
again, $g$ is a bijection because $f$ is, so we have a smaller
counterexample---the last contradiction.
\end{description}
\end{description}
We have shown a contradiction in every case, so our initial
assumption that the lemma is not true must be false. 
\end{proof}

So, our definitions of finite and infinite sets should be clear, both
formally and informally.
For example, for all $n$, the set $\{ 0, 1, 2, 3, \ldots, n \}$ is
finite.  On the other hand, the set of all natural numbers, ${\cal N}
= \{ 0, 1, 2, 3, \ldots \}$, is infinite.
A more interesting example arose in the very first lecture this term: 
\begin{theorem}
The set $P$ of all primes is infinite.
\end{theorem}

\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that $P$ is finite.  
Then by the definition of a finite set,
there exists an $n \in {\cal N}$ such that $|P| = n$.  
Denote the
elements of $P$ by $p_1, p_2, \ldots, p_n$.  Now let $m = p_1 p_2
\cdots p_n + 1$.  Since $m > p_i$ for all $i$, $m$ cannot be a prime.
Hence $m$ must be divisible by some prime $p_i$:

\begin{eqnarray*}
& & p_i \mid m \\ & \Rightarrow & p_i \mid p_1 p_2 \cdots p_n + 1 \\ &
\Rightarrow & p_i \mid 1
\end{eqnarray*}

The first implication follows by substituting the definition of $m$.
The second follows because $p_i$ divides the product $p_1 p_2 \cdots
p_n$, and so must divide 1 in order to divide the sum.  But no prime
divides 1, so we have a contradiction.  Therefore, there are an
infinite number of primes.
\end{proof}

Proving that the set of primes is infinite is relatively easy, but the
next example shows that determining whether a set is finite or
infinite can be tricky.

\begin{defin*}
A {\em twin prime} is a pair $(n, n+2)$ such that both $n$ and $n + 2$
are prime.
\end{defin*}

Examples of twin primes include $(3, 5)$, $(5, 7)$, $(11, 13)$, $(17,
19)$, and $(101, 103)$.  Is the set of twin primes finite or infinite?
If you settle this question, then you can probably wheedle a few extra
credit points from your TA.  Mathematicians have tried unsuccessfully
to solve this problem for more than {\em two thousand years}!

Other examples of infinite sets:  the natural numbers, the even
natural numbers, the integers, the rationals, the reals.

Note that I haven't yet talked about the ``cardinality'' of an
infinite set, $|S|$.
It's not obvious what this means. 
We could just write $|S| = \infty$.
But it turns out there are different ``sizes'' of infinity.
In the rest of this lecture, we will try to classify different kinds
of infinities. \\
Sample question: What is the ``smallest'' kinds of infinite set? 

\section{Countable Sets}

\subsection{Definition}

Countably infinite sets are the ones that are ``like {\cal N}'' in
the sense that we can enumerate them in a list format: 
\begin{eqnarray*}
{\cal N} & = & \{ 0, 1, 2, 3, \ldots \} \\
\mbox{even numbers} & = & \{ 0, 2, 4, 6, \ldots \} \\
\mbox{squares} & = & \{ 0, 1, 4, 9, 16, \ldots \} \\
\mbox{primes} & = & \{ 2, 3, 5, 7, 11, \ldots \}
\end{eqnarray*}

Sets whose elements can be listed are called {\em countable sets}.  Of
course, we cannot write down \emph{every} element, but the $\ldots$
imply that if we keep going, writing down more elements of the list,
we will eventually get to any element that is supposed to be present.
That is, there is a first element, a second element, etc.
Equivalently, we can count through the items one after another so that
every element of the set is eventually counted.  Countable sets are
formally defined in terms of bijections with the natural numbers.
\begin{defin*}
An infinite set $S$ is said to be {\em countably infinite\/} iff there
exists a bijection $f: {\cal N} \mapsto S$.  A set is {\em countable}
if it is finite or countably infinite.
\end{defin*}
This formal definition is equivalent to the notion of a listable set,
since listing the elements of a set gives a bijection with ${\cal N}$
and vice versa.  
When we list the elements
of $S$ as $s_0, s_1, s_2, \ldots$, we are actually defining a
bijection $f: {\cal N} \mapsto S$ by $f(i) = s_i$.  In the reverse
direction, if we have such a bijection, then $f(0), f(1), f(2),
\ldots$ is a list of all the elements of $S$.

Caution:
Sometimes we can list the elements of a set $S$, but the corresponding
bijection $f: {\cal N} \mapsto S$ is very hard to compute.  For
example, in principle we could list the elements in any subset of
${\cal N}$.  However, most of these subsets are bizarre and difficult
to describe; writing a program to compute $f(i)$ might be difficult or
even impossible.  The good news is that to prove that $S$ is
countable, we must only prove that a bijection $f: {\cal N} \mapsto S$
exists; we do not have to write $f$ explicitly or to give an algorithm
to compute $f(i)$.

Let's use this definition to prove that some sets are countable. 
\begin{lemma}
The set of even numbers is countably infinite.
\end{lemma}

\begin{proof}
An example of a bijection from $\cal N$ to $\set{0,2,4,6,8,\ldots}$ is
the function $f(x)= 2x$. 
\end{proof}

Another example of a bijection between these sets is obtained by
listing the even numbers in another order, say $2, 0, 6, 4, 10, 8,
\ldots...$.
This listing defines the desired bijection, e.g. $f(0) = 2$,
$f(1) = 0$, $f(2) = 6$, $f(3) = 4$, etc. \\
This is the typical way to prove that a set is countably
infinite---just show that you can list all of the elements.  This
implicitly defines a bijection with ${\cal N}$. 
Note that we only have to prove that a bijection $f$ exists; it is not
necessary to come up with a closed-form formula for computing $f$.

\begin{example}
Set $B$ of finite length bit strings. \\
Enumerate $B$ as: $\lambda, 0, 1, 00, 01, 10, 11, 000, \ldots$.
\end{example}

\subsection{Integers}

\begin{theorem}
The set ${\cal Z}$ of integers is countably infinite.
\end{theorem}

\begin{proof}
To prove that that the integers are countably infinite, we must prove that
there exists a bijection $f: {\cal N} \mapsto {\cal Z}$.  
The integers can be listed as follows: $0, 1, -1, 2, -2, 3, -3, 4, -4,
\ldots$.
\end{proof}

As noted above, we only have to prove that
a bijection $f$ exists; we don't need a formula. 
In this case, however, $f$ can be written as:
\[
f(i) = \left \{
\begin{array}{ll}
- \frac{i}{2} & \mbox{if } i \mbox{ is even,} \\
\frac{i+1}{2} & \mbox{if } i \mbox{ is odd.} \\
\end{array}
\right.
\]

The method of proving a set countable by listing elements has one
potential pitfall.  As an example, the following listing of the
integers does not demonstrate countability: 
\[
0, -1, -2, -3, \ldots, 1, 2, 3, \ldots 
\]
The problem is that the ``$\ldots$'' in the middle of the list represents
a infinite number of elements.  As a result, we never actually get
around to listing the positive integers; in particular, there is no
$i$ such that $f(i) = 1$.  This means that the function $f$
``defined'' by this listing is not a bijection (actually, it is
not properly ``defined'' at all).

\subsection{Unions of Countable Sets}

The integers can be viewed as the union of two countably infinite
sets: the natural numbers and the negative integers.
The natural numbers are obviously countably infinite.
It is also easy to see that the negative integers are countably infinite.
The ``interleaving'' strategy described above is a way to see that the
union of these two countably infinite sets is also countably infinite.

Another example: Half integers. \\
Define the set ${\cal Z}^{1/2}$ as follows:
\begin{eqnarray*}
{\cal Z}^{1/2} & = & \{ \frac{x}{2} \mid x \in {\cal Z} \} \\
        & = & \{ 0, 1, -1, 2, -2, \ldots \} \cup
              \left\{ \frac{1}{2}, -\frac{1}{2}, \frac{3}{2}, -\frac{3}{2},
                \ldots \right\}
\end{eqnarray*}
In other words, ${\cal Z}^{1/2}$ consists of all integers and all half
integers.  This set is countable.  We have written ${\cal Z}^{1/2}$ above as
the union of two countable sets.  We can list all the elements of
${\cal Z}^{1/2}$ by interleaving these two lists:
\[
Z^{1/2} = \left\{ 0, \frac{1}{2}, 1, -\frac{1}{2}, -1,
        \frac{3}{2}, 2, -\frac{3}{2}, -2, \ldots \right\}
\]

This trick generalizes to a theorem.
\begin{theorem}
\label{th:union}
If $A$ and $B$ are countable, then $A \cup B$ is countable.
\end{theorem}

\begin{proof}
From the definition of ``countable'', we have four cases.  
Each of $A$ and $B$ may be countably infinite or finite.
If both are countably infinite, we can list the elements: 
\begin{eqnarray*}
A & = & \{ a_1, a_2, a_3, \ldots \} \\
B & = & \{ b_1, b_2, b_3, \ldots \} \\
\end{eqnarray*}
Therefore, we can list the elements of the union as follows:

\[
A \cup B  =  \{ a_1, b_1, a_2, b_2, a_3, b_3, \ldots \}
\]
There is a complication: 
sets $A$ and $B$ may contain common elements.
Therefore, an element should be omitted from the list if it already
appears in a smaller position. \\
\\
If one of the sets is finite, we continue listing elements of the
other set without interleaving. \\
\\
If both are finite, then, as we already know, the union is finite,
which means that it's countable. 
\end{proof}

\subsection{Rationals}

Recall that the set ${\cal Q}$ of rational numbers consists of all
ratios of integers with non-zero denominator:
\[
{\cal Q} = \{ a/b \mid a, b \in {\cal Z}, b \neq 0 \}
\]
There are a lot of rational numbers!  It is easy to imagine that we
could not list all the rational numbers just as we could not list all
the real numbers.  In fact, however, there is a clever way to list all
the rationals, and this proves that the set ${\cal Q}$ is countable.

\begin{theorem}
\label{th:rationals}
The set ${\cal Q}$ of rational numbers is countable.
\end{theorem}

\begin{proof} {\em (Failed attempt.) }
To prove that that the rational numbers are countable, we must prove
that there exists a bijection $f: {\cal N} \mapsto {\cal Q}$.  The
rational numbers can be listed as follows:

\[
0,
\frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \ldots,
\frac{1}{2}, \frac{2}{2}, \frac{3}{2}, \ldots,
\frac{1}{3}, \frac{2}{3}, \frac{3}{3}, \ldots
\]

Omit from the listing all numbers that have already appeared.  (For
example, $2/2$ and $3/3$ should be omitted, since the rational number
1 already appeared as $1/1$.)  This listing implicitly defines the
desired bijection $f$.
\end{proof}

There are two problems with this ``proof'', one minor and one serious.
The minor problem is that we completely forgot the negative rational
numbers.  But the negative rationals are easy to add; we will show how
in the correct proof given below.  The killer problem is that we used
``$\ldots$'' in the middle of the list to represent an infinite number
of elements.  This means that we will never reach, say, 1/2; that is,
there is no $i$ such that $f(i) = 1/2$.  This means that $f$ is not a
bijection as claimed.  We need to list the rational numbers in a
completely different order to make the proof work.

\begin{proof} {\em (Successful attempt.) }
We can list the positive rational numbers in the order indicated in
Figure~\ref{fig:rationals}, omitting numbers that have already
appeared in the list.  This proves that the positive rationals are
countable.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/rationals.eps,height=2.5in}}
\caption{\em This digram shows the ordering of rationals used in the proof
of Theorem~\ref{th:rationals}.  This ordering technique is called
``dovetailing''.}
\label{fig:rationals}
\end{figure}

Negating each number in the figure establishes that the negative
rationals are countable.  The set of all rationals is the union of
positive rationals, negative rationals, and $\{ 0 \}$.  Since these
three sets are countable, two applications of Theorem~\ref{th:union}
show that the set of all rationals is countable.
\end{proof}

\subsection{Products of Countable Sets}

The ordering technique used in the proof and indicated in
Figure~\ref{fig:rationals} is called ``dovetailing''.  This technique
is often used in 6.045.  We can use dovetailing to prove that the
product of any two countable sets is countable:

\begin{theorem}
If $A$ and $B$ are countable, then $A \times B$ is countable.
\end{theorem}

\begin{proof}
Since $A$ and $B$ are countable, we can list the elements of $A$ as
$\{a_1, a_2, a_3, \ldots\}$ and the elements of $B$ as $\{b_1, b_2, b_3,
\ldots\}$.  We can obtain a listing of $A \times B$ by dovetailing:

\begin{eqnarray*}
&& (a_1, b_1), \\
&& (a_1, b_2), (a_2, b_1), \\
&& (a_1, b_3), (a_2, b_2), (a_3, b_1), \\
&& (a_1, b_4), (a_2, b_3), (a_3, b_2), (a_4, b_1), \\
&& \quad \quad \ldots \quad \quad \ldots
\end{eqnarray*}

If either or both sets $A$ and $B$ are finite, omit from the listing
all pairs containing non-existent elements $a_i$ or $b_j$.
\end{proof}

Note that the ordering of elements in this proof corresponds to the
ordering in Figure~\ref{fig:rationals}.  In fact, the proof that the
rationals are countable used the idea of the above proof with $A = B =
{\cal Z}^+$.

\begin{example}
The Cartesian product ${\cal N} \times {\cal N}$ is countable. \\
That's because it's the product of two countable sets.
\end{example}

Another way of viewing the product examples is as countable unions of
countable sets.
E.g., for the ${\cal N} \times {\cal N}$ example, we can express the
entire set as the countable union of sets $A_i$, $i \in {\cal N}$,
where $A_i$ is defined to be the set of all pairs of the form $(i,n)$,
$n \in {\cal N}$.
In general, we have:
\begin{theorem}
If for all $i \in {\cal N}$, $A_i$ is a countable set, then
$\bigcup_{i \in {\cal N}} A_i$ is countable.
\end{theorem}

\begin{proof}
Use a dovetailing construction.
\end{proof}

\subsection{The Smallest Infinite Sets}

Is ${\cal N}$ the smallest infinite set?
We can show that it is, in the following sense:
\begin{theorem}
Suppose $T$ is ``no larger'' than ${\cal N}$, in the sense that $T$
has a bijection with a subset of ${\cal N}$.
Then $T$ is either countably infinite or finite.
\end{theorem}

\begin{proof}
Assume that there is a bijection between $T$ and a subset $A$ of
${\cal N}$.  Write $A = \{a_0, a_1, a_2, \ldots \}$, listing the
elements of $A$ in the order in which they appear in $\cal N$.
If $A$ is finite, then $T$ is also finite because of the bijection. \\
\\
On the other hand, if $A$ is infinite, then there is a bijection from
${\cal N}$ to $A$, given by the enumeration of $A$ above.
Also, there is a bijection from $A$ to $T$, by assumption.  So by
composition of bijections, there is a bijection from ${\cal N}$ to
$T$.
That says that $T$ is countably infinite.
\end{proof}

This theorem says that there is nothing whose ``size'' is between the
countably infinite sets and the finite sets.
We still haven't defined the size of an infinite set;
we'll come back to this later in the lecture. 

So far, we have finite sets and countably infinite sets.
Let's continue classifying. 
Are all infinite sets countably infinite?

\section{Uncountable Sets}

It turns out that many important sets are not countable.  Sets that
are not countable are called {\em uncountable}.

\subsection{Reals}

The most important example of an uncountable set is the reals:
\begin{theorem*}
The set ${\cal R}$ of real numbers is uncountable.
\end{theorem*}

This theorem says that there is no way to make a list of all the real
numbers.  Naturally, one is immediately tempted to try anyway:
\[
0,\ 1,\ 0.5,\ 0.75,\ 0.1,\ 0.05,\ 0.001,\ \ldots
\]
It looks like this is not going to be so easy!  
For example, where are we going to
stick in $\sqrt{2}$ and $\pi^{-173}$?
We can actually prove that no such listing exists.

We'll first work through the proof informally, and then make it more formal.
The argument is by contradiction; we assume for the purpose of
contradiction that ${\cal R}$ is countable.  This means that there
exists a bijection $f: {\cal N} \mapsto {\cal R}$.  We can then make a
list of all the real numbers that looks something like the one shown
below.  (The extra spaces only serve to highlight a diagonal sequence
of digits discussed below.)

\begin{verbatim}
                    f(0) =  76. 5 430000000...
                    f(1) = 163.7 7 77777777...
                    f(2) =   2.78 7 8787878...
                    f(3) =  -1.112 1 231234...
                    f(4) =   3.1415 9 26535...
                    f(5) = -15.37273 2 3928...
                    ...
\end{verbatim}

The plan is to reach a contradiction by constructing a real number
that appears nowhere in the list; this will prove that $f$ is not
surjective and contradict the assumption that $f$ is a bijection.

Consider the number defined by the diagonal digits in the above table,
$0.577192\ldots$.  Now suppose that we add 5 to every digit, working
modulo 10.  This gives $0.022647\ldots$; call this value $r$.  This
quantity $r$ is totally bizarre, but it is a well-defined real number,
since we have specified all the digits.

By our construction of $r$, $f(0)$ differs from $r$ in the first
position to the right of the decimal.  Similarly, $f(1)$ differs from
$r$ in the second decimal position, $f(2)$ differs in the third
position, and so forth.  In general, $f(i)$ differs from $r$ in the
$(i+1)$-st position.  So for all $i$, $f(i)$ is not equal to $r$.
This implies that the real number $r$ does not appear anywhere in our
list!
That contradicts our assumption that the list contains all the reals.

There is one irritating problem in the preceding paragraph that must
be fixed.  Some numbers have two decimal representations.  For
example, $1 = 0.999\ldots$.  Therefore, distinct decimal
representations do not necessarily correspond to distinct numbers.
Even though $r$ disagrees with $f(i)$ in at least one digit, the
two might be equal.  However, our construction ensures that $r$
actually differs from $f(i)$ by at least $4 \cdot 10^{-(i+1)}$.  For
example, $1.0002999\ldots$ differs from $1.0007000\ldots$ by $4 \cdot
10^{-4}$.

Here is how the same argument might be written as a formal proof.

\begin{proof}
We must show that there is no bijection $f: {\cal N} \mapsto {\cal
R}$.  The proof is by contradiction.  Assume for the purpose of
contradiction that such a bijection $f$ exists.  Let $r$ be the real
number with decimal expansion $0.r_0r_1r_2r_3\ldots$ where $r_i$ is $5
\ +$ the $(i+1)$-st decimal digit of $f(i)$, taken modulo 10.  
For all $i$, $f(i) \neq r$, since the $(i+1)$-st digits of $f(i)$ and
$r$ disagree by 5 and so $|r - f(i)| \geq 4 \cdot 10^{-(i+1)}$.  This
implies that $f$ is not surjective, contradicting the assumption that
$f$ is a bijection.
\end{proof}

This is called a ``diagonalization argument'', because of the
construction based on diagonal entries.  Diagonalization arguments are
used all the time to prove that there is no bijection between two
infinite sets.  The generic idea is to assume for the purpose of
contradiction that a bijection $f$ exists.  Then an element $r$ of the
range is constructed that differs from $f(\alpha)$ for
every $\alpha$ in the domain.  (In this case, for example, the real
number $r$ differs from $f(k)$ in the $(k+1)$-st decimal position for
every natural $k$.)  The existence of such an $r$ shows that $f$ is
not surjective, contradicting the assumption that $f$ is a bijection.
We conclude that no bijection between the two sets exists.

Diagonalization arguments are important in logic and computer science.
For example, this type of argument is used to show that there are some
problems that cannot be solved by a computer no matter how much time
you give them.  A similar method is used in logic to prove G\"{o}del's
Theorem, which says that there are some true theorems for which no
proof exists!

As with countable sets, bijections provide the way to see that two
uncountable sets are the ``same size.'' 
\begin{lemma}
\label{lm: interval-reals}
Let $(0,1)$ be the reals between 0 and 1.  Let $\reals^+$ be the
positive real numbers.  Then there is a bijection between the interval
$(0,1)$ and $\reals^+$
\end{lemma}
\begin{proof}
The function $f(x)=1/(1+x)$ is a bijection from the positive reals to
$(0,1)$.
\end{proof}

This is a bit surprising, as the positive reals seem much bigger.

\begin{example}
Countable or uncountable? \\
Define $S_n$ to be the set of $n$-digit decimal numbers.  For example:
\begin{eqnarray*}
S_1 = \{ .0, .1, .2, \ldots, .9 \} \\
S_2 = \{ .00, .01, .02, \ldots, .99 \} \\
\end{eqnarray*}
Now let $S = \bigcup_{n=1}^\infty S_n$.  Is $S$ countable?

{\em Argument that $S$ is uncountable: } We will prove that $S$ is
uncountable by the same diagonalization argument that we used to prove
that the set ${\cal R}$ of real numbers is uncountable.  Assume for
the purpose of contradiction that we can list the elements of $S$ in
some order $s_0, s_1, s_2, \ldots$.  Define $r = .r_0r_1r_2\ldots$
where $r_i$ is $5\ +$ the $(i+1)$-st decimal digit of $s_i$ taken
modulo 10.  Since $S$ contains decimal numbers of every length, $r$
must be in $S$.  However, $r$ differs from every element of $S$ by at
least one digit.  Therefore, $r$ is not in $S$, and we have a
contradiction.

{\em Argument that $S$ is countable: } We can list the elements of $S$
by listing the elements of $S_1$, followed by $S_2$, followed by
$S_3$, etc.  Since each of these sets is finite, every set is fully
listed eventually.

The first argument is incorrect, and the second argument is correct.
The false statement in the first argument is, ``Since $S$ contains
decimal numbers of every length, $r$ must be in $S$.''  The set $S$
does contain decimal numbers of every {\em finite} length, but no
numbers with an infinite number of non-zero digits to the right of the
decimal.  For example, the number $1/9 = 0.11111\ldots$ is not
contained in any set $S_i$ and therefore is not contained in the union
$S$.  As a result, there are many real numbers not in $S$.  For this
reason, the statement, ``$r$ must be in $S$'' is false.  This
eliminates the contradiction from the proof by contradiction!

The second argument is correct; the union of a countable number of
finite sets is always countable.
\end{example}

\subsection{The Subsets of {\cal N}}

\begin{theorem}
\label{th: powerset-uncountable}
The set $P({\cal N})$ of all subsets of $\cal N$ is uncountable.
\end{theorem}

In contrast, note that the set of all finite subsets of ${\cal N}$ is
countable. 
That's because we can list all of these (say, in order of size).

\begin{proof}
By contradiction, using a diagonalization construction like the one
for the reals.  It's actually a little simpler, because we don't have
the complication of duplicate representations. \\
\\
Represent each set $S$ by a bit string, with a $1$ in exactly the
positions corresponding to numbers $i \in S$.
(E.g., evens are represented by the string $1, 0, 1, 0, 1, \ldots$.)
Every set has exactly one representation.

Suppose we could enumerate all these sets, e.g.: \\
$S_0:  1 0 1 0 1 0 1 \ldots$ \\
$S_1:  0 0 0 1 0 0 0 \ldots$ \\
$S_2:  1 1 1 0 1 1 0 \ldots$ \\
... \\
\\
So, the bit in position $j$ of the string corresponding to $S_i$ is
$1$ if $j \in S_i$, $0$ if not. \\
\\
Now get a contradiction by finding a subset $T$ of ${\cal N}$ that
doesn't appear in the list.
Construct $T$ so that it differs from each set in the membership of
the diagonal element, that is, it differs from $S_0$ in the membership
of $0$, differs from $S_1$ in the membership of $1$, etc. 
Thus, $0 \in T$ iff $0 \notin S_0$, 
$1 \in T$ iff $1 \notin S_1$, and, in general,
$i \in T$ iff $i \notin S_i$. \\
\\
Obviously, $T$ doesn't appear in the list, so this list cannot contain
all the subsets of ${\cal N}$.
This is a contradiction, so $P(\cal N)$ is uncountable.
\end{proof}

\begin{proof}
(Alternative:)
In the construction above, the set $T$ can be written in a
more-obscure-looking way as $T = \{i | i \notin S_i \}$.
That is, $T$ is the set of all natural numbers that don't belong to
the set with that number as its index. 
The contradiction can be obtained by supposing that $T$ does appear in
the list, so it must be $S_j$ for some $j$. \\
Then we consider whether $j \in T$ or not, and get a contradiction
either way.
For, if $j \in T$, it means that $j \in S_j$, which means that $j
\notin T$ by definition of $T$. \\
And if $j \notin T$, then it means that $n \notin S_j$, which means
that $j \in T$ by definition of $T$. \\
Either way, a contradiction.
\end{proof}

The idea of this tricky looking contradiction is drawn from 
``Russell's Paradox''.  We will see it again in a few minutes.

The distinction between countable and uncountable sets is so important
that it distinguishes entire fields of mathematics.  Discrete math is
the study of countable sets; calculus, analysis, and continuous math
all study uncountable sets.  In this course, we will stick to discrete
mathematics after today; all sets will be countable.

\section{Cardinalities of Infinite Sets}

There seems to be some similarity between the set of reals and the
powerset of the naturals.
Are the two sets the same size?  
It's finally time to say more about what we mean by sizes of infinite
sets.

\subsection{Definition}

Two sets are considered to be the ``same size'' if there is a bijection
between them.  For example, the set of natural numbers is the same
size as the set of rational numbers because there is a bijection $f:
{\cal N} \mapsto {\cal Q}$.  On the other hand, the set of natural
numbers is not the same size as the set of real numbers because we
proved there is no bijection between these sets.

More generally, we say that:
\begin{itemize}
\item $|A| = |B|$ iff there exists a bijection $f: A \mapsto B$
\item $|A| \leq |B|$ iff there exists an injection $f: A \mapsto B$
\item $|A| \geq |B|$ iff there exists a surjection $f: A \mapsto B$
\item $|A| < |B|$ iff $|A| \leq |B|$ and $|A| \neq |B|$, that is,
there is an injection but there is no bijection.
\item $|A| > |B|$ iff $|A| \geq |B|$ and $|A| \neq |B|$, that is,
there is a surjection but there is no bijection.
\end{itemize}
If you are being careful, you will see that we haven't actually given
a formal definition of the cardinality of an arbitrary set, but have
only given some properties (axioms) that this notion has to satisfy.
Some additional properties follow from these axioms, for instance:

\begin{lemma}
$|A| \le |A|$.
\end{lemma}

\begin{proof}
The function $f:A\rightarrow A$ given by $f(a)=a$ is clearly an
injection.
\end{proof}

\begin{lemma}
$|A| \le |B|$ and $|B| \le |C|$ together imply $|A|\le|C|$.
\end{lemma}
\begin{proof}
  Let $f:A\rightarrow B$ and $g:B \rightarrow C$ be the assumed
  injections.  Then $h:A\rightarrow C$ given by $h(a)=g(f(a))$ is also
  an injection.  For suppose that $a \ne a'$.  Then by injectivity of
  $f$, we know $f(a) \ne f(a')$.  But then by injectivity of $g$, we
  know that $g(f(a)) \ne g(f(a'))$, that is $h(a) \ne h(a')$.
\end{proof}

\begin{lemma}
If $|A| \le |B|$ and $|B| \le |A|$, then $|A|=|B|$.  In other words,
if there is an injection from $A$ to $B$, and an injection from $B$ to
$A$, then there is a bijection from $A$ to $B$.
\end{lemma}

\begin{proof}
This one is rather tricky.  It took 3 famous mathematicians to prove
what is now called the Cantor-Schroeder-Bernstein theorem.  You can
find it in Section 7.3 of Velleman. 
Basically, you have to construct the bijection by piecing together
parts of the two injections. 
\end{proof}

\subsection{Examples}

Using CBS makes it easier to prove certain sets are the same size:
instead of coming up with a bijection, you can come up with two
injections:
\begin{lemma}
\label{lm: interval-powerset}
$|(0,1)| = |P({\cal N})|$ where $P({\cal N})$ is the set of all subsets
of ${\cal N}$
\end{lemma}

\begin{proof}
We construct two injections, one in each direction. 
Here is an injection from $(0,1)$ to $P({\cal N})$.  For any given
real number, consider an expansion as an infinite sequence of binary
digits $b=0.b_0b_1b_2\ldots$ where each $b_i=0$ or $1$.  Define
$S_b=\set{i \mid b_i = 1}$.  Since any two reals differ in some binary
digit at some position $i$, they will map to different sets---one will
contain $i$ and one will not---so this is an injection. \\
\\
Here is an injection from $P({\cal N})$ to $(0,1)$.  Given
$S\subseteq{\cal N}$, define a real number $0.b_0b_1b_2\ldots \in
(0,1)$ as follows: $b_i = 3$ if $i \in S$, and $b_i = 7$ otherwise.
\end{proof}

One might think the first injection given above is a bijection, but it
isn't.  Some sets of natural numbers (\eg ${\cal N}$ itself) are not
``hit'' by the mapping: ${\cal N}$ would correspond to the real number
$0.11111\cdots = 1$ which is not in the interval at all.  And this is
not an isolated example.  It is much easier to work with pairs of
injections.

\begin{corollary}
$|\reals^+| = |P({\cal N})|$
\end{corollary}

This follows from Lemma \ref{lm: interval-powerset} and \ref{lm:
interval-reals}.

Exercise:  Show that $|\reals| = |P({\cal N})|$.
LTTR.

You can also show that ``$|A|\le |B|$'' and ``$|B| \ge |A|$'' are
equivalent: that is, there is an injection from $A$ to $B$ if and only
if there is a surjection from $B$ to $A$:
\begin{lemma}
$|A| \leq |B|$ iff $|B| \geq |A|$.
\end{lemma}
% [[[Seems like we need axiom of choice here, for the right-to-left
% direction.]]]

\subsection{Sets Between $\reals$ and ${\cal N}$?}

We have seen that there aren't any sets that are bigger than the
finite sets yet smaller than the countably infinite sets.
Are there any sets that are bigger than the countable infinite sets
yet smaller than $\reals$ and $P({\cal N})$?

It turns out that this is not so easy to answer.
Cantor posed this question in the 1870s, but it was not resolved until
1963, by Cohen.
He showed that there might or might not be such ``in-between''
sets---their existence is actually {\em independent\/} of the standard
axioms of set theory!
The Continuum Hypothesis is a new axiom saying that no such set exists.

\section{Other Infinite Sets}

We have seen that $|{\cal N}| < |{\cal R}|$.  
This fact follows from $|{\cal N}| \leq
|{\cal R}|$ and $|{\cal N}| \neq |{\cal R}|$.  The first statement
holds because there is an injection from ${\cal N}$ to ${\cal R}$;
namely, each natural number is mapped to itself.  The second statement
holds because we have proven that there is no bijection between ${\cal
  N}$ and ${\cal R}$.

In this sense, ${\cal N}$ and ${\cal R}$ are two different kinds of
infinities.  In fact, there are many types of infinities, and there is
a whole branch of mathematics to deal with them.  The most common
types of infinities are based on power sets.  (For now, we will denote
the power set of $S$ by ${\cal P}(S)$.)  These types of infinity are
denoted by the Hebrew letter aleph, $\aleph$, with a subscript.  A
bigger subscript implies a bigger type of infinity.  Here are the
first few:
\begin{eqnarray*}
\aleph_0 & = & |{\cal N}| \\
\aleph_1 & = & |{\cal P}({\cal N})| = |{\cal R}| \\
\aleph_2 & = & |{\cal P}({\cal P}({\cal N}))| = |{\cal P}({\cal R})| \\
        & \ldots
\end{eqnarray*}
Each new type of infinity is obtained by taking the power set of the
preceding type of infinity.
It is not immediately clear, however,
that sets of size $\aleph_2$ are really any larger than sets of size
$\aleph_1$, or more generally that taking the power set of $S$ gives a
larger set than $S$ itself.  This fact can be proven, however.

\begin{theorem}
For all sets $S$, $|S| < |{\cal P}(S)|$.
\end{theorem}

This implies that $\aleph_0 < \aleph_1 < \aleph_2 < \ldots$, and so
there is a whole infinite hierarchy of infinite sets!  
The statement generalizes that of Theorem \ref{th: powerset-uncountable}.
So we will prove it by generalizing the proof of that theorem, in
particular, the ``alternative proof'' using the idea of Russell's
Paradox.

\begin{proof}
We have to prove that $|S| \leq |{\cal P}(S)|$ and $|S| \neq |{\cal
P}(S)|$.

{\em $|S| \leq |{\cal P}(S)|$: } We must show that there exists an
injection $f: S \mapsto {\cal P}(S)$.  The function $f(a) = \{ a \}$
for all $a \in S$ is just such an injection.

{\em $|S| \neq |{\cal P}(S)|$: } The proof is by contradiction.
Assume for the purpose of contradiction that $|S| = |{\cal P}(S)|$.
Then there is a surjection $f: S \mapsto {\cal P}(S)$.  (In fact,
there is a bijection, but we do not need this fact.)  
To show a contradiction, we will define an item in ${\cal P}(S)$ that is not
covered by $f$; this will contradict the assertion that $f$ is a
surjection.  In particular, let $T = \{ a \in S | a \not\in f(a) \}$.  
The set $T$ is a subset of $S$, and so $T$ is an element of the
power set of $S$.  Since $f$ is a surjection, there must be an $a
\in S$ such that $f(a) = T$; fix such an $a$.
Now there are two cases: either $a \in T$ or $a \not\in T$.

{\em ($a \in T$): } By the definition of the set $T$, this implies
that $a \not\in f(a) = T$, a contradiction.

{\em ($a \not\in T$): } Now the definition of the set $T$ implies that
$a \in f(a) = T$, another contradiction.

The contradictions in both cases imply that our assumption was wrong;
therefore, $|S| \neq |{\cal P}(S)|$ and so $|S| < |{\cal P}(S)|$.
\end{proof}
\end{document}

We can construct many types of infinity using power sets, but what
about completely different types of infinity?  For example, is there
an infinite set $S$ that is larger than the natural numbers, but
smaller than the real numbers?  This question was posed by Cantor in
the 1870's and was not resolved for almost a century.

In 1900 David Hilbert posed 24 unsolved problems for the new century
and this was first on his list.  Hilbert conjectured that no such set
existed, and this conjecture became known as the Continuum
Hypothesis.

In 1963, Paul Cohen answered the question.  He did not prove that such
a set existed or did not exist, but rather showed that {\em both}
scenarios are consistent with the axioms of set theory.  
This has two bizarre consequences:
\begin{itemize}
\item Assuming set-theory is consistent, it is impossible to prove
  that the Continuum Hypothesis is false, {\bf and} it is impossible
  to prove the Continuum Hypothesis is true!
\item If set theory is consistent, you can make {\bf either}
  assumption about the Continuum Hypothesis into an axiom, and still
  have a consistent theory!
\end{itemize}

\end{document}








