\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumerate}

\usepackage{hyperref}

\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}

\usepackage{wasysym}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.5in}
\setlength{\textwidth}{7in}

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}


\newcommand{\F}{\mathbb{F}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}

\newcommand{\LEMMA}{\vspace{0.05in} \noindent \fbox{\large\bf Lemma:}  }
\newcommand{\COR}{\vspace{0.05in} \noindent \fbox{\large\bf Corollary:}  }
\newcommand{\DEF}{\vspace{0.05in} \noindent \fbox{\large\bf Definition:}  }
\newcommand{\THM}{\vspace{0.05in} \noindent \fbox{\large\bf Theorem:}  }
\newcommand{\EX}{\vspace{0.05in} \noindent \fbox{\large\bf Example:}  }
\newcommand{\bproof}{\vspace{0.1in} \noindent {\bf Proof:} }
\newcommand{\eproof}{$\blacksquare$ \vspace{0.05in}}


\begin{document}

\pagestyle{empty}

\noindent
{\bf Math 2110}
\hfill {\Large \bf The Cantor-Schr\"{o}der-Bernstein Theorem} \hfill 
{\bf Tech. of Proof}

\vspace{0.1in}

\DEF Let $A$ and $B$ be sets. We say that $A$ and $B$ have the same {\bf cardnality} (denoted $|A|=|B|$ or $\mathrm{card}(A)=\mathrm{card}(B)$)
 if there exists a bijection (i.e., a one-to-one and onto = invertible function) from $A$ to $B$.
 
\vspace{0.05in}

\noindent 
Notice that\dots

\vspace{-0.05in}

\begin{description} \setlength\itemsep{0pt}
\item[Reflexive:]  $|A|=|A|$ (using the identity function),
\item[Symmetric:] $|A|=|B|$ implies $|B|=|A|$ (the inverse of a bijective function exists and is bijective itself), and 
\item[Transitive:] if both $|A|=|B|$ and $|B|=|C|$, then $|A|=|C|$ (the composition of two bijective functions is bijective). 
\end{description}

\vspace{-0.05in}

\noindent
These facts tell us that the relation $|A|=|B|$ is an {\bf equivalence relation}.

\vspace{0.15in}

\noindent
If cardinality is to measure {\it size}, we should be able to compare different sizes with some kind of $\leq$ relation. 

\vspace{0.05in}

\DEF We say $|A| \leq |B|$ if there exists an injection (a one-to-one function) from $A$ to $B$. 

\vspace{0.05in}

One can show that there is an injection from $A$ to $B$ if and only if there is a surjection from $B$ to $A$. We will skip the proof. 
However, keeping this fact in mind, we could replace the following discussions built on one-to-one functions with discussions built on onto functions.

\vspace{0.05in}

\noindent
Notice that\dots

\vspace{-0.05in}

\begin{description} \setlength\itemsep{0pt}
\item[Reflexive:] $|A| \leq |A|$ (using the identity function), 
\item[Anti-Symmetric:] if both $|A| \leq |B|$ and $|B| \leq |A|$, then $|A|=|B|$ (this requires proof), and
\item[Transitive:] $|A| \leq |B|$ and $|B| \leq |C|$ implies that $|A| \leq |C|$ (the composition of two injective functions is injective).
\end{description}

\vspace{-0.05in}

\noindent
These facts tell us that the relation $|A| \leq |B|$ is a {\bf partial order}.

\vspace{0.1in}

Notice that we didn't supply a quick justification of anti-symmetry. It turns out that this is a little tricky to establish (Cantor didn't immediately see how to prove this). In fact, this result is called the Cantor-Schr\"{o}der-Bernstein theorem.

\vspace{0.1in}

\THM Let $A$ and $B$ be sets such that $|A| \leq |B|$ and $|B| \leq |A|$. Then $|A|=|B|$.

\bproof
Since $|A| \leq |B|$ there exists an injection $f:A \to B$ and since $|B| \leq |A|$ there exists an injection $g:B \to A$.
Let's define the follow sets inductively. First, let $S_1 = A - g(B)$. Then for each $n \geq 1$, let $S_{n+1} = g(f(S_n))$. Finally
let $\displaystyle{S = \bigcup_{n=1}^{\infty} S_n}$. We can now define our candidate bijection. Let $h:A \to B$ be defined by

\vspace{-0.1in}

$$h(x) = \left\{ \begin{array}{cl}  f(x) & x \in S \vspace{0.1in} \\ g^{-1}(x) & x \in A-S \end{array} \right.$$

First, notice that if $x \in A-S$, then $x \not\in S$. So $x \not\in S_n$ for all $n \geq 1$. In particular, $x \not\in S_1=A-g(B)$.
Therefore, $x \in g(B)$, so $x$ is the image of something in $B$. But $g$ is injective, so $x$ is the image of exactly one element
of $B$. We call this (unique) element ``$g^{-1}(x)$''. Therefore, $h$ is a well-defined function.

\vspace{0.05in}

Let's show $h$ is injective. Suppose that $h(x)=h(y)$. There are four possibilities: (1) $x,y \in S$, (2) $x,y \in A-S$, 
(3) $x \in S$ and $y \in A-S$, and (4) $x\in A-S$ and $y \in S$. In case (1): $f(x)=h(x)=h(y)=f(y)$ thus $x=y$ because $f$ is injective. 
Case (2): $g^{-1}(x)=h(x)=h(y)=g^{-1}(y)$. Note that $z=g^{-1}(x)=g^{-1}(y)$ is the element which maps to $x$ and maps to $y$. 
Now $g$ is well-defined, so these better be the same. Thus $x=y$. Finally, cases (3) and (4) are symmetric, so without loss of generality, 
let's assume that $x \in S$ and $y \in A-S$. Thus $f(x)=h(x)=h(y)=g^{-1}(y)$ so that $g(f(x))=y$. Now $x \in S$ so $x \in S_m$ for some 
$m \geq 1$. Then $y = g(f(x)) \in g(f(S_m))=S_{m+1}$. Therefore, $y \in S$ which is a contradiction. Therefore, cases (3) and (4) cannot 
actually occur. Thus in all cases we have $x=y$. Therefore, $h$ is one-to-one.

\vspace{0.05in}

We also need to show that $h$ is surjective (i.e., onto). Suppose that $y \in B$. Either $y \in f(S)$ or $y \not\in f(S)$. If $y \in f(S)$, then
$y=f(x)$ for some $x \in S$. Now $x \in S$, so $h(x) = f(x) = y$. Therefore, $y$ is in the range of $h$. 

Next, consider $y \not\in f(S)$. Then $g(y) \in g(B)$ so $g(y) \not\in A-g(B)=S_1$. Could $g(y)$ be in $S_{n+1}=g(f(S_n))$ for $n>1$? If so, $g(y)=g(z)$ for some $z \in f(S_n)$. However, $g$ is one-to-one, so $g(y)=g(z)$ implies $y=z \in f(S_n)$. But since $S_n$ is contained in $S$, this means $y \in f(S)$ (contradicting our assumption). So $g(y)$ cannot belong to any $S_n$ and thus $g(y) \not\in S$. We now have $g(y) \in A-S$ and so $h(g(y))=g^{-1}(g(y))=y$.
Once again, this means $y$ is in the range of $h$. Therefore, in both cases (i.e., $y \in f(S)$ and $y\not\in f(S)$), we have $y$ is in the range of $h$. Thus $h$ is surjective.

\vspace{0.05in}

We have shown that $h$ is injective and surjective. Thus $h$ is bijective, so there exists a bijection from $A$ to $B$.
Therefore, $|A|=|B|$. 
\eproof



\end{document}
