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

\begin{document}

\handout{notes-cardinality}{Cardinality: Further Notes for
Lecture 13}{March 30, 1999}

\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, namely a \emph{bijection}, 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 in Lecture 12 a
correspondence between the powerset, $P(S)$, and the 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$.

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.

(d) Describe a simple procedure for computing $f^{-1}(k)$.
\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 a proper subset of itself.

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

A set, $S$, is said to be \emph{finite} iff there is a bijection between
$S$ and $\clop{n}$ for some $n \in \naturals$.  If $S$ is a finite set,
the \emph{cardinality}, $\card{S}$, of $S$, is this, necessarily unique,
number $n$.
\end{defin}
Note that by definition, $\clop{0} = \emptyset$, and so this definition
agrees with the observation that the only set with cardinality zero is the
empty set.

\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$.
\end{defin}

Some elementary, but important properties of these relations are:
\begin{lemma}

\begin{enumerate}
\iffalse
\item Composition of functions is an associative operation:
\[f \circ (g \circ h) = (f \circ g) \circ h.\]
\fi

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

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

\item If $A$ is nonempty, then $A \inj B$ iff $B \sur A$.

\end{enumerate}
\end{lemma}

Basic properties of bijections, injections, and surjections are reviewed
in the Appendix.  We state without proof the simple connections between
the cardinality of finite sets and the existence of injective or
surjective functions between them.

\begin{theorem}\label{masterfin}

\begin{enumerate}
\item If $B$ is finite and $A \inj B$, then $A$ is finite and $\card{A} \le \card{B}$.
\item If $B$ is finite and $B \sur A$, then $A$ is finite and $\card{B} \ge \card{A}$.
\item If $B$ is finite and $A \bij B$, then $A$ is finite and $\card{A} = \card{B}$.
\end{enumerate}
\end{theorem}

Here are two more obvious properties of finite sets which follow directly
from the definition of their cardinality.
\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}

\begin{corollary}\label{disju}
If $A$ and $B$ are disjoint finite sets, then
$\card{A \union B} = \card{A} + \card{B}$.
\end{corollary}

\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 easily shown to be a bijection, so $\card{A
\union B} = \card{A} + \card{B}$ by Theorem~\ref{masterfin}.
\end{proof}


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

\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$.
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.  So this process
defines the desired sequence $a_1, a_2, \dots, a_n, \dots$.

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.  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}}$, which is impossible\footnote{A
completely formal development of finite cardinality should include a proof
of this fact.  Technically,
a slightly stronger basic
fact is needed even earlier to show that the cardinality of a finite set
is uniquely defined:
\[\clop{m} \inj \clop{n} \iff m \leq n.\]
The proof is a routine induction on $n$ which we omit.}
\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.  This is proved using the
\emph{diagonal} arguments described in lecture and section~\ref{diag} below.

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$.
Note that in the Fall 97 Lecture 13 Notes, the notation $\card{A} \leq
\card{B}$ used for finite sets was extended to infinite sets to mean
precisely that $A \inj B$.  The $\inj$ notation is preferable since we
have not defined $\card{A}$ for infinite sets\footnote{It is possible to
give a technical definition of $\card{A}$ for infinite sets, but we have
no need to do so.}.

Now 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\footnote{Corollary~\ref{uinv} in the Appendix.} 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


\section{Countable Sets}\label{countable}
\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}

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

In lecture we described a \emph{dovetailing} technique which shows that
the rational numbers, $\rationals$, is a countable set.  The
Schr\"{o}der-Bernstein Theorem allows us to reach the same conclusion
in another way:
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.
The results above show that $\nats, \ints, \rationals, \ints^2, \nats^2$
are all countably infinite.

\begin{problems}

\problem Prove that $A$ is countable iff $A \inj \nats$.

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

\problem  Suppose $A_0 \inj A_1$ and $B_0 \inj B_1$.
\bparts
\ppart Prove that $(A_0 \times B_0) \inj (A_1 \times B_1)$.

\ppart Prove that $P(A_0) \inj P(A_1)$.

\ppart  Give a counterexample to the claim that
\[A_0 \union B_0\ \inj\ A_1 \union B_1.\]

\ppart Show that previous claim holds if at least one of $A_0$ and $B_0$ is
infinite.

\ppart Suppose $A_0 \bij A_1$ and $B_0 \bij B_1$.  Give a counterexample to
the claim that $A_0 \intersect B_0\ \inj\ A_1 \intersect B_1$.

\eparts

\end{problems}

\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{Bigger and bigger infinities}\label{diag}
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{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}

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

For example, since $\nats \ll P(\nats) \bij \reals$, we can conclude that
$P(\nats)$ and $\reals$ are both uncountable sets.

Now Cantor's Theorem also implies that we can keep finding bigger
infinities:
\[\naturals\ \ll P(\naturals) \ll P(P(\naturals)) \ll P(P(P(\naturals))) \ll \dots.\]
But that's not all: there are sets which are bigger than any of the sets
in the preceding sequence.  Namely, let $U ::= \union_{i=0}^{\infty}
P^i(\nats)$, then every set $P^i(\nats) \subset U \ll P(U)$, so $P(U)$ is
strictly larger than every set in the sequence!

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.

\section{Set Theory}
(This section contains optional material, not required for 6.042.)

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 \emph{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 \emph{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.  Indeed,
virtually all mathematicians 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 \emph{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 1940'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.  

\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}If $A$ is nonempty, then
\[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}

\end{document}
