I'm trying to understand a proof of the Schroeder-Bernstein theorem. I can link the set of lecture notes it originated from, but the document is quite large, so it's probably better if I paraphrase it, adding details I thought were helpful at understanding (so if I'm incorrect, I'd appreciate if someone would point it out). I'll stop at the steps I didn't follow. For anyone interested, the proof is located on page 10 of this document.
Theorem. If $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$.
Proof. Without loss of generality, we can assume $A$ and $B$ are disjoint. If not, replace $A$ with $A \times \{0\}$ and $B$ with $B \times \{1\}$, where $0 = \emptyset$ and $1 = \{\emptyset\}$. Then $|A| = |A \times \{0\}|$ via the bijection $a \mapsto (a,0)$. and $|B| = |B \times \{1\}|$ via the bijection $b \mapsto (b,1)$. Therefore, if we establish that $|A \times \{0\}| = |B \times \{1\}|$, where $A \times \{0\}$ and $B \times \{1\}$ are disjoint, then composing maps gives $|A| = |B|$.
Let $f: A \to B$ and $g: B \to A$ be injections, and define
$$
F = f \cup g: A \cup B \to A \cup B,
$$
which is well-defined since $A$ and $B$ are disjoint. As $f$ and $g$ are injective, so is $F$. Indeed, if $F(x) = F(x')$, then because $A$ and $B$ are disjoint, either $x,x' \in A$ or $x,x' \in B$; indeed, if $x \in A$ and $x' \in B$ (or vice-versa), then $F(x) = g\in B$ and $F(x') \in A$, and $F(x) \neq F(x')$ by disjointness. If $x,x' \in A$, then $F(x) = f(x)$, $F(x') = f(x')$, and we have $f(x) = f(x')$, so $x = x'$ by injectivity of $f$. Similarly, if $x,x' \in B$, then $F(x) = F(x')$, so $g(x) = g(x')$, so $x = x'$ by injectivity of $g$. So $F$ is injective.We say that $F(x)$ is the child of $x$, and $x$ is the parent of $F(x)$. Then every $x \in A \cup B$ has only one parent, and because $F$ is a well-defined function and sends every input to a unique output, every parent has exactly one child. A godfather is defined as a parent that is no one's child.
I think I understand the concept of a "godfather." A godfather is a parent, meaning that it has a unique child $x \in A \cup B$ and is of the form $F(x)$, but is not itself the image of an element of $x \in A \cup B$; if $y = F(x)$ is the godfather, then $y \neq f(t)$ for every $t \in A \cup B$. So a godfather is an element of $A \cup B \setminus f(A \cup B)$, an element of the codomain of $F$ but not its image.
I don't understand the next sentence and it's crucial for defining the bijection, so I'm going to quote it in full.
"For any $x \in A \cup B$, either $x$ is descended from a unique godfather (possibly from $x$ itself), or $x$ has no godfather; it has an infinite line of ancestors (or $x$ is descended from itself.)"
I can't tell whether, in the case where $x$ is descended from itself, which I assume means $F(x) = x$, whether $x$ is a godfather or whether it counts in the section that has no godfather. The proof seems to include it in both. Without the second mention, I think I understand. Let's say $x$ is in the image of $F$. Then I attempt to trace its lineage, first by reversing the arrow $F$ and then retracing $f$ and $g$. If I end up at an element of $A \cup B \setminus f(A \cup B)$, then it falls into the category of descending from a unique godfather. Because $f$ and $g$ are injective and $A$ and $B$ are disjoint, I can only trace back its lineage in a single way, so there's a unique such godfather. If its lineage regressed ad infinitum and doesn't end up in $A \cup B \setminus f(A \cup B)$, then it's in the latter described category. Now suppose that $x$ is not in the image of $F$. It's certainly in the domain of either $f$ or $g$, so I simply start with these arrows and continue to follow them until I either end up at $A \cup B \setminus f(A \cup B)$ or it regressed ad infinitum.
Moving on:
Partition $A$ into three pieces as follows. Let $A_0$ be the elements of $A$ with no godfather, $A_A$ be the elements of $A$ whose godfather is in $A$, and $A_B$ be the elements of $A$ whose godfather is in $B$. Partition $B$ similarly.
The proof then argues there is a bijection between $A_0$ and $B_0$, a bijection between $A_A$ and $B_A$, and a bijection between $A_B$ and $B_B$.
Between $A_0$ and $B_0$:
The map sends $a \in A_0$ to its child $F(a)$. This map is injective since $F$ is injective, and so the restriction of $F$ to $A_0$ is not injective. It argues that the map is surjective because every element of $B_0$ has a parent and this element must live in $A_0$. I'm confused on both of these points. If an element of $A \cup B$ is not in the image of $F$, doesn't it lack a parent? Why must the parent live in $A_0$? This proof I'm not able to fully follow. I also don't see why $F(a) \in B_0$.
The map between $A_A$ and $B_A$ again sends $a \in A_A$ to $F(a)$. I'm again having trouble understanding why the image is in $B_A$ and $B_B$, respectively.
I would greatly appreciate if someone could help me understand the proof. My questions are:
-
On the line regarding $x$ being descended from itself: does that mean $F(x) = x$, and does that correspond to $x$ having no godfather?
-
Understanding the bijections between $A_0$ and $B_0$, $A_A$ and $B_A$, and $A_B$ and $B_B$, why the image of $a$ under these maps is in the respective subset of $B$, and how we can be certain that the maps are surjective.
Best Answer
The "$x$ is descended from itself" case is not the case that $F(x)=x$ (as this would require $x$ to be in both $A$ and $B$, which is impossible), but rather the case of there being an even-length cycle where, e.g., $x\mapsto y\mapsto x'\mapsto y'\mapsto x$. Every element in this cycle has a parent, so $x$ has no godfather.
If $a\in A_0$, then $a$ has no godfather. It certainly the case then that $F(a)\in B$ cannot have a godfather, else $a$ would also have this godfather, so $F(a)\in B_0$. For surjectivity, any $b\in B_0$ must have a parent (else it would be its own godfather), so we can find some $a\in A_0$ (if $a$ had a godfather, it would also be a godfather of $b$) with $F(a)=b$.
(aka 2 continued but MSE numbering is finnicky) If $a\in A_A$, then $a$ has a godfather in $A$. $F(a)\in B$ shares this godfather, so $F(a)\in B_A$ as well. For surjectivity, each $b\in B_A$ must have a parent (else it would be its own godfather, which it cannot be since it's not in $A$), so again we can find $a\in A_A$ with $F(a)=b$. The argument for $A_B$ and $B_B$ is symmetric.