Questions about the Schroeder-Bernstein Theorem

Question

The following is the Schroeder-Bernstein Theorem in Real Analysis with Real Applications by Donsig and Davidson p.$63$:

There are certain parts of the proof that I'm having trouble understanding. When I try drawing a diagram using Figure $2.6$ as a reference, for example, I'm unable to complete the diagram using a finite number of points. That is, using Figure $2.6$ I replaced the "ellipsis block" in both $A$ and $B$ by $A_{4}$ and $B_{4}$. Then I assigned exactly one point to each of $A_{1},A_{2},A_{3},A_{4},$ and $A_{5}$. I repeated the process with $B$ and assigned exactly one point to each $B_{1},B_{2},B_{3},B_{4},$ and $B_{5}$. But then applying the recursive process in the given proof, I can't apply the function $f$ to $A_{4}$ since this would imply the existence of some subset $B_{5}$ of $B$ which doesn't exist in the diagram that I've constructed. I'd like to know where I'm going wrong or what important assumption I'm missing.

Also, I'm unsure what $(fg)^{i-1}$ is supposed to represent. Is it supposed to be some sort of composite function made up of both $f$ and $g$, raised to the power $i-1$?

Answer 1

It's an infinite process, we have $B_1=B\setminus f(A)$, then $$A_1=g(B_1),\ B_2=f(A_1),\ A_2=g(B_2),\ \dots, B_5=f(A_4),\ A_5=g(B_5),\ \dots$$ Yes, $(fg)^{i-1}$ is the $i-1$-fold composition of the composite $fg$ with itself. If $i-1=0$, we mean the identity function.

Answer 2

The OP writes

Then I assigned exactly one point to each of $A_{1},A_{2},A_{3},A_{4},$ and $A_{5}$. I repeated the process with $B$ and assigned exactly one point to each $B_{1},B_{2},B_{3},B_{4},$ and $B_{5}$

This 'proof probing' can be actualized by taking a concrete example and 'running it thru' the proof diagram.

Let $f: \Bbb Z^{>0} \to \Bbb Z^{<0}$ be given by

$\quad f: m \mapsto -(m+1)$

Let $g: \Bbb Z^{<0} \to \Bbb Z^{>0}$ be given by

$\quad g: m \mapsto 1-m$

So we have two injective mappings and we set

$\quad B_1 = \Bbb Z^{<0} \setminus f\bigr(\Bbb Z^{>0}\bigr) = \{-1\}$

Here is the corresponding diagram

and

$\quad A_0 = \{1,3,5,\dots\}$

$\quad B_0 = \{-2,-4,-6,\dots\}$

The bijection $h:\Bbb Z^{>0} \to \Bbb Z^{<0}$ is given by

$$ h(n)=\begin{cases}g^{-1}(n)&n \text{ is even}\\ f(n)&n \text{ is odd} \end{cases} $$

---

Examining the OP's diagram proof found in the book, we start by setting $B_1$ to all the elements of $B$ that $f$ 'misses'. The recursive $g^{-1}$ chain correspondence

$\quad A_{1},A_{2},A_{3},A_{4},$
$\quad B_{1},B_{2},B_{3},B_{4},$

'squeezes out' the problem, so that when you get to the

$\quad f: A_0 \to B_0$

step you know that $f$ is surjective since $B_0 \cap B_1 = \emptyset$.