Last revised 12feb11
\begin{document} \maketitle
\begin{document}
\textbf{Definition: } Two sets are said to have the same \textit{cardinality}
if there is a bijection from one to the other.
\textbf{Theorem: } Two sets have the same cardinality,
card($A$)=card($B$), if there exist injections
$\beta: A \rightarrow B$ and $\alpha : B \rightarrow A$.
\textbf{What is to be proved}\\
The hypothesis says that there exist two injections (1:1 mapping).
The conclusion requires us to construct a bijection (1:1 and onto mapping)
$ A \rightarrow B $. Note that if either $\alpha$ or $\beta$ are also
surjective (onto) to begin with, then there nothing to be proved.
Also, we couldn't find an amusing or instructive figure to decorate this
lesson, so the photograph is of Prof. Guyla Koenig. It is his proof we shall
give here, since historically earlier proofs are more difficult.
The Wikipedia recalls the convoluted history of this theorem.
\textbf{ Strategy of proof} \\
Without loss of generality, we assume $A \cap B = \emptyset$.
Mathematicians like to say such things but rarely say why there
is no loss of generality. One way is to paint all of the elements
of A red, and all elements of B blue, and then they two sets would
no longer have any elements in common.
We'll next take the (disjoint) union $C = A \cup B$ and \textit{partition}
it into disjoint subsets $D$ and define a bijection
$ D\cap A \rightarrow D\cap B$. All of these bijections together then
constitute a bijection $A \rightarrow B$.
\textbf{Defining successors} \\
We define a \textit{successor function} on $C$ by
\begin{eqnarray*}
c'& =& \alpha(c) \mbox{ if } c \in B \\
c'& =& \beta(c) \mbox{ if } c \in A \\
\end{eqnarray*}.
This is well defined because $c$ must be in either $A$ or $B$ and
cannot be in both.
Note that by hypothesis, not only is the successor of an element in $C$
unique (both $\alpha$ and $\beta$ are functions) but if an element
has a \textit{ predecessor }, it too is unique (both $\alpha$ and $\beta$
are injective).
\textbf{Defining the succession sequences } \\
For each element $c \in C $ we can form its \textit{ succession sequence}
\[ \Sigma(c) :=\{ ..., q_3, q_2, q_1, c, p_1, p_2, p_3,... \}
\mbox{ where all } q_n = q'_{n+1}, p_{n+1} = p'_n . \]
Of course, we let $q_0=c=p_0$ so that this definition makes sense for all
$n\in \mathbb{N}$. But there are other issues to resolve. While the
sequence always progresses to the right from $c$ because every element
of $C$ has a successor, in may not extend very far to the left. Furthermore,
we do not assume that every element to the right or to the left is different.
The sequence could repeat after a finite number of steps.
But whatever $\Sigma(c)$ does, it is unique in the following sense. It cannot
branch apart at any point to the right, because successors are unique. Nor
can two branches come together on the left, becuse predecessors are unique,
insofar as there are any.
\textbf{The succession sequences are a partition}\\
Clearly every element of $C$ is a member of its own succession sequence.
But it is not in two different succession sequences. For if it were,
these two succession sequence would be identical.
Note, in passing, in each bijection sequence, membership if $A$ and
$B$ alterates. We shall define a bijection from
$ \gamma : \Sigma(c)\cap A \rightarrow \Sigma(c)\cap B $.
\textbf{Definition of}$\gamma$ \\
Now exactly one of three things could happen for a particular succession
sequence. It could continue forever on the left as it necessarily does
on the right. It could stop with an element $a\in A$, or stop with an
element $b \in B$.
In the first two cases, every element in $ \Sigma(c)\cap B $ has a
predecessor. If we define $\gamma = \beta $ ( restricted to
$ \Sigma(c)\cap A $ of course) then $\gamma $ is injective since $\beta$
is given to be so. But it is also surjective, since every element
in $ \Sigma(c)\cap B$ is the successor of its predecessor.
Note that the previous argument could not be applied if the first
element on the left is in $B$. Then for every element in $\Sigma(c)$,
its succession sequence would be the same
$ \Sigma=\{ b, a_1, b_2, a_3, .... \}$,
where each $a_{2n+1} = \alpha( b_{2n})$ for all $n = 0,1,2,3 ...$, and
$b_0 := b$ for consistency. Since the inverse
$\alpha^{-1}$
is defined on all of $\Sigma\cap A $ we take $ \gamma = \alpha^{-1} $
restricted to $\Sigma \cap A$.
\textit{Comment}
We hope you will find this proof easier to follow than the one in
the book. Also note, nothing is said just how vastly infinite
the sets are.
\end{document}<\div><\pre><\body>
The Cantor-Bernstein-Schroeder Theorem
\begin{document} \maketitle
\begin{document}
\textbf{Definition: } Two sets are said to have the same \textit{cardinality}
if there is a bijection from one to the other.
\textbf{Theorem: } Two sets have the same cardinality,
card($A$)=card($B$), if there exist injections
$\beta: A \rightarrow B$ and $\alpha : B \rightarrow A$.
\textbf{What is to be proved}\\
The hypothesis says that there exist two injections (1:1 mapping).
The conclusion requires us to construct a bijection (1:1 and onto mapping)
$ A \rightarrow B $. Note that if either $\alpha$ or $\beta$ are also
surjective (onto) to begin with, then there nothing to be proved.
Also, we couldn't find an amusing or instructive figure to decorate this
lesson, so the photograph is of Prof. Guyla Koenig. It is his proof we shall
give here, since historically earlier proofs are more difficult.
The Wikipedia recalls the convoluted history of this theorem.
\textbf{ Strategy of proof} \\
Without loss of generality, we assume $A \cap B = \emptyset$.
Mathematicians like to say such things but rarely say why there
is no loss of generality. One way is to paint all of the elements
of A red, and all elements of B blue, and then they two sets would
no longer have any elements in common.
We'll next take the (disjoint) union $C = A \cup B$ and \textit{partition}
it into disjoint subsets $D$ and define a bijection
$ D\cap A \rightarrow D\cap B$. All of these bijections together then
constitute a bijection $A \rightarrow B$.
\textbf{Defining successors} \\
We define a \textit{successor function} on $C$ by
\begin{eqnarray*}
c'& =& \alpha(c) \mbox{ if } c \in B \\
c'& =& \beta(c) \mbox{ if } c \in A \\
\end{eqnarray*}.
This is well defined because $c$ must be in either $A$ or $B$ and
cannot be in both.
Note that by hypothesis, not only is the successor of an element in $C$
unique (both $\alpha$ and $\beta$ are functions) but if an element
has a \textit{ predecessor }, it too is unique (both $\alpha$ and $\beta$
are injective).
\textbf{Defining the succession sequences } \\
For each element $c \in C $ we can form its \textit{ succession sequence}
\[ \Sigma(c) :=\{ ..., q_3, q_2, q_1, c, p_1, p_2, p_3,... \}
\mbox{ where all } q_n = q'_{n+1}, p_{n+1} = p'_n . \]
Of course, we let $q_0=c=p_0$ so that this definition makes sense for all
$n\in \mathbb{N}$. But there are other issues to resolve. While the
sequence always progresses to the right from $c$ because every element
of $C$ has a successor, in may not extend very far to the left. Furthermore,
we do not assume that every element to the right or to the left is different.
The sequence could repeat after a finite number of steps.
But whatever $\Sigma(c)$ does, it is unique in the following sense. It cannot
branch apart at any point to the right, because successors are unique. Nor
can two branches come together on the left, becuse predecessors are unique,
insofar as there are any.
\textbf{The succession sequences are a partition}\\
Clearly every element of $C$ is a member of its own succession sequence.
But it is not in two different succession sequences. For if it were,
these two succession sequence would be identical.
Note, in passing, in each bijection sequence, membership if $A$ and
$B$ alterates. We shall define a bijection from
$ \gamma : \Sigma(c)\cap A \rightarrow \Sigma(c)\cap B $.
\textbf{Definition of}$\gamma$ \\
Now exactly one of three things could happen for a particular succession
sequence. It could continue forever on the left as it necessarily does
on the right. It could stop with an element $a\in A$, or stop with an
element $b \in B$.
In the first two cases, every element in $ \Sigma(c)\cap B $ has a
predecessor. If we define $\gamma = \beta $ ( restricted to
$ \Sigma(c)\cap A $ of course) then $\gamma $ is injective since $\beta$
is given to be so. But it is also surjective, since every element
in $ \Sigma(c)\cap B$ is the successor of its predecessor.
Note that the previous argument could not be applied if the first
element on the left is in $B$. Then for every element in $\Sigma(c)$,
its succession sequence would be the same
$ \Sigma=\{ b, a_1, b_2, a_3, .... \}$,
where each $a_{2n+1} = \alpha( b_{2n})$ for all $n = 0,1,2,3 ...$, and
$b_0 := b$ for consistency. Since the inverse
$\alpha^{-1}$
is defined on all of $\Sigma\cap A $ we take $ \gamma = \alpha^{-1} $
restricted to $\Sigma \cap A$.
\textit{Comment}
We hope you will find this proof easier to follow than the one in
the book. Also note, nothing is said just how vastly infinite
the sets are.
\end{document}<\div><\pre><\body>