Understanding Halmos’ proof of Schroeder Bernstein I'm trying to understand Halmos’ proof of the Schroeder-Bernstein theorem. I'm going to replicate as much of the argument as I can, pausing at steps I can't completely follow.

If $|X| \leq |Y|$ and $|Y| \leq |X|$, then $|X| = |Y|$.


Proof. Without loss of generality, suppose $X \cap Y = \emptyset$. If not, we can replace $X$ and $Y$ with isomorphic copies $X'$ and $Y'$ such that $X' \cap Y' = \emptyset$ and, upon establishing a bijection $X' \to Y'$, we have a bijection $X \to Y$. Let $f: X \to Y$ and $g: Y \to X$ be injections. If one is also surjective, then, taking an inverse if necessary, there exists a bijection $X \to Y$, so we assume neither are surjective.

I am not sure if I need to rule out surjectivity, though when it comes to apply the inverse function to elements not in the image of either $f$ or $g$, I want to be sure that these sets are nonempty to prevent any issues with well-definedness. If this isn't necessary, please let me know.

Given $x \in X$, we say $x$ is the parent of $f(x) \in Y$, and given $y \in Y$, we say $y$ is the parent of $g(y) \in X$. We can then define the descendents of $x$ and $y$ by successively applying $f$ and $g$, namely, the descendants of $x$ are
$$f(x), g(f(x)), f(g(f(x)), \ldots$$
and the descendants of $y$ are
$$g(y), f(g(y)), g(f(g(y)), \ldots$$
where the elements alternate between membership in $X$ and membership in $Y$. Each term in the sequence of descendants is, by definition, an ancestor of all terms that follow.


We partition $X$ and $Y$ as follows. Given any element in either $x$ or $y$ and upon tracing back its lineage by successively applying $f$ and $g$, we have three mutually exclusive and exhaustive possibilities. First, an element may have no parent in $Y$, i.e., it lives in $X - g(Y)$. Second, it may have no parent in $X$, i.e., it lives in $Y - f(X)$. Third, its lineage regresses ad infinitum, and we can always find a parent no matter how far we go.

I don't think I fully understand this process since we're partitioning $X$ and $Y$ simultaneously. Where exactly are we starting? Do I have to start at $x$ to end up in $X - g(Y)$ or at $Y$ to end up in $Y - f(X)$?

Define $X_X$ to be the set of elements of $X - g(Y)$ and their descendants in $X$. That is, $x_X$ consists of all $x \in X - g(Y)$ and $f(x), f(g(f(x))$, ad infinitum.

Am I incorrect that I can keep applying $f$ and $g$ since these elements "died in $X$," in some sense? I don't fully grasp why I have to a tack on the descendants, especially since I'm looking for elements of $X$, so I assume I need to omit all descendants starting with an application of $g$.

Define $X_Y$ to be the set of elements of descendants in $X$ of elements in $Y - f(X)$. That is, elements $g(y), g(f(g(y))$, ad infinitum.

I defined this similarly to the above, and have the same confusion.

Then define $X_{\infty}$ to be the set of all elements in $X$ that lack any parentless ancestor, i.e., all remaining $x$. Define $Y_X$, $Y_Y$, and $Y_{\infty}$ similarly to partition $Y$.

I don't think I fully understand the partition of $Y$. What exactly is the correspondence between $X_X$ and $Y_X$, $X_Y$ and $Y_Y$, and $X_{\infty}$ and $Y_{\infty}$?
The argument from here becomes that we can biject $X_X$ with $Y_X$, $X_Y$ with $Y_Y$, and $X_{\infty}$ with $Y_{\infty}$, giving a bijection $X$ to $Y$.
Any help with understanding this argument would be appreciated.
 A: Surjectivity
At first, we have to exclude maps from being surjective. Suppose $f: X \to Y$ be surjective also. Then let us define a map $f':Y \to X$ such that $f'(y) = f^{-1}(y)$. Due to surjectivity of $f$, $f^{-1}(y) \ne \phi$ and due to injectivity of $f$, $|f^{-1}(y)| = 1$. Hence the map $f'$ is well defined. Thus, $f' \circ f = $id$_X$ and $f \circ f' = $id$_Y$. Therefore, $X$ and $Y$ are equivalent and $|X| = |Y|$.
Therefore, we have to exclude surjectivity to get more non trivial cases.
Lineage sytem
To understand it let us think it as two hypothetical cities $X$ and $Y$. Now set a rule if child lives in $X$ then its parent (if exist) must live in $Y$ and vice versa. In short, child and parent cannot live in same city. Also, every person has only one child and atmost one parent.
Now, $f$ and $g$ both mark the child of the person. Now, $X - g(Y)$ is the collection of people having no parent and living in X; they are the 1st of their family live in X. Similarly, $Y - f(X)$ is the collection of people having no parent and living in Y; that is they are the 1st people of city Y.
Now, coming to your question: we are starting from nowhere; it's just a system.
Final part
To understand this part, let us assume there are 2 kind of people: (1) normal people and (2) gods. So, what's the difference? A normal person have someome from whom the family started but for god, there is none; that is, every god has a parent. So, according to our new schematics.
$X_X$ is the collection of normal people whose family tree started in X and also lives in X.
$X_Y$ is the collection of normal people whose family tree started in Y but lives in X.
$X_\infty$ is the collection of gods living in X.
Similarly, we partition $Y$.
Connections
Let $a \in X_X$. So, $a$ is a normal person living in $X$ and having first ancestor in X. $f(a)$ is the child of $a$ living in $Y$ but having first ancestor in $X$. So, $f(a) \in Y_X$. So, $f(X_X) = Y_X$. Therefore, using our argument of Surjecitivity section, $|X_X| = |Y_X|$. By same argument, $|Y_Y| = |X_Y|$ [Here, the trick is we have to use $g$].
For gods, $f(X_\infty) \subseteq Y_\infty$; but a god always has a parent, so $Y_\infty \subseteq f(X_\infty)$. Hence, again we have $f(X_\infty) = Y_\infty$.
