\documentclass[11pt]{article}

\usepackage{precalc}
\usepackage{url}
\newcommand{\W}{\mathbb{W}}

\begin{document}

\assigntitle{3}{To $\infty$\dots and beyond!\footnote{With apologies
    to Buzz Lightyear.}}

This week, we'll take a look at some fascinating implications of set
theory as it relates to the infinite.

\section{Comparing cardinalities}

\topic{comparing M\&M jars}
Suppose someone gave you two jars full of M\&M's and asked you which
one contained more.  How would you answer them? You would probably
count the M\&M's in the first jar, then count the M\&M's in the second
jar, then compare the two numbers to see which was greater.

\begin{problem} \label{prob:mm-method2}
  Before continuing, can you think of a different way to determine which
  jar has more M\&M's?  In particular, see if you can think of a
  method which doesn't involve counting anything.
\end{problem}

\topic{comparing set cardinalities}
This example can easily be extended to a method of comparing the
cardinalities of two finite sets---just compute the cardinality of the
first, compute the cardinality of the second, and compare.  For
example, it's obvious that $\{1,2,3\}$ has greater cardinality than
$\{7,9\}$, since the first set has cardinality $3$, the second has
cardinality $2$, and $3 > 2$.  What could be simpler?

However, this method doesn't work so well for infinite sets!  For
example, how are we to compare the set of all integers with the set of
all even integers?  The set of all integers has cardinality\dots
infinity?  And there are also infinitely many even integers\dots and
besides, infinity isn't really a number!  

Intuitively, of course, it seems like there are more integers than
even integers. After all, every even integer is also an integer, and
there are some integers which aren't even, so the set of even integers
is a proper subset of the set of integers.

However, we have to tread carefully here.  It turns out that intuition
isn't much use when it comes to infinity!

\section{Hotel $\infty$} 
\label{sec:hotel-infty}

(The original idea for Hotel $\infty$ is due to the German
mathematician David Hilbert (1862--1943); I have borrowed his idea and
taken some artistic license.)

\topic{the Hotel} Once upon a time, in the beautiful land of
Mathistan, there lived a certain man named George Canand.  George was
the proprietor of a most unusual hotel called Hotel $\infty$.  This
hotel was very posh (it had received a rating of infinity stars for as
long as anyone could remember), very expensive (for the price of
infinity dollars you could stay as long as you wanted), and very
large: in fact, there were an infinite number of rooms, numbered 1, 2,
3, and so on.  George himself lived in a special apartment numbered 0.

One Sunday night, George was getting ready to go to bed.  He was
infinitely tired, since it had been an infinitely busy weekend; every
single room in the hotel was occupied, so George and his employees (an
infinite number of cooks, bellhops, and cleaning staff) had spent the
whole weekend cooking an infinite number of meals, carrying an
infinite number of suitcases, and vacuuming up an infinite amount of
dust from an infinity of floors.  Just as he was about to get under
the covers, he heard a knock at the hotel's front door, which was
right next to his apartment.  There were an infinite number of staff
working at the front desk, of course, but for some reason George's
curiosity was piqued, and he decided to see who it was for himself.

\topic{arrival of Wan Moore}
When he went out into the lobby, he was surprised to see a man
standing there with a suitcase, dressed in sandals, shorts and a
t-shirt with a picture of some sort of strange twisted bottle
thing which had no inside or outside. The man introduced himself as
Wan Moore.

``I'm here in Mathistan to attend the Infinitieth International
Conference on the Continuum, but my flight from North Logicia was
delayed considerably, and the trains out to the convention center are
no longer running this evening.  So, I was wondering if I might stay
here tonight.''

George was astonished but polite.  ``Didn't you see the sign out
front?  All of our rooms are occupied.  I'm afraid we have no room for
you here.  Might I suggest the Holiday $\in$ down the street?''

``Oh, but I absolutely must stay here,'' Wan insisted.  ``Even if
what I've heard is only half true, the Hotel $\infty$ is infinitely
better than anywhere else I could ever stay.''

``Well, that is true,'' conceded George with an infinite amount of
pride.  ``But you'll simply have to come back a different night.''

``Wait,'' said Wan, ``I have an idea.''

After listening carefully, George agreed that it was an excellent
idea, and instructed his staff to carry it out immediately.  Wan did
stay in Hotel $\infty$ that night after all, and in the morning
claimed that he slept infinitely better than he had ever slept before.

\begin{problem}
  What was Wan's idea?  (You may assume that George's guests
  love Hotel $\infty$ so much that they don't mind being woken up in
  the middle of the night, or even being asked to switch rooms, as
  long as they still have a place to sleep.  Sharing a hotel room with
  another guest, however, is completely out of the question.)
\end{problem}

\topic{a tour group of twenty} The next day, no one checked out of the
hotel (since you can stay as long as you want, no one ever checks
out).  That night, however, a bus with twenty tourists showed up.
After thinking a bit, George was able to accommodate them, too.  Each
one of them slept soundly in their own room of Hotel $\infty$.

\begin{problem}
  What did George do this time to accommodate the new guests?
\end{problem}

For the remainder of the week, no one new showed up (much to George's
relief).  But no one checked out, either, so all the rooms were still
full.  That Friday, just as George was getting ready for bed, there
came another knock at the door.  ``Oh, no,'' thought George, ``who
could it be this time?''

\topic{an infinite tour group} Much to his dismay, when he entered the
(infinitely large) lobby, he found it full of an infinite number of
people!  A woman approached him and introduced herself as Alice Nul.
``Hi, my infinite number of friends and I are here on a sightseeing
tour of Mathistan, and we were wondering if you have room for us here.
I've heard that this is the only place that can fit all of us, and
we'd really like to all be able to stay in the same hotel.''

``I'm really sorry, Alice, but all our rooms are full!'' replied
George.  ``I would love for you and your friends to stay here, but
there simply isn't room.''

``Are you absolutely sure?'' Alice asked.  ``I don't know where else we
would go.  Maybe some people have checked out that you didn't notice?
We would really, really like to stay here.''

``I don't know,'' said George unhappily, ``but I'll check.''

Instead, George ran straight to room 21.  ``Wan!'' he cried,
knocking frantically.  ``I need your help!''

``What's wrong?'' Wan asked, opening the door.  

George explained the situation.  

``Oh.  Is that all?'' said Wan.

``Wan, you are a genius!'' exclaimed George, after hearing Wan's idea.

That night, Alice and all her friends enjoyed their stay in Hotel
$\infty$, and declared it to be chief among the wonders of Mathistan.

\begin{problem}
  What was Wan's idea this time?
\end{problem}

\topic{an infinite number of infinite tour groups} After their tour of
Mathistan, Alice and her friends returned to Wordsylvania and spread
the word about Hotel $\infty$.  Their glowing review spread so far and
fast that the next weekend, an infinite number of tour buses, each
filled with an infinite number of people, all showed up at Hotel
$\infty$ at once!  By now, however, Wan Moore had accepted George's
offer of employment as general manager of the hotel (for a salary of
\$$2^\infty$), and easily accommodated all the tourists.  George
didn't even wake up.

\begin{problem} \label{prob:infinity-tour-buses}
  How did Wan do it!? 
\end{problem}

\section{By jection!}

\topic{infinity is strange}
By now, you should be thoroughly convinced that \emph{infinity is
  really strange}.  Don't worry, though.  It gets even stranger!

\topic{matching M\&M's}
But first, let's go back to M\&M's.  Here's another way to compare the
two jars to see which has more.  Is this the method you came up with
in \pref{prob:mm-method2}?
\begin{enumerate}
\item Take out two M\&M's, one from each jar.
\item Eat them.\footnote{Feeding them to your pet mmweasel is also an
    option.  If you've never heard of mmweasels, they are a certain
    type of weasel, found mostly in North America and parts of
    Iceland, which eat only M\&M's.}
\item If one of the jars is now empty, it had fewer M\&M's to begin
  with than the other jar.  Otherwise, return to step 1.
\end{enumerate}

Do you see how this works?  The interesting thing about this method is
that it \emph{doesn't involve any counting}!  In other words, we can
compare the cardinality of two sets without actually counting
anything, just by matching up their elements.

That phrase ``matching up their elements'' ought to ring a bell---of
course, a bijection is a function which does just that!  So, we can
define equality of cardinalities in terms of bijections:

\begin{defn}{equality of set cardinality}
  Two sets $S$ and $T$ have the same cardinality if there exists a
  bijection $f: S \to T$.
\end{defn}

Since this doesn't involve any counting, it works just as well for
infinite sets as for finite ones.  In order to prove that two sets $S$
and $T$ have the same cardinality, you just have to specify some
function $f : S \to T$, and show that $f$ is a bijection (by showing
that it is both injective and surjective).

\topic{$|\N| = |\W|$}
As an example, let's show that the sets $\N$ (the natural numbers $0$,
$1$, $2$, $3$ \dots) and $\N \setminus \{0\}$ (the whole numbers $1$, $2$,
$3$, \dots) have the same cardinality.  This might seem
strange---after all, $\N$ has an element that $N \setminus \{0\}$
doesn't---but it's true!

As an abbreviation, let's write $\W$ in place of $\N \setminus
\{0\}$.  Now consider the function $f : \N \to \W$ defined as $f(n) =
n + 1$.  I claim that $f$ is a bijection.

First, we need to show that $f$ is injective.  (Remember, to show that
a function $f$ is injective, we must show that if $f(x) = f(y)$, then
$x = y$, for any $x$ and $y$ in the domain of $f$.)  Suppose $x,y \in
\N$, and $f(x) = f(y)$.  By the definition of $f$, this means
that $x + 1 = y + 1$.  But now we can just subtract $1$ from both
sides to get $x = y$.  Therefore $f$ is injective.

Now we will show that $f$ is a surjection (by showing that for every
element $y$ of its codomain, there is some corresponding element of the
domain which $f$ maps to $y$).  Suppose $y \in \W$.  Then I claim that
$y - 1 \in \N$, and $f(y-1) = y$.  If $y \in W$ then $y \geq 1$, which
means that $y - 1 \geq 0$, proving that $y-1 \in \N$.  It is also
obvious that $f(y-1) = y$.  Therefore, $f$ is surjective.

Since $f$ is both injective and surjective, it is a bijection, and
$|\N| = |\W|$!

\begin{problem}
  What does this have to do with Hotel $\infty$?
\end{problem}

\begin{problem}
  Prove that the set of integers ($\Z$) and the set of even integers
  (often written $2\Z$) have the same cardinality.
\end{problem}

Strange, isn't it!? For \emph{finite} sets $S$ and $T$, if $S \subset
T$ then we know that $|S| < |T|$. ($S \subset T$, pronounced ``$S$ is
a proper subset of $T$,'' means that $S \subseteq T$ and $S \neq T$;
that is, every element of $S$ is an element of $T$, \emph{and} there
are some elements of $T$ which are \emph{not} elements of $S$.) For
example, $\{3,4,5\} \subset \{2,3,4,5\}$, and clearly the cardinality
of $\{3,4,5\}$ (namely, $3$) is smaller than the cardinality of
$\{2,3,4,5\}$ (namely, $4$).  But this isn't necessarily true for
infinite sets!  As you have just proved, it is quite possible to have
two infinite sets where one is a proper subset of the other, and yet
they have the same cardinality.

\begin{problem}
  Prove that $|\N| = |\Z|$.
\end{problem}

\section{Cantor's discoveries}

\topic{Georg Cantor}
Most of the ideas in this week's assignment are due to the German
mathematician Georg Cantor (1845-1918).  He created set theory, and
was one of the first people to realize the importance of talking about
bijections (one-to-one correspondences) between sets.  His ideas about
infinity were quite controversial while he was alive (many people
objected to them on philosophical and religious grounds in addition to
mathematical ones!), but have since become widely accepted, mainly due
to the numerous connections that have been discovered between his
ideas and a wide range of other areas of mathematics.  If you're
interested in learning more about Cantor, the Wikipedia article on his
life and work makes for an interesting read.

For the remainder of the assignment, we'll explore just a few of the
surprising discoveries he made.

\subsection{$\N \times \N$ and $\Q$}

The first surprising application of Cantor's new framework of
one-to-one correspondence between sets was in proving that $\N$ (the
set of natural or counting numbers, $0$, $1$, $2$, $3$, \dots) has the
same cardinality as $\N \times \N$ (the set of all \emph{pairs} of
natural numbers).

\begin{problem}
  Explain how $\N \times \N$ is like the infinite number of tour buses
  of infinite tour groups who descended on Hotel $\infty$ at the end
  of the story in \pref{sec:hotel-infty}.
\end{problem}

\topic{$|\N| = |\N \times \N|$}
There are actually lots of different bijections between $\N$ and $\N
\times \N$.  If you want to see one of them, you can read about it
here: \url{http://www.mathlesstraveled.com/?p=94}.  The basic idea is
to lay out all the elements of $\N \times \N$ in a grid, and list them
``by diagonals'': $(0,0)$, $(1,0)$, $(0,1)$, $(2,0)$, $(1,1)$,
$(0,2)$, $(3,0)$ \dots (incidentally, if you haven't solved
\pref{prob:infinity-tour-buses} yet, consider this a hint!).  As I
talk about in that blog post, this actually shows that the cardinality
of $\Q$ (the rational numbers) is also the same as $\N$.

\subsection{$\R$}

Every set that is either finite or has the same cardinality as $\N$ is
called \term{countable}.  At this point it would be easy to assume
that, in fact, \emph{all} infinite sets are countable.  The amazing
thing is that if you assumed that, you would be wrong!

Cantor's most surprising discovery, and the one thing which upset his
critics the most, was his discovery that the set of real numbers $\R$
actually has a \emph{different} cardinality than the set of natural
numbers $\N$.  They are both infinite sets, but there is an important
and specific sense in which $\R$ is \emph{more infinite} than $\N$!

Not only that, but he also showed that the cardinality of the
$\mathcal{P}(S)$, the set of all subsets of $S$, is always greater than
the cardinality of $S$.  This means that there is actually an infinite
hierarchy of infinities, each more infinite than the last!  Don't hurt
your brain.

\topic{$|\R| \neq |\N|$}
Let's see how Cantor proved that the cardinality of $\R$ is greater
than that of $\N$.  To prove that two sets have the same cardinality,
we have to show a bijection between them; so, to show that two sets
have different cardinalities, we must show that \emph{no bijection
between them can possibly exist}.

What Cantor actually proved is that the cardinality of $[0,1]$ is
greater than that of $\N$; if that is true, than the cardinality of
all of $\R$ (of which $[0,1]$ is a subset) must be greater than $\N$
as well.

Let's start by assuming that there \emph{is} some one-to-one
correspondence between $\N$ and $[0,1]$.  That means we can make a
list of \emph{all} the real numbers in $[0,1]$, with each one labeled
by a natural number. (That is, every real number in $[0,1]$ can have
its own room in Hotel $\infty$.) Like this:

\setlength\arraycolsep{2pt}
\begin{equation*}    \label{eq:enum-01}
  \begin{array}{ccccccccccccccc}
    r_0 & = & 0 & . & \mathbf{1} & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & \dots \\
    r_1 & = & 0 & . & 3 & \mathbf{1} & 4 & 1 & 5 & 9 & 2 & 6 & 5 & 3 & \dots \\
    r_2 & = & 0 & . & 4 & 9 & \mathbf{0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\
    r_3 & = & 0 & . & 7 & 7 & 7 & \mathbf{7} & 7 & 6 & 7 & 7 & 7 & 7 & \dots \\
    r_4 & = & 0 & . & 1 & 2 & 3 & 4 & \mathbf{5} & 6 & 7 & 8 & 9 & 0 & \dots \\
    r_5 & = & 0 & . & 4 & 7 & 5 & 8 & 9 & \mathbf{2} & 2 & 3 & 6 & 4 & \dots \\
    r_6 & = & 0 & . & 4 & 8 & 4 & 8 & 4 & 9 & \mathbf{4} & 9 & 4 & 5 & \dots \\
        & \vdots &&&&&&&&&&&&& 
  \end{array}
\end{equation*}

This list could be arranged any way we like, but if there \emph{is} a
bijection between $\N$ and $[0,1]$, then we would be able to make such
a list.  Note, of course, that the list goes on forever (there is an
$r_n$ for every $n \in \N$), and each number in the list extends on
forever to the right.  This is just a small part of the list we're
seeing.

\topic{Cantor's diagonal argument}
Now, do you see how the digits on a diagonal line are in bold? Let's
take those digits and use them to make another number: \[ q =
0.1107524 \dots \] In other words, $q$ has one digit taken from each
number in the list, each in a different place.  
\begin{problem}
  Now, write down another number $q'$ by changing each digit of $q$ into
  a different digit.
\end{problem}

\begin{problem}
  Explain why we know that $q'$ is not equal to $r_0$.
\end{problem}

\begin{problem}
  Explain why we know that $q'$ is not equal to \emph{any} of the
  numbers $r_n$ in our list.
\end{problem}

But\dots that means $q'$ is a real number in the interval $[0,1]$
which \emph{isn't in our list}---and our list was supposed to contain
\emph{all} such numbers! The only possible conclusion is that \emph{it
  is impossible to make such a list}, that is, there does not exist a
bijection between $\N$ and $[0,1]$. The real numbers are simply
\emph{too infinite} to fit in a list!  This also means, as promised,
that there are different kinds of infinity, some more infinitely
infinite than others.  Feel free to have fun proving this to your
friends and watching their brains explode.

\end{document}