\documentclass[12pt]{amsart}
\theoremstyle{plain}    
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}
\newtheorem*{exercise}{Exercise}
\newtheorem*{conjecture}{Conjecture}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{remark}{Remark}
\begin{document}
\title{Cardinality}
\section{Introduction}
\par\vspace{0.3 cm}
By the \textbf{cardinality} of a set $E$, we mean the number of elements in the set, sometimes denoted by $n(E)$.
\par\vspace{0.3 cm}
For a nonempty finite set $E$, $n(E)$ is clearly a natural number:
\[
E=\{1,3,6\}\quad n(E)=3\qquad S=\{a,b,c,d,e\} n(S)=5
\vspace{0.2 cm}
\]
It is easy to imagine the origin of the concept of a number and therefore of mathematics as a way to express cardinality. 
\par\vspace{0.3 cm}
What about a set like $\mathbb{N}=\{1,2,3,\ldots\}$?  The construct
\[
n(\mathbb{N})=\infty
\vspace{0.2 cm}
\]
expresses the fact that the set is not finite, but is not very helpful beyond that. How would we prove, given an arbitrary set $E$, that $n(E)=\infty$?  In fact, what exactly does that equation mean?
\par\vspace{0.3 cm}
The first person to systematically consider the cardinality of inifinite sets was George Cantor (1845-1918), who is regarded as one of the most original thinkers in the history of Mathematics.  Cantor's approach was based on the idea of \textbf{equivalence} of two sets, which he defined as:
\begin{definition}[set equivalence]
Two sets $A$ and $B$ are \textbf{equivalent} if there exists a 1-1 correspondence between them, that is, if there exists a function $f:A\rightarrow B$ that is 1-1 and onto.
\end{definition}
\begin{example}
Consider the sets
\[
A=\{1,3,4\}\quad\mbox{and}\quad B=\{a,b,e\}
\vspace{0.2 cm}
\]
The function $f:A\rightarrow B$ defined by $f(1)=b$, $f(3)=e$, and $f(4)=a$ is 1-1 and onto, so we say $A$ and $B$ are equivalent.  Cantor then argued that equivalent sets have the same cardinality, that is, if we can establish a 1-1 correspondence between the elements of two sets, they have the same cardinality.
\end{example}
\par\vspace{0.2 cm}
The advantage of this approach is that we are no longer limited to finite sets.  Consider
\[
A=\mathbb{N}=\{1,2,3,\ldots\}\quad\mbox{and}\quad B\subset\mathbb{Z}=-\mathbb{N}=\{-1,-2,-3,\ldots\}
\vspace{0.2 cm}
\]
define $f:A\rightarrow B$ by $f(a)=-a,\quad a\in A$.  Clearly this is a 1-1 correspondence between $A$ and $B$, so 
we would say $A$ and $B$ have the same cardinality, $n(A)=n(B)$.
\par\vspace{0.3 cm}
There are some suprising implications of set equivalence when we consider infinite sets.  Let
\[
A=\mathbb{N}=\{1,2,3,\ldots\}\quad\mbox{and}\quad B=\{1,3,5,\ldots\}
\vspace{0.2 cm}
\]
Now define $f:A\rightarrow B$ by $f(a)=2a-1,\quad a\in A\}$.  $f$ is clearly a 1-1 correspondence, so we conclude that
$A$ and $B$ have the same cardinality, that is, the same number of elements.  
\par\vspace{0.3 cm}
How can this be if there are elements in $A$ that do not belong to $B$?  $B$ is a proper subset of $A$.  
\par\vspace{0.3 cm}
It turns out that, for infinite sets, this does not make any difference.
\par\vspace{0.3 cm}
In fact, Cantor used this as the \textbf{definition} of an infinite set:  An infinite set is a set that can be put in $1-1$ correspondence with a proper subset.
\par\vspace{0.2 cm}
Once he had settled on these definitions, Cantor quickly discovered that a great many sets are in fact equivalent to $\mathbb{N}$, meaning they have the same cardinality.  Cantor denoted this cardinal number by the symbol $\aleph_0$.
\par\vspace{0.2 cm}
\begin{theorem}
\[
n(\mathbb{Z})=\aleph_0
\vspace{0.2 cm}
\]
\end{theorem}
\begin{proof}
Since $n(\mathbb{N})=\aleph_0$ by definition, all we need to do is show that $\mathbb{Z}$ is equivalent to $\mathbb{N}$, which we establish by finding a 1-1 correspondence between $\mathbb{N}$ and $\mathbb{Z}$.  Define
\[
f(n)=\left\{
\begin{array}{lcl}
\frac{1-n}{2} &\mbox{if}& n\in\{1,3,5,\ldots\}\\
\frac{n}{2} &\mbox{if}& n\in\{2,4,6,\ldots\}\\
\end{array}\right.
\vspace{0.2 cm}
\]
Clearly $f$ is a 1-1 correspondence between $\mathbb{Z}$ and $\mathbb{N}$, so they have the same cardinality, $\aleph_0$.
\end{proof}
So, there are exactly as many integers as there are natural numbers.
\par\vspace{0.3 cm}
Even more suprising is the fact that $n(\mathbb{Q})=\aleph_0$.  For simplicity, considere the positive rationals, each of which can be written as 
\[
q=\frac{m}{n}\quad m,n\in\mathbb{N}
\vspace{0.2 cm}  
\]
Represent $\mathbb{N}\times\mathbb{N}$ as a 2-dimensional table
\par\vspace{0.2 cm}
\begin{tabular}{c|ccccc}
$n/m$ & 1 & 2 & 3 & 4 & $\cdots$\\
\hline
1   & 1/1 & 1/2 & 1/3 & 1/4 & $\cdots$\\
2   & 2/1 & 2/2 & 2/3 & 2/4 & $\cdots$\\
3   & 3/1 & 3/2 & 3/3 & 3/4 & $\cdots$\\
4   & 4/1 & 4/2 & 4/3 & 4/4 & $\cdots$\\
$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\ddots$\\
\hline
\end{tabular}
Now cross off any entries that have a common factor in the numerator and denominator, and, starting from the $(1,1)$ element, number the remaining entries in serpentine fashion working down diagonally from the upper left hand corner, 
reversing direction at the end of each diagonal.
\par\vspace{0.2 cm}
A bit of thought should convince you that this construction will produce a 1-1 correspondence between $\mathbb{Q}$ and $\mathbb{N}$.
\par\vspace{0.2 cm}
So the cardinality of the rationals is the same as the cardinality of the natural numbers!
\par\vspace{0.2 cm}
Another suprising result:  Let $L$ be the set of points on the line segment $[0,1]$, and $S=[0,1]\times[0,1]$ the unit square.  Cantor established that $n(S)=n(L)$ with the following construction:
\par\vspace{0.2 cm}
Every element of $L$, that is, every element of $[0,1]$, can be written in decimal form as:
\[
l\in\L=0.a_1a_2a_3a_4\ldots\quad a_i\in\{0,1,2,\ldots,9\}
\vspace{0.2 cm}
\]
Identify $l$ with the ordered pair
\[
(0.a_1a_3a_5a_7,\ldots,0.a_2,a_4,a_6,\ldots)\in [0,1]\times[0,1]=S
\]
Again, a bit of thought should convince you that this is in fact a 1-1 correspondence between $[0,1]$ and $[0,1]\times[0,1]$, so $n(L)=N(S)$.
\par\vspace{0.3 cm}
This equivalence between the 1-dimensional set $L$ and the two dimensional set $S$ was so suprising that Cantor remarked "I see it, but I don't believe it". 
\par\vspace{0.2 cm}
Now we come to one of the most famous proofs of the last 200 years.  In 1873 Cantor was able to establish that it is \textbf{not} possible to find a 1-1 correspondence between $\mathbb{N}$ and $\mathbb{R}$, meaning in effect there are more real numbers than natural numbers (recall that there are exactly as many rationals as natural numbers).
\par\vspace{0.2 cm}
The proof is called "Cantor's diagonalization proof" and is a proof by contradiction.  For simplicity we consider the interval $(0,1)$.  (we can put this into 1-1 correspondence with $(-\infty,\infty)$ by $z=-\ln(x/(1-x)$).  Every number in this interval can be represented as $0.a_1a_2a_3\ldots$ where the $a_i$ are decimal digits.
\par\vspace{0.2 cm}
Suppose we have a 1-1 correspondence between $S=(0,1)$ and $\mathbb{N}$, expressed in the form of a list whose first element is $f(1)$, second element is $f(2)$, $n^{th}$ element is $f(n)$, and so on (we can always represent a 1-1 correspondence with $\mathbb{N}$ as a list $\{f(1),f(2),f(3),\ldots\}$).  The list looks like this:
\[
\begin{array}{cc}
1 & 0.a_{11}a_{12}a_{13}a_{14}\ldots\\
2 & 0.a_{21}a_{22}a_{23}a_{24}\ldots\\
3 & 0.a_{31}a_{32}a_{33}a_{34}\ldots\\
\vdots & \vdots\\
\end{array}
\]
The claim that this is a 1-1 correspondence is equivalent to saying every real number is in the list somewhere.  Now 
we show that this claim has to be false by constructing a real number not in the list. 
\par\vspace{0.3 cm}
Construct a real number $b$ from the list as follows:
\begin{itemize}
\item The first digit of $b$ is something other than $a_{11}$
\item The second digit of $b$ is something other than $a_{22}$
\item The third digit of $b$ is something other than $a_{33}$
\end{itemize}
\par\vspace{0.3 cm}
and so on.  Then clearly, $b\neq a_1$, $b\neq a_2$, $b\neq a_3$, etc. so $b$ is not in the list, contradicting the claim that the list contained all real numbers.  This establishes that the natural numbers cannot be put into 1-1 correspondence with the reals.
\par\vspace{0.3 cm}
Cantor denoted the cardinal number of $\mathbb{R}$ by $\aleph_1$ and was able to show that
\[
\aleph_1=2^{\aleph_0}
\vspace{0.2 cm}
\]
That is, there are exactly as many real numbers as there are \textit{subsets} of the natural numbers.
\par\vspace{0.3 cm}
He went on to define larger and larger cardinal numbers in this fashion,
\[
\aleph_2=2^{\aleph_1}
\vspace{0.2 cm}
\]
A set with cardinality $\aleph_0$ is called \textbf{countable}, (because counting is essentially the same as establishing a 1-1 correspondence between the set and $\mathbb{N}$ or a subset of $\mathbb{N}$).
\par\vspace{0.3 cm}
The uncountability of the reals has far-reaching consequences which were not even imagined at the time of Cantor's discovery.  Goedell used it in the proof of his famous incompleteness theorem, and it is used to establish things like the existence of problems that cannot be solved by a computer program (just show that the set of possible programs is at most countable, and the set of problems is uncountable). 
\par\vspace{0.3 cm}
A suprising consequence of the uncountablility of $\mathbb{R}$ is the fact that since $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ are all countable, and $\mathbb{R}$ is not, the uncountable part, which must be the overwhelming majority of $\mathbb{R}$, is the irrationals.  
\par\vspace{0.3 cm}
Even more remarkable, if we divide the irrationals into the \textit{algebraics}, meaning numbers like $\sqrt{2}$ that can be obtained as a root of a polynomial with integer coefficients, and the \textit{transcendentals} like $e$ and $\pi$, which cannot, it turns out that the algebraics are countable, so the overwhelming majority of real numbers are in fact transcendental.  
\par\vspace{0.3 cm}
How can it be that, out of this enormous set, even Mathematics students usually can only name a handful?  The reason is that the vast majority of them are simply infinite, nonrepeating, nonterminating sequences of decimal digits, 
which cannot be written down or stored in a computer, or even named (we would not have enough names because the number of possible names is at most countable). So, most of them are doomed to remain anonymous.


\end{document}



