\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{epsfig}

\setlength{\topmargin}{-.55in} \setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in} \setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.1in}

\begin{document}
\title{Are All Infinities Created Equal?}
\author{Guram Bezhanishvili\footnote{Department of Mathematical Sciences,
New Mexico State University, Las Cruces, NM 88003;
\texttt{gbezhani@nmsu.edu}.}\thinspace\footnote{With thanks to Joel
Lucero-Bryan.}}

\date{}
\maketitle

%\begin{center}
%{\large  \textbf{Guram Bezhanishvili}{}}\footnote{Department of Mathematical Sciences,
%New Mexico State University, Las Cruces, NM 88003;
%\texttt{gbezhani@nmsu.edu}.}\thinspace\footnote{With thanks to Joel Lucero-Bryan.}\smallskip
%\end{center}

Georg Ferdinand Ludwig Philip Cantor (1845--1918), the founder of
set theory, and considered by many as one of the most original minds
in the history of mathematics, was born in St.\ Petersburg, Russia
in 1845. His parents, who were of Jewish descent, moved the family
to Frankfurt, Germany in 1856. Georg entered the Wiesbaden Gymnasium
at the age of 15, and two years later began his university career at
Z\"{u}rich. In 1863 he moved to the University of Berlin, which
during Cantor's time was considered the world's center of
mathematical research. Four years later Cantor received his
doctorate from the great Karl Weierstrass (1815--1897). In 1869
Cantor obtained an unpaid lecturing post, which ten years later
flourished into a full professorship, at the minor University of
Halle. However, he never achieved his dream of holding a Chair of
Mathematics at Berlin. It is believed that one of the main reasons
for this was the rejection of his theories of infinite sets by the
leading mathematicians of that time, most noticeably by Leopold
Kronecker (1823--1891), a professor at the University of Berlin and
a very influential figure in German mathematics, both mathematically
and politically.

Cantor married in 1874 and had two sons and four daughters. Ten
years later Georg suffered the first of the mental breakdowns that
were to plague him for the rest of his life. He died in 1918 in a
mental hospital at Halle. By that time his revolutionary ideas
were becoming accepted by some of the leading figures of the new
century. For example, one of the greatest mathematicians of the
twentieth century, David Hilbert (1862--1943), described Cantor's
new mathematics as ``the most astonishing product of mathematical
thought" \cite[p. 359]{GBHollingdale}, and claimed that ``no one
shall ever expel us from the paradise which Cantor has created for
us" \cite[p. 353]{GBHollingdale}.

In this project we will learn about Cantor's treatment of infinite
sets. We will discuss the cardinality of a set, the notion of
equivalence of two sets, and study how to compare infinite sets with
each other. We will introduce countable sets and show that many sets
are countable, including the set of integers and the set of rational
numbers. We will also discuss Cantor's diagonalization method which
allows us to show that not every infinite set is countable. In
particular, we will show that the set of real numbers is not
countable. We will also examine the cardinal number $\aleph_0$, the
first in the hierarchy of transfinite cardinal numbers, and obtain a
method that allows us to create infinitely many transfinite cardinal
numbers.

We will learn much of this by studying and working with the
historical source \cite{GBCantor}, which is an English translation
of two papers by Cantor \cite{GBCantor1895,GBCantor1897} that appeared
in 1895 and 1897. More on Georg Cantor can be found in
\cite{GBDunham90,GBHollingdale,GBLaubenbacher} and in the literature cited
therein.

We begin by reading Cantor's definition of the cardinal number of a
given set. Note that in this translation Jourdain uses ``aggregate"
instead of the more familiar ``set."

\vspace{3mm}

\noindent 1. Read carefully the following quote from Cantor.

\begin{quote}
{\sf  Every aggregate $M$ has a definite ``power," which we also
call its ``cardinal number."

We will call by the name ``power" or ``cardinal number" of $M$ the
general concept which, by means of our active faculty of thought,
arises from the aggregate $M$ when we make abstraction of the
nature of its various elements $m$ and of the order in which they
are given.

We denote the result of this double act of abstraction, the
cardinal number or power of $M$, by $$\overline{\overline{M}}.$$}
\end{quote}

\noindent What do you think Cantor means by ``cardinal number"? Why?
Given a set $M$ consisting of ten round marbles, each of a different
color, what is $\overline{\overline{M}}$?

\vspace{3mm}

\noindent 2. Read the following quote from Cantor.

\begin{quote}
{\sf We say that two aggregates $M$ and $N$ are ``equivalent," in
signs
$$ M \sim N \ \ \ {\sf{or}} \ \ \ N \sim M,  $$
if it is possible to put them, by some law, in such a relation to
one another that to every element of each one of them corresponds
one and only one element of the other.}
\end{quote}

\noindent In modern terminology describe what it means for two sets
to be equivalent.

\vspace{3mm}

\noindent 3. Prove the following claim of Cantor.

\begin{quote}
{\sf Every aggregate is equivalent to itself:
$$  M \sim M.  $$}
\end{quote}

\vspace{3mm}

\noindent 4. Prove the following claim of Cantor.

\begin{quote}
{\sf If two aggregates are equivalent to a third, they are
equivalent to one another, that is to say:
$$  {\sf from} \ \ \ M \sim P \ \ \ {\sf {and}} \ \ \ N \sim P \ \ \
{\sf{follows}} \ \ \ M \sim N.  $$}
\end{quote}

\vspace{3mm}

\noindent 5. Read carefully the following quote from Cantor.

\begin{quote}
{\sf  Of fundamental importance is the theorem that two aggregates
$M$ and $N$ have the same cardinal number if, and only if, they
are equivalent: thus,
\begin{center}
from $M \sim N$, we get $\overline{\overline{M}} =
\overline{\overline{N}}$,
\end{center}
and
\begin{center}
from $\overline{\overline{M}} = \overline{\overline{N}}$, we get
$M \sim N$.
\end{center}
Thus the equivalence of aggregates forms the necessary and
sufficient condition for the equality of their cardinal numbers.}
\end{quote}

\noindent Explain in your own words what Cantor means in the above.

\vspace{3mm}

\noindent 6.  Let {\bf P} be the set of all perfect squares
$$  \{\, 0, 1, \ 4, \ 9, \ 16, \ 25, \ \ldots \, \} ,  $$
and let {\bf N} denote the set of all natural numbers
$$ \{\, 0, 1, \ 2, \ 3, \ 4, \ 5, \ \ldots \, \}.  $$
From Cantor's statement above, do {\bf P} and {\bf N} have the
same cardinality?  Justify your answer.

\vspace{3mm}

\noindent 7.  Let {\bf Z} denote the set of all integers.
Do {\bf N} and {\bf Z} have the same cardinality? Justify your
answer.

\vspace{3mm}

\noindent 8.  Let ${\bf N}\times{\bf N}$ denote the Cartesian
product of {\bf N} with itself; that is $${\bf N}\times{\bf
N}=\{(n,m):n,m\in{\bf N}\}.$$ Do {\bf N} and ${\bf N}\times{\bf N}$
have the same cardinality? Justify your answer. Hint: Draw a picture
of ${\bf N}\times{\bf N}$. Can you label each element of ${\bf
N}\times{\bf N}$ by a unique natural number?

\vspace{3mm}

\noindent 9.  Let {\bf Q} denote the set of all rational numbers;
that is $${\bf Q}=\{\frac{a}{b}:a\in{\bf Z} \ \mbox{and} \ b\in{\bf
N}-\{0\}\}.$$ What is the cardinality of {\bf Q}? Justify your
answer. Hint: Establish a 1-1 correspondence between {\bf Q} and (a
subset of) ${\bf Z}\times({\bf N}-\{0\})$ and modify your solution
to (8).

\vspace{3mm}

\noindent 10. Read carefully the following quote from Cantor.

\begin{quote}
{\sf If for two aggregates $M$ and $N$ with the cardinal numbers
$\mathfrak{a}=\overline{\overline{M}}$ and
$\mathfrak{b}=\overline{\overline{N}}$, both the conditions:
\begin{enumerate}
\item[(a)] There is no part\footnote{The modern
terminology is ``subset".} of $M$ which is equivalent to $N$,
\item[(b)] There is a part $N_1$ of $N$, such that $N_1\sim M$,
\end{enumerate}
are fulfilled, it is obvious that these conditions still hold if
in them $M$ and $N$ are replaced by two equivalent aggregates $M'$
and $N'$. Thus they express a definite relation of the cardinal
numbers $\mathfrak{a}$ and $\mathfrak{b}$ to one another.

Further, the equivalence of $M$ and $N$, and thus the equality of
$\mathfrak{a}$ and $\mathfrak{b}$, is excluded; for if we had
$M\sim N$, we would have, because $N_1\sim M$, the equivalence
$N_1\sim N$, and then, because $M\sim N$, there would exist a part
$M_1$ of $M$ such that $M_1\sim M$, and therefore we should have
$M_1\sim N$; and this contradicts the condition (a).

Thirdly, the relation of $\mathfrak{a}$ to $\mathfrak{b}$ is such
that it makes impossible the same relation of $\mathfrak{b}$ to
$\mathfrak{a}$; for if in (a) and (b) the parts played by $M$ and
$N$ are interchanged, two conditions arise which are contradictory
to the former ones.

We express the relation of $\mathfrak{a}$ to $\mathfrak{b}$
characterized by (a) and (b) by saying: $\mathfrak{a}$ is ``less"
than $\mathfrak{b}$ or $\mathfrak{b}$ is ``greater" than
$\mathfrak{a}$; in signs $$\mathfrak{a}<\mathfrak{b} \ \mbox{or} \
\mathfrak{b}>\mathfrak{a}.$$}
\end{quote}

\noindent Describe in modern terminology when two cardinals
$\mathfrak{a}=\overline{\overline{M}}$ and
$\mathfrak{b}=\overline{\overline{N}}$ are in the relation
$\mathfrak{a}<\mathfrak{b}$.

\vspace{3mm}

\noindent 11. Prove the following claim of Cantor.

\begin{quote}
{\sf We can easily prove that, $$\mbox{if} \
\mathfrak{a}<\mathfrak{b} \ \mbox{and} \
\mathfrak{b}<\mathfrak{c}, \ \mbox{then we always have} \
\mathfrak{a}<\mathfrak{c}.$$}
\end{quote}

\vspace{3mm}

\noindent 12. Read carefully the following quote from Cantor.

\begin{quote}
{\sf Aggregates with finite cardinal numbers are called ``finite
aggregates," all others we will call ``transfinite aggregates" and
their cardinal numbers ``transfinite cardinal numbers."

The first example of a transfinite aggregate is given by the
totality of finite cardinal numbers $\nu$; we call its cardinal
number ``Aleph-zero," and denote it by $\aleph_0$; }
\end{quote}

\noindent In the modern terminology, a set whose cardinal number is
$\aleph_0$ is called ``countable." What symbol is used today to
denote the ``totality of finite cardinal numbers $\nu$"?

\vspace{3mm}

\noindent 13. Prove the following claim of Cantor.

\begin{quote}
{\sf The number $\aleph_0$ is greater than any finite number
$\mu$: $$\aleph_0>\mu.$$ }
\end{quote}

\vspace{3mm}

\noindent 14. Prove the following claim of Cantor.

\begin{quote}
{\sf On the other hand, $\aleph_0$ is the least transfinite
cardinal number. If $\mathfrak{a}$ is any transfinite cardinal
number different from $\aleph_0$, then
$$\aleph_0<\mathfrak{a}.$$ }
\end{quote}

\noindent Hint: Let $\mathfrak{a}=\overline{\overline{A}}$. Can you
define a 1-1 map from {\bf N} into $A$? What can you deduce from
this?

\vspace{3mm}

\noindent 15. Let $[0,1]$ denote the set of all real numbers between
$0$ and $1$. Show that $\aleph_0<\overline{\overline{[0,1]}}$. We
outline what is now known as Cantor's diagonalization method as one
way to prove this. Represent real numbers in $[0,1]$ as infinite
decimals (which do not end in infinitely repeating $9$'s). Assume
that ${\bf N}\sim [0,1]$. Then to each infinite decimal one can
assign a unique natural number, so the infinite decimals can be
enumerated as follows:
\[
\begin{array}
[c]{c}
.a_{11}a_{12}\ldots a_{1n}\ldots\\
.a_{21}a_{22}\ldots a_{2n}\ldots\\
\vdots\\
.a_{n1}a_{n2}\ldots a_{nn}\ldots\\
\vdots
\end{array}
\]
Can you construct an infinite decimal $.b_1b_2\ldots b_n\ldots$
such that $a_{nn}\neq b_n$ for each positive $n$? What can you
conclude from this?

\vspace{3mm}

\noindent 16. Let {\bf R} denote the set of all real numbers. Is
$\overline{\overline{\bf R}}$ strictly greater than $\aleph_0$?
Justify your answer.

\vspace{3mm}

\noindent 17. For a set $M$, let $\mathcal{P}(M)$ denote the set of
all subsets of $M$; that is $\mathcal{P}(M)=\{N:N\subseteq M\}$.
Prove the following claim of Cantor:
$$\overline{\overline{\mathcal{P}(M)}} > \overline{\overline{M}}.$$
Hint: Employ a generalized version of Cantor's
diagonalization method. Assume that $M\sim\mathcal{P}(M)$. Then
there is a 1-1 and onto function $f:M\to\mathcal{P}(M)$. Consider
the set $N=\{m\in M: m\notin f(m)\}$. Can you deduce that
$N\subseteq M$ is not in the range of $f$? Does this imply a
contradiction?

\vspace{3mm}

\noindent 18. Using the previous exercise, give an infinite
increasing sequence of transfinite cardinal numbers.

\section*{Notes to the Instructor}

This project is designed for an undergraduate course in discrete
mathematics. It could be assigned as a three-week project on naive
set-theory with an emphasis on 1-1 correspondences. Since some of
Cantor's writings require nontrivial interpretations, it is
advisable that in the beginning the instructor leads the class
carefully, especially in reading Cantor's ``definition" of cardinal
number. The instructor may also wish to lead the class in
discovering that the set of rational numbers is countable, and
especially in using Cantor's diagonalization method to show that the
set of real numbers is not countable. There is a shadow of the axiom
of choice in Cantor's claim that $\aleph_0<\mathfrak{a}$ for any
transfinite cardinal number $\mathfrak{a}$ different from $\aleph_0$
(Exercise 14). The instructor may wish to spend a little bit of
class time on giving an informal explanation of the main idea behind
the axiom of choice.

\begin{thebibliography}{10}

\bibitem{GBCantor1895} Cantor, G.,
\emph{Beitr\"{a}ge zur Begr\"{u}ndung der transfiniten
Mengenlehre. I}, Mathematische Annalen \textbf{46} (1895),
481--512.

\bibitem{GBCantor1897} Cantor, G.,
\emph{Beitr\"{a}ge zur Begr\"{u}ndung der transfiniten
Mengenlehre. II}, Mathematische Annalen \textbf{49} (1897),
207--246.

\bibitem{GBCantor} Cantor, G.,
\emph{Contributions to the Founding of the Theory of Transfinite
Numbers}, Philip Jourdain (translator), Dover Publications Inc.,
New York, 1952.

\bibitem{GBDunham90} Dunham, W.,
\emph{Journey Through Genius. The Great Theorems of Mathematics},
John Wiley \& Sons Inc., New York, 1990.

\bibitem{GBHollingdale} Hollingdale, S.,
\emph{Makers of Mathematics}, Penguin Books, New York, 1994.

\bibitem{GBLaubenbacher} Laubenbacher, R., Pengelley, D.,
\emph{Mathematical Expeditions: Chronicles by the Explorers},
Springer Verlag, New York, 1999.

\end{thebibliography}

\end{document}