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

\begin{document}

\mainlylecture
\lecture{notes17}{Lecture Notes}{April 6, 2000}

\begin{outline}

\forlecture{
{\bf Discuss exam.  Coverage. Ask about makeups.}
}

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.  Nevertheless, the
techniques we develop for dealing with infinite sets will be quite
useful later on in 6.045 when you learn about computability.

\section{Finite Sets vs. Infinite Sets}

Let's start by distinguishing finite sets from infinite sets.

\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 = f \circ g^{-1}$ is a bijection
  from $\seto{n}$ to $\seto{m}$.  No suppose $m > n$.
  Then by the pigeonhole principle $h$ maps two elements of
  $\seto{m}$ to the same element of $\seto{m}$, so is
  not a bijection.  This is a contradiction.  Similarly, if $n>m$, 
  then $h^{-1}$ (also supposed to be a bijection) maps two elements of
  $\seto{n}$ to the same element of $\seto{m}$.  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{lemma}
  If $n>m$, then there is no injection (and thus no bijection) from
  $\seto{n}$ to $\seto{m}$
\end{lemma}
\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$ was 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 bad example 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 initially
assumption that the lemma is not true must be false.  QED.
\end{proof}

\begin{defin*}
  A set is {\em finite} if there exists an $n \in {\cal N}$ such that
  $|S| = n$.
\end{defin*}

\begin{defin*}
A set is {\em infinite} if $|S| \ne n$ for any $n$.
\end{defin*}

These definitions imply that every set is either finite or infinite.
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.  Here is a more interesting
example: 

\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.  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}!

\section{Countable Sets}

A nice property of finite sets is that we can write out their elements
in a list.  For example, we can write out the set of integers between
1 and n as $\{ 1, 2, 3, \ldots, n \}$.  We can also express some
infinite sets in a list format:

\begin{eqnarray*}
{\cal N} & = & \{ 0, 1, 2, 3, \ldots \} \\
\mbox{even numbers} & = & \{ 0, 2, 4, 6, \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*}

Many familiar sets are countable: ${\cal N}$, the even numbers,
primes, integers modulo a constant $k$, etc.

The formal definition of a countable set 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$.

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 double check this definition:
\begin{lemma}
The set of even numbers is countable.
\end{lemma}
\begin{proof}
  The following is easily seen to be a bijection $\set{2,4,6,8,\ldots}
  \rightarrow {\cal N}:\ f(x)=x/2$.  
\end{proof}

Now lets look at some more complicated countability arguments.

\subsection*{The Integers}

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

\begin{proof}
  To prove that that the integers are countable, 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,
  etc.  This listing defines the desired bijection, e.g. $f(0) = 0$,
  $f(1) = 1$, $f(2) = -1$, $f(3) = 2$, etc. 
\end{proof}

This is the typical way to prove that a set is countable---just show
that you can list all of the elements.  This implicitly defines a
bijection with ${\cal N}$.  As noted above, we only have to prove that
a bijection $f$ exists; $f$ need not be a function that we can
actually compute.  In this case, however, $f$ can be written simply:

\[
f = \left \{
\begin{array}{ll}
- \frac{i}{2} & i \mbox{ even} \\
\frac{i+1}{2} & i \mbox{ 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 is incorrect: $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
properly ``defined'' at all).

\subsection*{The Half Integers}

Define the set $Z^{1/2}$ as follows:

\begin{eqnarray*}
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, $Z^{1/2}$ consists of all integers and all half
integers.  This set is countable.  We have written $Z^{1/2}$ above as
the union of two countable sets.  We can list all the elements of
$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}
Since $A$ and $B$ are countable, 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 are two complications.  First, sets $A$ and $B$ may contain
common elements, so an element should be omitted from the list if it
has already appeared.  Second, either or both sets may be finite.  If
at some point all elements of one set have been listed, continue
listing elements of the other set without interleaving.
\end{proof}

\subsection*{The 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{nooutline}
\begin{figure}[htbp]
\centerline{\includegraphics[height=2.5in]{figures/rationals}}
\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}
\end{nooutline}

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}

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}^+$.

\section{Uncountable Sets}

There would be little need for intuition and definitions about
countable sets if all sets were countable; unfortunately, many
important sets are not countable.  Sets that are not countable are
called {\em uncountable}.

\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
\]

This is not going to be so easy!  For example, where are we going to
stick in $\sqrt{2}$ and $\pi^{-173}$?  Later we will see clever ways
of listing the elements of some seemingly ``big'' sets like the
rational numbers, but for the real numbers we can actually prove that
no such listing exists.

We'll first work through the proof informally, and then write it up.
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...
                          ...etc...
\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!

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 every $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 a little bit 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 can not 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
sets are the ``same size.''  We write $|A|=|B|$ is there is a
bijection from $A$ to $B$.

\begin{lemma}
Let $(0,1)$ be the reals between 0 and 1.  Let $\reals^+$ be the
positive real numbers.  Then $|(0,1)|=|\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.


\subsection*{A Paradox}

Here is a set that appears to be both countable and uncountable!  This
is impossible, so one argument must be incorrect, but which one?

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.  In fact, for homework you will show
that a union of a countable number of countable sets is always
countable.

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{Other Infinite Sets}

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| \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 there exists a bijection $f: A \mapsto B$
\item $|A| < |B|$ iff $|A| \leq |B|$ and $|A| \neq |B|$
\item $|A| > |B|$ iff $|A| \geq |B|$ and $|A| \neq |B|$
\end{itemize}

The use of ``$\le$'' here is not an accident.  It turns out that we
have defined a partial order on sets!  Well, it is a partial order if
we interpret ``$=$'' as above: clearly two sets can have the same size
without being the same set!  Some of this partial order claim is easy
to see:
\begin{lemma}
The relation $\le$ defined above is reflexive.  That is, $|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}
The relation $\le$ defined above is transitive.  That is, $|A| \le
|B|$ and $|B| \le |C|$ implies $|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}

The last thing to prove about the relation is antisymmetry.  That is:
\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 an 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 the appendix of \emph{How to Read and Do Proofs}.
\end{proof}

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}
$|(0,1)|=P(\naturals)$ where $P(\naturals)$ is the set of all subsets
of $\naturals$
\end{lemma}
\begin{proof}
Here is an injection from $(0,1)$ to $P(\naturals)$.  For any given
real number, consider its 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(\naturals)$ to $(0,1)$.  Given
$S\subseteq\naturals$, 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 $\naturals$ itself) are not
``hit'' by the mapping: naturals 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.

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$.

\subsection*{A Hierarchy of Infinities}

We have already proved some things about this relation. F or example,
$|{\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.  (We will not prove the assertion on the
second line that the set of real numbers is the same size as the power
set of the natural numbers.)  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 proof of
the theorem is really convoluted; the main idea is drawn from
``Russel'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(\alpha) = \{
\alpha \}$ for all $\alpha \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 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 $R = \{ a \mid a \in S, a \not\in f(a)
\}$.  The set $R$ is a subset of $S$, and so $R$ 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) = R$.  Now there are two cases: either $a \in
R$ or $a \not\in R$.

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

{\em ($a \not\in R$): } Now the definition of the set $R$ implies that
$a \in f(a) = R$, 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}

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{outline}
\end{document}
