\documentstyle[12pt,twoside,amsfonts,amstex,psfig]{article}
\input{macros-course}

\begin{document}

\handout{notes-cardinality}{The Size of Sets}{March 30, 1998 (typos 4/1/98)}

\newcommand{\bij}{\mathop{\mbox{\rm bij}}}
\newcommand{\inj}{\mathop{\mbox{\rm inj}}}
\newcommand{\sur}{\mathop{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\iden}[1]{\text{id}_{#1}}
\newcommand{\clop}[1]{\mbox{{\rm \texttt{[}$0,#1$\texttt{)}}}}
\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}

\section{Sets of the Same Size: Bijections}
Counting is a theme throughout discrete mathematics: how many leaves in a
tree, minimal colorings of a graph, trees with a given set of vertices,
five-card hands in a deck of fifty-two, consistent rankings of players in a
tournament, stable marriages given boy's and girl's preferences, and so on.

A useful technique for determining the size of a set is to set up an exact
correspondence between the elements of the set and the elements of some
other set of known size.  For example, for any finite set $S$ with $n>0$
elements, we set up a correspondence between subsets of $S$ and binary
words of length $n$.  Since every computer scientist knows there are $2^n$
binary words of length $n$, she can conclude that there are also exactly
$2^n$ subsets of a set of size $n$.

To specify the correspondence, suppose the distinct elements of $S$ are
$s_1, s_2, \dots, s_n$.  Let each length $n$ binary word $b_1 b_2\dots
b_n$ correspond to the subset $T(b_1 b_2\dots b_n) ::= \set{s_i : b_i =
1}$.  So each length $n$ binary word, $b$, determines a unique subset
$T(b) \subseteq S$.  It is easy to see that distinct binary words
determine distinct subsets: if their $i$th bits differ, then one of the
corresponding subsets contains $s_i$ and the other doesn't --- that is,
$T$ is an \emph{injection}.  Also, every subset corresponds to the word
whose $i$th bit is 1 exactly when $s_i$ is in the subset --- that is, $T$
is a \emph{surjection}.  So, the mapping $T:\set{0,1}^n \to P(S)$ is a
\emph{bijection}.

Remember ``bijection'' is defined as follows:
\begin{defin}
Let $f$ be a function with domain $A$ and codomain $B$, that is, $f:A\to B$.
Define $f$ to be an \emph{injection} (also called ``one-to-one'') iff
\[f(a) = f(a') \implies a = a' \]
for all $a, a' \in A$.  The \emph{range} of $f$ is defined as
\[\ran{f} ::= \set{b \in B : b = f(a) \mbox{ for some a } \in A}.\]
Define $f$ to be a \emph{surjection} (also called ``onto'') iff $\ran{f} =
B$.  Define $f$ to be a \emph{bijection} iff $f$ is both an injection and
a surjection.
\end{defin}

Exact correspondences between infinite sets can be useful as well.  For
example, how does a single serial processor simulate a Java program which
spawns a growing number of parallel threads? --- by ``dovetailing'' the
computation of the threads.  Namely, at each interval of computation, the
serial processor picks a single thread to simulate.  Of course it won't do
for the serial processor simply to simulate some fixed number of threads
in a cycle, for then threads not in the cycle never get a turn.  For a
dovetailing strategy to work properly, every one of the growing number of
threads must get a growing number of turns as time goes on.

More precisely, we require that for every pair of nonnegative integers
$(n,m)$, there is an number, $f(n,m)$ such that the $n$th thread gets its
$m$th turn in the $f(n,m)$th time interval, and in every time interval
exactly one thread gets a turn.  So formally, a proper strategy is a
bijection $f:\naturals^2 \to \naturals$.  Since a thread can't have its
$m+1$st turn before it $m$th, the bijection $f$ also has to be increasing
in its second argument that is, $f(n,m_1) < f(n, m_2)$ whenever $m_1 <
m_2$.

There are many ways to define such a bijection.  For example, let $f(n,m)$
be the $m$th largest nonnegative integer which is divisible by $2^n$ and
not by $2^{n+1}$ .  A more uniform strategy arises by letting the
processor simulate threads in a cycle, but to add another thread to the
cycle each time around.  The bijection determined by this strategy turns
out to be a polynomial $f(n,m) ::= ((n+m)^2 + m - n)/2$.

So the correspondence above demonstrated
\begin{theorem}\label{n2n}
There is a bijection $f:\naturals^2 \to \naturals$.
\end{theorem}

\emph{Exercise}: Let $f(n,m) = ((n+m)^2 + m - n)/2$.

(a) List the eleven pairs of nonnegative integers $(n,m)$ such that
$f(n,m) \leq 10$.

(b) Describe in general how, given $k \in \nats$, to find a pair $(n,m)\in
\nats^2$ such that $f(n,m) = k$.

(c) Verify that $f$ is a bijection.
\medskip

\medskip

In these notes we'll demonstrate that using bijections to specify the size
of infinite sets yields a sensible theory of infinite set sizes --- yes
there will be more than one size of infinity --- but it's important to
notice from the start that there will be some dramatic contrasts between
size properties of finite and infinite sets.

For example, a proper subset of a finite set is always strictly smaller
than the whole finite set.  On the other hand, the set, $\ints$ of all
integers is the ``same size'' as the set, $\naturals$, of all natural
numbers, even though $\nats$ is a proper subset of $\ints$.  Namely, there
is a bijection betweeen the natural numbers and all the integers.  For
example, the function $f:\naturals \to \ints$ such that $f(n) ::= -n/2$
when $n$ is even, and $f(n) = (1 + n)/2$ when $n$ is odd, is a bijection.  In
fact we shall show below that this behavior determines infiniteness: a
set is infinite iff it has an bijection into proper subset of itself.

While it's pretty clear what is meant by ``the number of elements'' in a
finite set, it isn't so clear for infinite sets.  In fact, the definition
of ``finite'' depends on being able to count the number of elements in a
set in the first place.  So to avoid circularity, and especially to be
sure we're on firm ground when we handle infinite sets as well as finite
ones, let's be very careful in our definitions about the size of sets.
Before we define precisely what the size of a set may be, let's define the
more fundamental notion of ``same size'' we've discussed above.

\begin{defin}
We write $A \inj B$ to indicate that there is an injection from $A$ to
$B$.  Similarly, we write $A \sur B$ iff there is a surjection from $A$ to
$B$.  Finally, we write $A \bij B$ to indicate that there is a bijection
from $A$ to $B$.

Two sets $A$, $B$ are said to be of the \emph{same cardinality} iff $A \bij
B$.
\end{defin}

\section{Finite Sets}

One way to demonstrate that a set is finite, and in fact has $n$ elements,
is to find a bijection between it and some standard set of $n$ elements.
We'll use the set $\set{0,1,\dots,n-1}$, indicated by the
notation\footnote{This notation follows a common convention that when an
interval is denoted by its endpoints, square left bracket ``\texttt{[}''
indicates that the smaller endpoint is included in the interval, and
ordinary right parenthesis ``\texttt{)}'' indicates that the larger
endpoint is not included in the interval.}  ``$\clop{n}$,'' as the
standard set of size $n \in \naturals$.
\begin{defin}
For $n \in \naturals$, define $\clop{n} ::= \set{i \in \naturals : i < n}$.
\end{defin}
So by definition, $\clop{0} = \emptyset$.

\begin{defin}
A set, $S$, is said to be \emph{finite} iff $S \bij \clop{n}$ for some $n
\in \naturals$.  If $A$ is a finite set, the \emph{cardinality},
$\card{A}$, of $A$, is the least $n \in \naturals$ such that $A \bij
\clop{n}$.
\end{defin}
So if $A$ is finite, then $A \bij \clop{\card{A}}$ by definition of
$\card{A}$.

As a initial, simple ``sanity check'' of our technical definition of
cardinality, let's verify that a set of size zero is empty:
\begin{lemma}\label{empty0}
$\card{A} = 0 \iff A = \emptyset$.
\end{lemma}
\begin{proof}
($\Rightarrow$)
By definition, if $\card{A} = 0$, then there is a bijection $f:A \to
\clop{0}$.  But $\clop{0} = \emptyset$, and the only
function\footnote{Remember, a function $f:A \to B$ is, by definition,
\emph{total}.  That is, $f(a)$ is defined and $f(a) \in B$ for
\emph{all} $a \in A$.} from a set into the empty set is the function with
empty domain, that is, $A =\emptyset$.

($\Leftarrow$) The ``empty'' function from $\emptyset \to \emptyset$
satisfies the definition of bijection.  Since $\emptyset = \clop{0}$, we
have a bijection from the empty set to $\clop{0}$.  So according to the
definition of cardinality, $\card{\emptyset} = 0$.
\end{proof}

Since we are using the set of nonnegative integers less than $n$ as the
standard in the definition of cardinality $n$, we better be sure that in
fact this set has cardinality $n$.  This property seems obvious, and it
certainly is utterly familiar, but it does does not quite follow
immediately.

The definition says that the cardinality of the set of nonnegative
integers less than $n$ is the \emph{least} $m\in \naturals$ such that
there is a bijection from this set to $\clop{m}$.  This obviously implies
that $\card{\clop{n}} \le n$.  But is it possible that $\card{\clop{n}} <
n$?  In other words, is it possible that there is a bijection between the
nonnegative integers less than $n$ and those less than $m$ for some $m<n$?
Well of course not!  In fact, the following stronger fact indeed can be
proved:
\begin{lemma}\label{minjn}
$\clop{m} \inj \clop{n}$ iff $m \le n$.
\end{lemma}
The proof is by induction on $n$ and appears at the beginning of
Appendix~\ref{fincardprf}.

The remaining basic properties of finite cardinality are summarized in:
\begin{theorem}\label{masterfin}
If $B$ is a finite set, then
\[A \inj B \iff A \mbox{ is finite and } \card{A} \le \card{B}.\]
In particular,
\[A \bij B \iff A \mbox{ is finite and } \card{A} = \card{B}.\]
\end{theorem}

\begin{corollary}\label{finsub0}
Any subset of a finite set is finite.
\end{corollary}
\begin{proof}
If $A \subseteq B$, the ``inclusion'' function $\iden{AB}:A \to B$ where
$\iden{AB}(a) ::= a$, is an injection, so $A \inj B$.  So if $B$ is
finite, then by Theorem~\ref{masterfin}, $A$ is also finite.
\end{proof}

The statements in Lemma~\ref{minjn} and Theorem~\ref{masterfin} are pretty
obvious, and it's hard to imagine that anyone would be upset if we simply
took them as axioms from the start.  But these properties are in fact
logical consequences of the definition of cardinality, injections and
bijections.  We've placed their proofs in Appendix~\ref{fincardprf} to
illustrate this kind of reasoning from first principles.  The proofs break
down into a series of elementary Lemmas, but actually take several pages
to work out.  It isn't necessary to look at Appendix~\ref{fincardprf} to
understand the rest of these notes.

We assume below that the reader knows the basic properties
of bijections, injections, and surjections.  The main properties used are:
\begin{itemize}

\item Composition of functions is an associative operation:
\[f \circ (g \circ h) = (f \circ g) \circ h.\]

\item The relation, $\bij$, is an equivalence relation on sets.

\item The relations $\inj$ and $\sur$ are transitive.

\item $A \inj B$ iff $B \sur A$.
\end{itemize}
Appendix~\ref{bijprops} provides a review of the definitions and proofs of
these properties.

\section{Inclusion-Exclusion}
Now we can exhibit yet another proof of the principle of
Inclusion-Exclusion.  This one is kind of elegant.

\begin{lemma}\label{disju}
If $A$ and $B$ are disjoint finite sets, then
$\card{A \union B} = \card{A} + \card{B}$.
\end{lemma}
\begin{proof}
Since $A$, $B$ are finite, there are bijections $f:A \to \clop{\card{A}}$
and $g:B \to \clop{\card{B}}$.  Since $A$ and $B$ are disjoint, we can
define a function $h$ on $A \union B$  where $h(a) ::= f(a)$ for
$a \in A$, and $h(b) ::= g(b) + \card{A}$ for $b \in B$.  Then $h:A\union
B \to \clop{\card{A} + \card{B}}$ is a bijection, so $\card{A \union B} =
\card{A} + \card{B}$ by Theorem~\ref{masterfin}.
\end{proof}

\begin{lemma}\label{b-a}
For any set, $A$, and finite set, $B$,
\[\card{B - A} = \card{B} - \card{A \intersect B}.\]
\end{lemma}
\begin{proof}
For any sets $A, B$, we have $B = (B - A) \union (A \intersect B)$.
Moreover, $(B - A)$ and $A \intersect B$ are disjoint subsets of $B$.  Now
if $B$ is finite, then by Corollary~\ref{finsub0}, so are $(B - A)$ and $A
\intersect B$.  Hence, by the previous Lemma~\ref{disju},
\[\card{B} = \card{B - A} + \card{A \intersect B}.\]
\end{proof}

\begin{theorem}(Inclusion-Exclusion)
For finite sets $A,B$,
\[\card{A \union B} = \card{A} + \card{B} - \card{A \intersect B}.\]
\end{theorem}
\begin{proof}
For any sets $A,B$, we have $A \union B = A \union (B - A)$;
also $A$ and $B - A$ are disjoint.
So for finite $A,B$, the two previous Lemmas~\ref{disju} and~\ref{b-a} imply
\[\card{A \union B} = \card{A} + \card{B - A}
   = \card{A} + (\card{B} - \card{A \intersect B}).\]
\end{proof}

\textbf{Notation}: We write $A \subset B$ to indicate that $A$ is a proper
subset of $B$, that is, $(A \subseteq B)$ and $A \neq B$.

\begin{corollary}\label{propsub}
If $B$ is a finite set and $A \subset B$, then $A$ is finite and $\card{A}
< \card{B}$.
\end{corollary}
\begin{proof}
Since $B$ is finite, so are $A$ and $B-A$ by Corollary~\ref{finsub0}.
Since $A \subset B$, we have $B - A \neq \emptyset$, so $\card{B-A} > 0$
by Lemma~\ref{empty0}.  Also, $A \intersect B = A$.  Now by
Lemma~\ref{b-a},
\[0 < \card{B - A} = \card{B} - \card{A \intersect B} = \card{B} - \card{A}.\]
\end{proof}


\section{Infinite Sets}
The most familiar example of an infinite set is probably the nonnegative
integers, $\naturals$.  Let's check that $\naturals$ is infinite according
to our definitions.  Actually, we'll prove something slightly stronger: a
set is infinite iff there is an injection of the nonnegative integers into
the set.  This means that $\nats$ is the ``smallest'' possible infinite
set.

\begin{defin}
A set is said to be \emph{infinite} iff it is not finite.
\end{defin}

\begin{theorem}\label{inf<->Ninj}
A set $A$ is infinite set iff $\naturals \inj A$.
\end{theorem}
\begin{proof}
($\Rightarrow$) We define a sequence of distinct elements $a_1, a_2, \dots,
a_n, \dots$ recursively.  Since $A$ is infinite, it cannot be empty, so
there is an element in $A$.  Let $a_1$ be this element.  To define
$a_{n+1}$, let $f:\clop{n}\to A$ be defined by the rule $f(k) ::= a_{k+1}$
for $0 \le k < n$.  Since the $a_i$ for $i \le n$ are distinct, we know
that $f$ is an injection.  Now if $\ran{f}=A$, then $f$ would be a
bijection, contradicting the fact that $A$ is infinite.  So there is an
element in $A-\ran{f}$; let $a_{n+1}$ be this element.

Now define $g:\naturals \to A$ by the rule that $g(m) ::= a_{m+1}$.  Since
the elements of the sequence of $a_i$'s are distinct, $g$ is an injection.
Hence, $\naturals \inj A$.

($\Leftarrow$) Suppose for contradiction that $A$ is finite, so $A \inj
\clop{\card{A}}$.  But $\naturals \inj A$, hence $\naturals \inj
\clop{\card{A}}$ because $\inj$ is transitive (\emph{cf.}
Appendix~\ref{bijprops}.)  That is, there is an injection $f:\naturals \to
\clop{\card{A}}$.  Now the restriction of $f$ to the domain
$\clop{\card{A}+1} \subset \naturals$ is an injection from
$\clop{\card{A}+1}$ to $\clop{\card{A}}$, contradicting Lemma~\ref{minjn}.
\end{proof}

It's important to notice that we have only said that there is an
\emph{inj}ection from the nonnegative integers into any infinite set,
\emph{not} that there is a \emph{bij}ection.  In the 1870's, the
mathematician Georg Cantor made the dramatic discovery that not every
infinite set can be put in exact correspondence with the nonnegative
integers --- there may not be a bijection.  We'll prove this in
Section~\ref{diagsec}.

Here is another characterization of infiniteness we mentioned earlier.

\begin{theorem}\label{fininjbij}
A set is infinite iff there is an injection from the set to a proper
subset of itself.
\end{theorem}
\begin{proof}
($\Leftarrow$) We have an injection $f:A \to A$ with at least one element
$a \in A - \ran{f}$.  Define $g:\naturals \to A$ recursively: $g(0) ::=
a$, and $g(n+1) ::= f(g(n))$.  We claim $g$ is an injection, which implies
that $A$ is infinite by the previous Theorem~\ref{inf<->Ninj}.

Suppose to the contrary that $g$ is not an injection.  Then there must be
a least $j_0 \in \naturals$ such that $g(j_0) = g(j_1)$ for some $j_1 >
j_0$.  Note that $g(j) \in \ran{f}$ for $j >0$ by definition.  Since $g(0)
= a \not\in \ran{f}$, we know in particular that $g(0) \neq g(j)$ for
all $j > 0$.  So $j_1 > j_0> 0$.  Now we have $f(g(j_0-1)) = g(j_0) =
g(j_1)= f(g(j_1-1))$, and since $f$ is an injection, we conclude that
$g(j_0-1) = g(j_1-1)$, contradicting the minimality of $j_0$.
\end{proof} 

\textbf{Exercise}.  Prove the left-to-right direction of
Theorem~\ref{fininjbij}.  \hint Corollary~\ref{propsub}.

\iffalse

\textbf{Solution:}  

($\Leftarrow$) Suppose $A$ is finite, and $f:A \to A$ is an injection.
Let $f_1$ be $f$ with its codomain restricted to $\ran{f}$.  That is,
$f_1:A \to \ran{f}$ where $f_1(a) = f(a)$ for all $a \in A$.  Now $f_1$ is
a bijection, so $\card{\ran{f}} = \card{A}$.  But $\ran{f} \subseteq A$,
so by Corollary~\ref{propsub}, $\ran{f} = A$.  Hence $f$ is also a
surjection.

\fi

Negating both sides of the ``iff'' in Theorem~\ref{fininjbij} gives an
immediate, but informative Corollary:
\begin{corollary}
A set is finite iff every injection from the set to itself is also a bijection.
\end{corollary}


\section{Schr\"{o}der-Bernstein Theorem}
If the sizes of two finite sets are each less than or equal to the other,
then the sets are the same size.  In other words, the ``smaller than''
relation is \emph{symmetric}, at least on finite sets.  We wouldn't be
happy with our interpretation of ``smaller than'' unless it was symmetric
on infinite sets as well as finite ones, and it is.

We've been interpreting ``$A$ is smaller than $B$'' as $A \inj B$.  So we
can formulate the Symmetry property precisely as:
\begin{theorem}
(Schr\"{o}der-Bernstein) [$A \inj B$ and $B \inj A$] iff $A \bij B$.
\end{theorem}

\textbf{Exercise}.  Show that the Schr\"{o}der-Bernstein Theorem for
finite $A,B$ follows directly from Theorem~\ref{masterfin}.
\medskip

The direct proof of the previous exercise depends heavily on properties of
finite sets, so it will not extend to infinite sets.  Instead, we present
the original elegant proof, which works equally well for finite and
infinite sets.

\begin{proof}
($\Leftarrow$) If $A \bij B$ then $A \inj B$ and $A \sur B$ by
definition.  But $A \sur B$ iff $B \inj A$.

($\Rightarrow$) Suppose there is an injection $f:A \to B$ and an injection
$g:B \to A$.  We show how to piece together portions of $f$ and $g$ into a
bijection $h:A \to B$.

We'll assume for convenience that $A$ and $B$ are disjoint (see the
Exercise below).  Now we treat the elements of $A$ and $B$ as the vertices
of a bipartite digraph.  (The graphs we've considered up to now have been
finite.  This one will be infinite whenever $A$ or $B$ is infinite.)  The
edges are
\[E ::= \set{(a,f(a)) : a \in A} \union \set{(b,g(b)) : b \in B}.\]
The graph is illustrated in Figure~\ref{fig:SB}.  Two connected elements
are pictured in Figure~\ref{fig:SB} as having a zig-zag path between them.

\begin{figure}[htbp]
\centerline{\psfig{figure=/figures/sb1.eps,height=2.5in}}
\caption{\em
Sets $A$ and $B$ with injections $f:A \to B$ and $g:B \to A$.}
\label{fig:SB}
\end{figure}

Notice that because $f$ and $g$ are functions, each vertex has out-degree
one.  This implies there is a unique infinite path starting at each
vertex.  Also, a vertex has in-degree one iff it is in the range of $f$ or
$g$; otherwise it has in-degree zero.  This implies there is a unique
maximal path, which may be finite or infinite, into each vertex.  So we
can partition the vertices into four kinds of components, with no edges
between distinct components:
\begin{enumerate}
\item\label{startA} a one-way infinite simple path starting at a vertex in
$A$,

\item\label{startB} a one-way infinite simple path starting at a vertex in
$B$,

\item\label{simcyc} a simple cycle,

\item\label{2way} a simple path which is infinite in both directions (all
its vertices are degree two).

\end{enumerate}
These four possibilities are illustrated in Figure~\ref{fig:4components}.

\begin{figure}[htbp]
\centerline{\psfig{figure=/figures/sb2.eps,width=\textwidth,angle=-90}}
\caption{\em The four kinds of connected components.}
\label{fig:4components}
\end{figure} 

In case~\ref{startA} of a one-way path starting in $A$, the function $f$
defines a bijection from the $A$-vertices on the path to the $B$-vertices
on the path.  Similarly, in case~\ref{startB} of a one-way path starting
in $B$, the function $g$ defines a bijection from the $B$-vertices to the
$A$-vertices on the path.  In cases~\ref{simcyc} and~\ref{2way} of a
finite cycle or two-way infinite path, both $f$ and $g$ define bijections
between the $A$-vertices and the $B$-vertices on the path.

So we simply define $h$ component by component.  Except for
case~\ref{startB}, the function $f$ defines on bijection from $A$-vertices
to $B$-vertices in a component, so define $h(a) ::= f(a)$ when $a$ is not
in a component with a start vertex in $B$.  In case~\ref{startB}, $g$
defines a bijection from the $B$-vertices to the $A$-vertices on the path,
so its inverse $g^{-1}$ is a uniquely defined bijection from the $A$
vertices to the $B$-vertices.  So we simply define $h(a) ::= g^{-1}(a)$
when $a$ is in a component with a start vertex in $B$.

Since $h$ is a bijection from the $A$-vertices to the $B$-vertices in each
component, and the components are disjoint, $h$ is the desired bijection
from $A$ from to $B$.
\end{proof}

\textbf{Exercise}:  Prove that for any sets $A, B$, there are disjoint
sets $A', B'$ such that $A' \bij A$ and $B' \bij B$.
\medskip


\iffalse
HERE ARE TWO FURTHER PROOFS, SOMEWHAT MORE FORMAL AND MUCH MORE CUMBERSOME.

\begin{defin}
For any function $f:A \to A$, define $f^{(n)}:A \to A$ for $n\in \naturals$
recursively as follows: $f^{(0)} ::= \iden{A}$, $f^{(n+1)} ::= f \circ f^{(n)}$.
\end{defin}

We're going treat the set $A$ as the vertices of a simple graph.  (The
graphs we've considered up to now have been finite.  This one will be
infinite when $A$ is.)  Two vertices $a_1, a_2 \in A$ are defined to be
adjacent iff
\[a_1 = g(f(a_2)) \mbox{ or } a_2 = g(f(a_1)).\]
Two connected elements would be pictured in Figure~\ref{fig:SB} as having a
zig-zag path between them.

Notice that because $f$ and $g$ are bijections, the connected components
of this graph are either simple cycles or infinite simple paths.  The
infinite simple path components are of two kinds: those which are infinite
in both directions, meaning they consist entirely of vertices of degree
two, and those which are infinite in one direction, meaning they contain a
unique vertex of degree one, called the \emph{start} vertex, and all the
other vertices have degree two.  Notice that except for some of the start
vertices, all the other vertices are in the range of $g$.

Define $h:A \to B$ as follows: if the connected component of vertex $a$
has a start vertex which is not in the range of $g$, then let $h(a) ::=
f(a)$.  Otherwise, $a$ must be in the range of $g$, and since $g$ is an
injection, there is a unique $b \in B$ such that $a = g(b)$; let $h(a) ::=
b$ in this case.  We claim $h$ is the desired bijection.

To prove that $h$ is a surjection, suppose $b \in B$.  We want to prove
that $b \in \ran{h}$.  There are two cases:
\begin{enumerate}
\item Suppose $b \not\in \ran{f}$.  Then $g(b)$ must be a start vertex
$a$, and of course $a = g(b) \in \ran{g}$, so $h(a) = b$ by definition.

\item Suppose $b \in \ran{f}$.  So $b = f(a)$ for some $a \in A$.  Now in
one case $h(a)$ is defined to be $f(a) = b$, and in the other case
$h(g(b)) = b$.  In either case, $b \in \ran{h}$.
\end{enumerate}
So in every case, $b \in \ran{h}$ as required.

To prove $h$ is an injection, we use the fact that $g(h(a))$ is always in
the same connected component as $a$, because in one case $h(a)$ is defined
to be $f(a)$, so $g(h(a)) = g(f(a))$ is actually adjacent to $a$, and in
the other case $g(h(a))$ is actually equal to $a$.

Now suppose $h(a) = h(a')$.  We want to prove that $a = a'$.

Since $h(a) = h(a')$, obviously $g(h(a)) = g(h(a'))$, and so $a,
g(h(a)), g(h(a'))$ and $a'$ are all in the same connected component.
Now there are two cases:
\begin{enumerate}
\item $h = f$ on the connected component of $a$ and $a'$.  So $f(a) = h(a)
= h(a') = f(a')$, and since $f$ is an injection, $a = a'$.

\item $g \circ h$ is the identity function on the connected component of $a$ and $a'$.
So $a = g(h(a)) = g(h(a')) = a'$.
\end{enumerate}
So in both cases $a = a'$ as required.

\end{proof}


A MORE ALGEBRAIC VERSION OF THE PROOF:

($\Rightarrow$) Suppose there is an injection $f:A \to B$ and an injection
$g:B \to A$.  So $g$ is an injection, and must have a left inverse $l:A\to
B$ (\emph{cf.}  Appendix~\ref{bijprops}, Lemma~\ref{leftinv}).  We show
how to piece together portions of $f$ and $l$ into a bijection $h:A \to
B$.

Define the \emph{orbit} of an element $a \in A$ to be
\[\mbox{orbit}(a) ::= \set{(g \circ f)^{(n)}(a) : n \in \nat}.\]
Say that an element $a \in A$ is an $f$-element iff $a \in
\mbox{orbit}(a_0)$ for some $a_0 \not\in \ran{g}$.

The orbit situation is illustrated in Figure INSERT FIGURE~/ref {orbit}
HERE.

It follows directly from the definition of $f$-element that $a$ is an
$f$-element iff $(g \circ f)(a)$ is an $f$-element.  Also, if $a$ is not
an $f$-element, then $a \in \ran{g}$.

Define $h:A \to B$ so that $h(a) ::= f(a)$ when $a$ is an $f$-element, and
$h(a) ::= l(a)$ otherwise.  We claim $h$ is a bijection.

To prove $h$ is an injection, say $h(a) = h(a')$.  We want to prove that
$a = a'$.  There are three cases:
\begin{enumerate}
\item
Suppose $a, a'$ are both $f$-elements.  Then $f(a) = h(a) = h(a') =
f(a')$, and since $f$ is an injection, $a = a'$.

\item Suppose neither $a$ nor $a'$ is an $f$-element.  Then we know both
are in $\ran{g}$, that is, $a = g(b)$ and $a' = g(b')$ for some $b, b' \in
B$.  So 
\[b' = l(g(b')) = l(a') = h(a') = h(a) = l(a) = l(g(b)) = b.\]
Hence, $a = g(b) = g(b') = a'$.

\item Exactly one of $a$ and $a'$ is an $f$-element.  Say $a$ is the
$f$-element and $a'$ is not.  Now we know that $a' \in \ran{g}$, so $a' =
g(b')$ for some $b' \in B$.  Also, $(g \circ f)(a)$ is an $f$-element, so
\[(g \circ f)(a) \neq a'.\]
But
\[(g \circ f)(a) = g(f(a)) = g(h(a)) = g(h(a')) = g(l(a')) = g(l(g(b'))) =
g(b') = a',\]
a contradiction.  So this case never occurs.
\end{enumerate}
We have shown that $h$ is an injection.

To prove that $h$ is a surjection, suppose $b \in B$.  We want to prove
that $b \in \ran{h}$.  There are two cases:
\begin{enumerate}
\item
Suppose $g(b)$ is an $f$-element.  That is, $g(b) = (g \circ f)^{(n)}(a)$
for some $a \in A - \ran{g}$ and $n \in \nat$.  But $g(b)$ is in $\ran{g}$
and $a$ is not, so $a\neq g(b)$ and $n>0$.  Hence, the $f$-element $a'::=
(g \circ f)^{(n-1)}(a)$ exists, and $g(b) = (g \circ f)(a') = g(f(a'))$.
But $g$ is an injection, so $b = f(a')$, and since $a'$ is an $f$-element,
$h(a') = f(a')$.  Therefore, $b = h(a')\in\ran{h}$.

\item Suppose $g(b)$ is not an $f$-element.  Then $h(g(b)) = l(g(b)) = b$,
so $b \in \ran{h}$.
\end{enumerate}
This shows that $h$ is also a surjection.
\end{proof}
\fi

\section{Countable Sets}\label{countable}
The Schr\"{o}der-Bernstein Theorem makes it much easier to prove that
there are bijections between sets.  For example, let $\rationals$ denote
the rational numbers.  Define $h: \ints^2 \to \rationals$ so that $h(m,n)
::= m/n$ when $n \neq 0$, and $h(m,0) ::= 1$.  Clearly $h$ is a
surjection, so $\ints^2 \sur \rationals$, and hence
\[\rationals \inj \ints^2.\]
Conversely, we know $\nats \bij \ints$, which implies
\[\ints^2 \bij \nats^2.\]
Also, we showed at the outset in Theorem~\ref{n2n} that
\[\nats^2 \bij \nats,\]
so altogether we conclude
\[\rationals \inj \nats.\]
On the other hand, $\nats \subset \rationals$, so $\nats \inj \rationals$.
Therefore, by Schr\"{o}der-Bernstein
\begin{theorem}
$\nats \bij \rationals$.
\end{theorem}

The rationals are densely spread over the entire real line, and so appear
more numerous than the nonnegative integers, which are sparsely spread
over half the line.  Nevertheless, we have deduced, indirectly but
undeniably, that there is an exact correspondence between these sets, so
the rationals are not in fact more numerous.

\begin{defin}
A set $A$ is \emph{countably infinite} iff $\naturals \bij A$.  It is
\emph{countable} iff it is finite or countably infinite.
\end{defin}

For example, the results above show that $\nats, \ints, \rationals,
\ints^2, \nats^2$ are all countably infinite.

The reason for the name is that we can ``count'' one after another through
the elements of a countable set so that every element of the set is
eventually counted.  That is, if $f$ is a bijection from the nonnegative
integers to a set, we can count each of the elements of the set in the
order $f(0), f(1), \dots$.  Other examples of countably infinite sets are

\begin{eqnarray*}
\mbox{even numbers} & = & \{ 0, 2, 4, 6, \ldots \} \\
\mbox{powers of two} & = & \{ 1, 2, 4, 8, \ldots \} \\
\mbox{primes} & = & \{2, 3, 5, 7, 11, \ldots \}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%F97
The bijection we described above between the nonnegative integers and the
integers, namely, $f(n) ::= -n/2$ when $n$ is even, and $f(n) = (1+ n)/2$ when
$n$ is odd, corresponds to counting the integers in the order
\[0, 1, -1, 2, -2, 3, -3, 4, -4, \dots.\]

This is the typical way to prove that a set is countable --- just list the
elements in the order they should be counted in.  This implicitly defines
a bijection with $\nats$.  Note that we only have to prove that a
bijection $f$ exists; it needn't have a simple description like the $f$
above.  It needn't even be a function that we can actually compute.

This 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, \dots, 1, 2, 3, \dots.\]
The problem is that the ``$\dots$'' in the middle of the list represents
the infinite list of negative integers from -4 on down.  As a result, we
never actually finish counting down, so we never get around to starting a
count of the positive integers.  More precisely, if $g(n)$ is defined to
be the $n$th number in this list, then $g(n)$ is not positive for any $n
\in \nats$.  This means that the function $g$ defined is not a bijection
to \emph{all} the integers, only to the nonpositive ones.

This counting approach offers a direct way, for example, to prove that the
positive rationals are countable.  As a first attempt, we might try to
count the positive rational numbers in the following order:
\[
\frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \dots,
\frac{1}{2}, \frac{2}{2}, \frac{3}{2}, \dots,
\frac{1}{3}, \frac{2}{3}, \frac{3}{3}, \dots
\]

A fixable problem with this list is that each rational is counted many
times.  We need to omit from the list 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$.

The killer problem is that we used ``$\dots$'' again 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, the $n$th element of the list above is the
integer $n$.  There is no $n \in \nats$ such that $1/2$ --- or any other
noninteger rational number for that matter --- appears as the $n$th
element.  So we have not counted all the positive rationals and have not
implicitly defined the required bijection.  We need to list the rational
numbers in a completely different order to make the proof work.

Having recognized the problem, there is a simple solution: 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 A dovetailing order to count the positive rationals.}
\label{fig:rationals}
\end{figure}

The ordering technique used in the proof and indicated in
Figure~\ref{fig:rationals} is just the kind of dovetailing described
earlier for simulation of Java threads.  We can also 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 way we showed that
the positive rationals are countable was a special case of the above
proof.

%%%%%%%%%%%%%%%F97

\textbf{Exercise}.  Prove that $A$ is countable iff $A \inj \nats$.

\textbf{Exercise}.  Prove that if $A_0, A_1, \dots$ is a sequence of
countable sets, then so is $\union_{i=0}^{\infty} A_i$.

\textbf{Exercise}.  Suppose $A_0 \bij A_1$ and $B_0 \bij B_1$.

(a)  Give a counterexample to the claim that
\[A_0 \union B_0\ \bij\ A_1 \union B_1.\]

(b) Show that the claim holds if at least one of $A_0$ and $B_0$ is infinite.


\section{The Continuum}
The real numbers, $\reals$, are sometimes, dramatically, referred to as
the \emph{continuum}.  We'll examine how they compare in size to some
other sets.

Every real number is the least upper bound of the set of rationals less
than it.  That is, $\mbox{lub}:P(\rationals) \to \reals$ is a surjection,
and therefore $\reals \inj P(\rationals)$.  But we showed in
Section~\ref{countable} that $\nats \bij \rationals$, which implies
$P(\nats) \bij P(\rationals)$, and altogether we conclude
\[\reals \inj P(\nats).\]

On the other hand, it's easy to find a surjection from the reals to the
sets of nonnegative integers.  For example, let $1^n$ denote a sequence of
$n$ consecutive 1's.  Then the function $f:\reals
\to P(\nats)$ where
\[f(r) ::= \set{n\in \nats : \mbox{ the digits $21^n2$
occur in the infinite decimal expansion of $r$}}\]
is a surjection.  So
$\reals \sur P(\nats)$, implying
\[P(\nats) \inj \reals.\]
Therefore, by Schr\"{o}der-Bernstein
\begin{theorem}\label{RbijN}
$\reals \bij P(\nats)$.
\end{theorem}
To appreciate the value of the Schr\"{o}der-Bernstein Theorem, the reader
can try directly contructing a bijection between the reals and $P(\nats)$.

A genuinely remarkable consequence of our definitions is that the real
line is the same size as the two-dimensional plane:
\begin{theorem}
$\reals^2 \bij \reals$
\end{theorem}
\begin{proof}
By the previous Theorem~\ref{RbijN}, all we need to show is that
\[P(\nats) \bij P(\nats)^2.\]
But that's easy: map $A \subseteq \nats$ to the pair of sets
\[(\set{n: 2n \in A}, \set{n: 2n+1 \in A}).\]
\end{proof}

This Theorem stands in dramatic contrast to a geometric picture of the
infinitely thin line with zero area versus the plane with its infinite
area.  Perhaps this violation of geometric intuition\footnote{Geometric
intuition can be substantially restored: injections from the plane into
the line have to be weird --- they can't be even piecewise continuous, for
example.} accounts for continued submissions to mathematics journals of
crank proofs that there are more points in two dimensions than in one
(\emph{cf.} Hodges, Wilfred, ``An Editor Recalls Some Hopeless Papers,''
\emph{Bulletin of Symbolic Logic}, March, 1998, v4,\#1).

\section{Diagonal Arguments}\label{diagsec}


%%%%%%%%%%%%F97

There would be little need for intuition and definitions about countable
sets if all sets were countable.  Many important sets turn out not to be
countable.  Sets that are not countable are called {\em uncountable}.

\begin{theorem}
The set 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
\]

But wait a minute!  All we're doing is listing the reals with finite
decimal expansion.  That doesn't even include all the rational numbers.
Where are we going to stick in $\sqrt{2}, \pi, pi^{-173}, \pi^e,$ all other numbers
with nonrepeating expansions like
\[0.1010010001000010\dots,\]
\emph{etc.}?  There just isn't any way to do it.

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 $\reals$ is countable.  This means that there
exists a bijection $f:\nats \to \reals$.  We can then make a
list of all the real numbers that looks something like the one shown
below. 

\begin{verbatim}
                    f(0) =  76.5430000000...
                    f(1) = 163.7777777777...
                    f(2) =   2.7878787878...
                    f(3) =  -1.1121231234...
                    f(4) =   3.1415926535...
                    f(5) = -15.3727323928...
                          ...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 digits on the diagonal starting at the
decimal point in the above table, $0.577192\ldots$.  Here is the same
table with extra spaces inserted to highlight this diagonal sequence:
\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}
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 $r$ differs from $f(0)$ 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(n)$ differs from $r$ in the
$(n+1)$-st position.  So for all $n$, $f(n)$ is not equal to $r$.
This implies that the real number $r$ does not appear anywhere in our
list!

Actually there is an irritating hole in this argument.  We have shown that
$r$ has a decimal expansion that differs from the decimal expansion of
$f(n)$.  But real numbers can have more than one decimal expansion: for
example, $1 = 0.999\ldots$.  So the fact that some expansion of $r$
differs from some expansion of $f(n)$ does not guarantee $r \neq f(n)$!
It might actually happen that $r = f(n)$ had we allowed in the
construction that the $n$th digit of $r$ differed from the $n$th digit of
$f(n)$ by 1 or 9.  But we were careful not to allow this.  Our
construction ensures that $r$ actually differs from $f(n)$ by at least $4
\cdot 10^{-(n+1)}$.  For example, $1.0002999\ldots$ differs from
$1.0007000\ldots$ by $4 \cdot 10^{-4}$.

Now since the reals are not countable, it is not true that $\reals \inj
\nats$, but since the nonnegative integers are a subset of the reals, we have
$\nats \inj \reals$.  Now it makes sense to say that the set of nonnegative
integers is strictly smaller than the set of reals.
\begin{defin}
A set $A$ is \emph{strictly smaller} than a set $B$, in symbols,
\[A \ll B,\]
iff $A \inj B$ and not $B \inj A$
\end{defin}


Here is how the argument above might be written as a formal proof without
mentioning the table and its diagonal:

\begin{proof}
We must show that there is no bijection $f: \nats \to \reals$.  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!

%%%%%%%%%%%%%%%%%%%%F97


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.



%%%%%%%F97

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

\textbf{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 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. \qed

\textbf{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. \qed

The first argument is incorrect;
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, in an earlier exercise we already
observed that a union of a countable number of countable sets is always
countable.

%%%%%%%%%%F97

\medskip
There is a nonpictorial version of the diagonal argument which is both
simpler and more general, although maybe not as intuitive.

\begin{lemma}\label{Df}
For any set $S$ and function $f: S \to P(S)$, let 
\[\mbox{Diag}(f) ::= \set{s\in S: s \not\in f(s)}.\]
Then $\mbox{Diag}(f) \not \in \ran{f}$.
\end{lemma}
\begin{proof}
By contradiction.  Suppose that $\mbox{Diag}(f) \in \ran{f}$, i.e., $\mbox{Diag}(f) = f(s_0)$
for some $s_0 \in S$.  Then by definition of $\mbox{Diag}(f)$,
\[s \in f(s_0) \iff s \in \mbox{Diag}(f) \iff s \not\in f(s)\]
for all $s \in S$.  So letting $s = s_0$, we conclude
\[s_0 \in f(s_0) \iff s_0 \not\in f(s_0),\]
a contradiction.
\end{proof}

\begin{theorem}(Cantor)
For every set $S$,
\[S \ll P(S).\]
\end{theorem}
\begin{proof}
The singleton function $g: S \to P(S)$ where $g(s) ::= \set{s}$, is an
injection, so $S \inj P(S)$.  By Lemma~\ref{Df}, it is not the case that
$S \sur P(S)$, so it must not be the case that $P(S) \inj S$.
\end{proof}

So Cantor's Theorem implies that we can keep finding bigger infinities:
\[\naturals\ \ll P(\naturals) \ll P(P(\naturals)) \ll P(P(P(\naturals))) \ll \dots.\]
But there are more: let $Q ::= \union_{i=0}^{\infty} P^i(\nats)$, then
every set $P^i(\nats) \subset Q \ll P(Q)$, so $P(Q)$ is strictly larger
than every set in the sequence!

\section{Set Theory}
Another important property we would expect of a ``smaller than''
relation is Totality, which we can state precisely as
\begin{claim}\label{total-claim} (Totality)
For any sets $A$ and $B$, either $A \inj B$ or $B \inj A$.
\end{claim}
This claim follows easily from Theorem~\ref{inf<->Ninj} if at least one of
$A$ or $B$ is countable.  However, it is far from obvious in general.  In
fact the only way to prove it requires sophisticated principles of the
theory of infinite sets such as the Well-ordering Axiom.  The
Well-ordering Axiom says that, not only $\nats$, but \emph{every} set can
be ordered in a way which ensures that every nonempty subset of the set
has a least element.

There is another question about set size which was raised by Cantor when
he first developed his theory of cardinality.  By Cantor's Theorem, we
know $P(\naturals)$ is strictly larger than the smallest infinite set,
$\nats$.  Is $P(\naturals)$ the next smallest set, or could there be some
set of size strictly between $\naturals$ and $P(\naturals)$?  Cantor
thought not, but was unable to prove it.  Using the fact that
$P(\naturals) \bij \reals$, he formulated the question as:

\textbf{The Continuum Hypothesis}. For every set $S$,
\[S \inj \reals \implies 
   [S \mbox{ is countable or } S\ \bij\ \reals].\]

It took almost a century to discover the remarkable result that there is
no way to prove or disprove the Totality Claim or the Continuum
Hypothesis.  It is consistent with the other more basic axioms of Set
Theory --- known as Zermelo-Frankel Set Theory, or \emph{ZF} for short ---
to assume the Well-ordering Axiom and hence Totality, and in practice
essentially all mathematicians do accept Well-ordering as a fundamental
axiom.  But in 1962, Paul Cohen astonished the mathematical world by
showing how to construct a mathematical model satisfying ZF but not the
Well-ordering axiom!  In other words, the truth of the Well-ordering Axiom
is \emph{independent} of the other basic axioms of ZF.

The Continuum Hypothesis is also independent of ZF and Well-ordering
together.  In the 1930's, Kurt G\"{o}del showed that it is consistent with
the other axioms to assume the Continuum Hypothesis is true.  On the other
hand, Cohen's methods applied as well to the Continuum Hypothesis.  Cohen
showed there is a model satisfying ZF \emph{and} the Well-ordering Axiom,
but not the Continuum Hypothesis.

These independence results are usually studied in graduate level Set
Theory courses.  But aside from nicely completing the ``smaller
than'' story, the Totality Claim and the Continuum Hypothesis play no role
in discrete Mathematics or the rest of 6.042, so we needn't pursue this
part of the theory of infinite sets.

\appendix
\section{Bijections, Injections, Surjections}\label{bijprops}
In the arguments above we used various elementary properties of
bijections, injections, and surjections.  In this section we review and
prove these basic facts.

To begin, let's review some further definitions:
\begin{defin}
If $f':B\to C$, the \emph{composition} of $f'$ and $f$, written $f' \circ
f$ is the function $e:A \to C$ defined by the rule that $e(a) ::=
f'(f(a))$.

For any set $S$, the \emph{identity function} $\iden{S}:S \to S$ is defined
by the property that $\iden{S}(s) = s$ for all $s \in S$.

Let $g,h: B \to A$.  Define $g$ to be a \emph{left inverse} of $f$
iff
\[g \circ f = \iden{A}. \]
Similarly, $h$ is a \emph{right inverse} of $f$
iff
\[f \circ h = \iden{B}. \]
\end{defin}

\begin{lemma}\label{leftinv}
Let $A$ be a nonempty set.  A function $f:A\to B$ is an injection iff it
has a left inverse.
\end{lemma}
\begin{proof}
($\Leftarrow$).  Suppose $g$ is a left inverse of $f$.  Now if $f(a_1) =
f(a_2)$, then
\[a_1 = \iden{A}(a_1) = (g \circ f)(a_1) = (g(f(a_1)) = g(f(a_2)) = (g \circ
f)(a_2) = \iden{A}(a2) = a_2\]
so $f$ is an injection.

($\Rightarrow$) Suppose $f:A\to B$ is an injection.  For every $b \in
\ran{f}$ there is by definition some $a \in A$ such that $f(a) = b$.  Since
$f$ is an injection, this $a$ is unique, so for $b \in \ran{f}$, we can
define $g(b)$ to be this unique $a$.  Since $A$ is nonempty, there is some
$a_0 \in A$.  For $b \in B - \ran{f}$, define $g(b) = a_0$.  So $g:B \to A$
and $g(f(a)) = a$ by definition of $g$.  That is, $g$ is a left inverse of
$f$.
\end{proof}

\begin{lemma}\label{rightinv}
A function $f:A\to B$ is an surjection iff it has a right inverse.
\end{lemma}
\begin{proof}
($\Leftarrow$).  Suppose $h:B\to A$ is a right inverse of $f$.  So for $b
\in B$, $f(h(b)) = b$.  Hence $b = f(a)$ where $a = h(b)$.  Thus $b \in
\ran{f}$.  So $\ran{f} = B$, that is, $f$ is a surjection.

($\Rightarrow$) For each $b \in B$, define $g(b)$ to be some $a$ such that
$f(a) = b$.  Since $f$ is a surjection, for each $b \in B$ there always is
at least one such $a$.  So $g:B \to A$ and $f(g(b)) = b$ for all $b \in B$.
That is, $g$ is a right inverse of $f$.
\end{proof}

\begin{corollary}\label{injsur}
\[A \inj B \iff B \sur A.\]
\end{corollary}
\begin{proof}
Notice that the definitions of left and right inverse imply that $g$ is a
left inverse of $f$ iff $f$ is a right inverse of $g$.  So
\[\begin{array}{rcl}
A \inj B &  \iff & \exists f: A \to B\, [f\mbox{ is an injection }]\\
         & \iff  & \mbox{(by Lemma~\ref{leftinv}) }
                     \exists f:A\to B, g: B \to A\,[g\mbox{ is a
                                    left inverse of } f]\\
 & \iff & \exists f:A\to B, g: B \to A\, [f\mbox{ is a right inverse of } g]\\
 & \iff  & \mbox{(by Lemma~\ref{rightinv}) }
             \exists g: B \to A\, [g\mbox{ is a surjection}]
\end{array}\]
\end{proof}

In fact, we can say something stronger
\begin{corollary}\label{uinv}
A function is a bijection iff it has a right inverse and a left inverse.
If a function $f$ has both right inverse and a left inverse, then they are
equal.
\end{corollary}
\begin{proof}
That a function is a bijection iff it has a right inverse and a left
inverse follows immediately from the definition of bijection and the two
previous Lemmas~\ref{leftinv} and~\ref{rightinv}.

Now suppose $g: B\to A$ is a left inverse of $f$ and $h: B\to A$ is a right
inverse.  Then
\[g(b) = g(\iden{B}(b)) = g ((f \circ h)(b)) = g(f(h(b))) = (g \circ f)(h(b))
= (\iden{A})(h(b)) = h(b),\]
so $g = h$.
\end{proof}

For a bijection $f:A \to B$, we conclude from Corollary~\ref{uinv} that all
right inverses and left inverses of $f$ are equal.  We write $f^{-1}:B \to
A$ to denote this unique function.

\begin{theorem}\label{2inv}
For any bijection $f:A\to B$, the function $f^{-1}:B \to A$ is also a
bijection, and $(f^{-1})^{-1} = f$.
\end{theorem}
\begin{proof}
We noted that the definitions of left and right inverse imply that $g$ is a
left inverse of $f$ iff $f$ is a right inverse of $g$.  Since $f^{-1}$ is a
left and right inverse of $f$, it follows that $f$ is a right and left
inverse of $f^{-1}$, so by Lemma~\ref{uinv}, $f^{-1}$ is a bijection and
$(f^{-1})^{-1} = f$ .
\end{proof}

Theorem~\ref{2inv} immediately implies that $A \bij B \iff B \bij A$, that
is, $\bij$ is \emph{symmetric}.  Obviously $A \bij A$, that is, $\bij$ is
also \emph{reflexive}.  So to show that $\bij$ is an equivalence relation,
we just have to verify that it is \emph{transitive}.  We'll actually prove
something somewhat stronger, namely that both $\inj$ and $\sur$ are
transitive relations.

\begin{lemma}\label{compinv}
The composition of two injections is an injection.
\end{lemma}
\begin{proof}
Suppose  $f: A \to B$ and $f':B \to C$ are injections.  Let $e = f' \circ
f$.  Suppose $e(a_1) = e(a_2)$.  We want to show that $a_1 = a_2$.

Let $b_i = f(a_i)$.  So
\[f'(b_1) = f'(f(a_1)) = e(a_1) = e(a_2) = f'(f(a_2)) = f'(b_2).\]
Since $f'$ is an injection, we conclude that $b_1 = b_2$.  So $f(a_1) =
f(a_2)$, and since $f$ is an injection, $a_1 = a_2$.
\end{proof}

\begin{corollary}
The relation $\inj$ is transitive.
\end{corollary}
\begin{proof}
Suppose $A \inj B$ and $B \inj C$.  So there is an injection $f:A \to B$
and an injection $f':B \to C$.  Then $(f' \circ f):A \to C$ is an injection
by Lemma~\ref{compinv}.  Hence $A \inj C$.
\end{proof}

\begin{lemma}\label{compsur}
The composition of two surjections is a surjection.
\end{lemma}
\begin{proof}
We could give a proof directly from the definitions as in the previous
Lemma, but let's use another argument based on inverses.

Suppose $f: A \to B$ and $f':B \to C$ are surjections.  We want to show
that $(f' \circ f)$ is a surjection.  By Lemma~\ref{rightinv}, we need only
find a right inverse for $(f' \circ f)$.  We'll do this as follows.  Let
$g:B\to A$ be a right inverse of $f$, which exists by Lemma~\ref{rightinv}.
Likewise, let $g':C\to B$ be a right inverse of $f'$.  Let $e' = g \circ
g'$.  We claim that $e'$ is the desired right inverse of $(f' \circ f)$.
This follows because
\[(f' \circ f) \circ e = (f' \circ (f \circ e)) = (f' \circ (f \circ (g
\circ g'))) = (f' \circ ((f \circ g) \circ g')) = (f' \circ (\iden{B} \circ
g')) = f' \circ g' = \iden{C}. \]
\end{proof}

Lemma~\ref{compsur} implies that the relation $\sur$ is transitive.  We
have finally completed the proof of
\begin{theorem}
The relation $\bij$ is an equivalence relation on sets.
\end{theorem}

\textbf{Exercise}.  Suppose $A_0 \bij A_1$ and $B_0 \bij B_1$.

(a) Prove that $A_0 \times B_0\ \bij\ A_1 \times B_1$, $P(A_0) \bij
P(A_1)$.

(b) Give a counterexample to the claim that $A_0 \intersect B_0\ \inj\ A_1
\intersect B_1$.

\section{Finite Cardinality}\label{fincardprf}
In this section we prove the basic properties of finite cardinality,
starting from the definitions of $\card{A}$ and the basic properties of
bijections, injections, and surjections in section~\ref{bijprops}.

We begin with the key Lemma which justifying the use of the sets
$\clop{n}$ as standard finite sets.

\begin{lemma}\label{minjn2}
$\clop{m} \inj \clop{n}$ iff $m \le n$.
\end{lemma}
\begin{proof}
($\Rightarrow$) If $m \le n$, then the ``inclusion function'' mapping $m
\in \clop{m}$ to itself, is an injection from $\clop{m}$ to $\clop{n}$.

($\Leftarrow$) By induction on $n$.

(Base case $n = 0$).  Since $n=0$, we know $\clop{n} = \emptyset$.  So if
$\clop{m} \inj \clop{n}$, then $\clop{m}$ must also be empty.  That is, $m
= 0 \le n$.

(Induction).  Assume that $n \ge 0$ and that
\[\forall m \in \naturals: \clop{m} \inj \clop{n} \implies m \le n.\]

Suppose $f:\clop{m} \to \clop{n+1}$ is an injection.  We must show that $m
\le n+1$.  If $m=0$, we are done, so we can assume $m> 0$.  Now there are
three cases:

\begin{enumerate}
\item Suppose $n \not\in \ran{f}$.  Then $f$ can also be regarded as a
function from $\clop{m}$ to $\clop{n}$, and so $\clop{m} \inj \clop{n}$.
Then by induction, $m \le n$, so $m \le n+1$ as required.

\item Suppose $f(m-1) = n$.  Since $f$ is a bijection to $\clop{n+1}$, we
know that $f(k) < n$ for $0 \le k < m-1$.  Now let $g$ be the restriction
of $f$ to $\clop{m-1}$, that is $g(k) ::= f(k)$ for $0 \le k < m-1$.  The
domain of $g$ is the domain of $f$ except for $m-1$.  Since $f$ is an
injection, the range of $g$ is the range of $f$ except for $f(m-1) = n$.  So
$g:\clop{m-1} \to \clop{n}$, and $g$ is an injection since $f$ is.  Hence,
$\clop{m-1} \inj \clop{n}$.  By induction, we have that $m-1 \le n$, which
implies $m \le n+1$.

\item Finally, supppose $n \in \ran{f}$ and $f(m-1) \neq n$.  Since $n \in
\ran{f}$, there is a nonnegative integer $j_0 < m-1$ such that $f(j_0) = n$.
Now let $g$ be defined so that it is the same as $f$ except that the
values at $j_0$ and $m-1$ are switched.  That is $g:\clop{m} \to \clop{n+1}$
is defined by the rule that $g(j) ::= f(m-1)$, $g(m-1) ::= f(j_0) = n$, and
$g(i) ::= f(i)$ for $i \neq j_0,m-1$.  Since $f$ is an injection, so is $g$.
But $g(m-1) = n$, so our argument in the previous case applies to $g$,
allowing us again to conclude that $m \le n+1$.
\end{enumerate}
\end{proof}

Now we can formally conclude that there really are exactly $n$ nonnegative
integers less than $n$, namely, the set $\set{0,1,\dots,n-1}$ has
cardinality $n$:
\begin{corollary}
For all $n \in \naturals$, $\card{\clop{n}} = n$.
\end{corollary}
\begin{proof}
Suppose $\card{\clop{n}} = m$, so $\clop{n} \bij \clop{m}$ by definition,
and therefore $n \le m$ by the previous Lemma~\ref{minjn2}.  But we've
already observed that $m = \card{\clop{n}} \le n$.  Therefore, $m = n$.
\end{proof}



\begin{lemma}\label{injnbijm}
If $A \inj \clop{n}$, then $A$ is finite and $\card{A} \le n$.
\end{lemma}
\begin{proof}
By induction on $n$. 

(Base case $n = 0$).  We have that $\clop{n} = \emptyset$, so
$A$ must be empty and hence $\card{A} = 0$ by Lemma~\ref{empty0}.

(Induction).  Assume that $n\ge 0$ and $B \inj \clop{n}$ implies $B$ is
finite and $\card{B} \le n$, for all sets $B$.

Now suppose $f:A \to \clop{n+1}$ is an injection.  We must show that $A$
is finite and $\card{A} \le n+1$.  There are two cases:
\begin{enumerate}
\item Suppose $n \not\in \ran{f}$.  Then $f$ can also be regarded as a
function from $A$ to $\clop{n}$, and so $A \inj \clop{n}$.  Then by
induction, $A$ is finite and $\card{A} \le n \le n+1$ as required.

\item Otherwise, $f(a) = n$ for some $a \in A$.  Let $B ::= A -\set{a}$.
Since $f$ is an injection, we know that $f(b) < n$ for $b \in B$.  Now let
$g$ be the restriction of $f$ to $B$, that is $g(b) = f(b)$ for $b \in B$.
Since $f$ is an injection, the range of $g$ is the range of $f$ except for
$f(a) = n$.  So $g:B \to \clop{n}$, and $g$ is an injection since $f$ is.
Hence, $B \inj \clop{n}$.

By induction, we conclude that $B$ is finite and $\card{B} \le n$.  That
is, there is a bijection $h':B\to \clop{m}$ for some $m \le n$.  Now
define a function $h$ on $A$ by the rule that $h(b) ::= h'(b)$ for $b \in
B$ and $h(a) ::= m+1$.  Then $h:A \to \clop{m+1}$ is a bijection.  So $A$
is finite and $\card{A} \le m+1$ by definition of $\card{A}$.  But $m+1 \le
n+1$, so $\card{A} \le n+1$ as required.
\end{enumerate}
\end{proof}

\begin{corollary}\label{finsub}
If $B$ is finite and $A \inj B$, then $A$ is finite.  In particular, 
if $B$ is finite and $A \subseteq B$, then $A$ is finite.
\end{corollary}
\begin{proof}
If $B$ is finite, then $B \bij \clop{\card{B}}$ by definition of
$\card{B}$.  If also $A \inj B$, then since $\inj$ is transitive, we
conclude that $A \inj \clop{n}$, so $A$ is finite by Lemma~\ref{injnbijm}.

If $A \subseteq B$, then the ``inclusion'' function $\iden{AB}:A \to B$
defined by the rule $\iden{AB}(a) ::= a$ is an injection, so $A \inj B$,
so the second statement in the Corollary follows from the first.
\end{proof}

\begin{corollary}\label{bijncardn}
\[A \bij \clop{n} \iff A \mbox{ is finite and } \card{A} = n.\]
\end{corollary}
\begin{proof}
($\Leftarrow$) By definition of $\card{A}$.

($\Rightarrow$) If $A \bij \clop{n}$, then $A$ is finite and $A \bij
\clop{\card{A}}$ by definition.  Since $\bij$ is an equivalence,
$\clop{n} \bij \clop{\card{A}}$, so $m=n$ by Lemma~\ref{minjn2}.
\end{proof}

We still need another ``sanity check'' of our definitions: we have defined
``same size'' separately from ``the size'' of finite sets.  We better be
sure the definitions agree:
 
\begin{theorem}\label{leinj}
If $B$ is a finite set, then
\[ [A \mbox{ is finite and } \card{A} \le \card{B}] \iff A \inj B.\]
\end{theorem}
\begin{proof}
Since $B$ is finite, if $A \inj B$, then $A$ is finite by we have by
Corollary~\ref{finsub}.  So we may assume in the proof that $A$ is finite.

By definition of cardinality, $A \bij \clop{\card{A}}$ and $B \bij
\clop{\card{B}}$.  
So since $\bij$ is an equivalence, $\bij$ implies
$\inj$, and $\inj$ is transitive, we have that
\[A \inj B \iff \clop{\card{A}} \inj \clop{\card{B}}.\]
But by Lemma~\ref{minjn2},
\[\clop{\card{A}} \inj \clop{\card{B}} \iff \card{A} \le \card{B}.\]
\end{proof}

\begin{corollary}\label{bijcard}
If $B$ is a finite set, then
\[ [A \mbox{ is finite and } \card{A} = \card{B}] \iff 
A \bij B.\]
\end{corollary}
\begin{proof}
($\Leftarrow$) $A \bij B$ implies that $A \inj B$ and $B \inj A$, so by
Theorem~\ref{leinj}, $A$ is finite, $\card{A} \le \card{B}$ and $\card{B}
\le \card{A}$.

($\Rightarrow$) By definition, $A \bij \clop{\card{A}}$ and $B \bij
\clop{\card{B}}$.  If $\card{A} = \card{B}$, then obviously
$\clop{\card{A}} = \clop{\card{B}}$, so $A$ and $B$ have a bijection to
the same set, namely, $\clop{\card{A}}$.  So $A \bij B$, since $\bij$ is
an equivalence.
\end{proof}

So to summarize, we have found that the relative sizes of finite sets are
completely captured by injections and bijections among them.

\end{document}
