Last revised 12feb11

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>