Bernstein-Schröder Theorem

[Wendel]

The theorem: Let $X$, $Y$ be sets. If there exist injections $X \to Y$ and $Y \to X$, then $X$ and $Y$ are equivalent sets.

Proof: Let $f : X \rightarrow Y$ and $g : Y \rightarrow X$ be injections. Each point $x \in g(Y)⊆X$ has a unique preimage $y\in Y$ under g; no $x \in X-g(Y)$ has one. Each point $y \in f(X)⊆Y$ has a unique preimage $x \in X$ under $f$; no $y \in Y-f(X)$ has one.
Consider the two composition telescopes:
$$...\to X \to Y \to X \to Y \to X \to Y \to X$$
$$... \to Y \to X \to Y \to X \to Y \to X \to Y$$
Composed of alternating copies of $f$ and $g$.
Peering through these telescopes from $X$ and $Y$, we see that each $x \in X$ and each $y \in Y$ has a unique maximal sequence of preimages under alternating copies of the injections $f$ and $g$, which we call their ancestry:

$$...\to y_{2k+1} \to x_{2k} \to ... \to x_5 \to y_4 \to x_3 \to y_2 \to x_1=x$$
and
$$...\to x_{2k+1} \to y_{2k} \to ... \to y_5 \to x_4 \to y_3 \to x_2 \to y_1=y$$

The ancestry of each $x \in X$ and each $y \in Y$ either has finite even length $2k \geq 2$, finite odd length $2k+1 \geq 1$, or infinite length. These properties give disjoint sets $X_{even}, X_{odd},$ and $X_\infty$ with union $X$, and disjoint sets $Y_{even}, Y_{odd},$ and $Y_\infty$ with union Y.
And the injections restrict to the three injections:
$$f : X_{odd} \to Y_{even}$$
$$g : Y_{odd} \to X_{even}$$
and
$$f : X_\infty \to Y_\infty$$
that are surjective.
So they determine a bijection $X \to Y$.
$$\blacksquare$$

At first I thought this might have meant that for every $x \in g(Y)$ there is either a finite composition of inverse images of $x$ and $y$:
$$g^{-1}(f^{-1}(...g^{-1}(f^{-1}(y))...))=y$$
and
$$f^{-1}(g^{-1}(...f^{-1}(g^{-1}(x))...))=x$$
or there is no such finite composition, in which case $x \in X_\infty$ or $y \in Y_\infty$
but such a sequence of preimages under f and g would always be of even length.
I am assuming by restricting f they mean $f(x)$ such that $x \in X_{even}$ etc., and similarly for g.
Why are they surjective though?
If some element $x_n \in X$ occurs in the sequence of preimages of $x_1$ under alternating copies of f and g, then it does not occur in any other sequence, so if we have another element $x_2 \in X$ (such that $x_2 \ne x_1$, then $x_2$ is not in the first sequence at all.
I'm wondering why these restrictions are surjective.
What do they mean by maximal sequence of preimages/ancestry?
Perhaps it is the smallest sequence for no subsequence of which do we have an element of $X$ or an element of $Y$ being sent to itself?
Also $f$ and $g$ could be any injections, so why should their restrictions to the subsets $X_{even},X_{odd},X_\infty⊆X$ and $Y_{even},Y_{odd},Y_{infty}⊆Y$ be the functions
$$f : X_{odd} \to Y_{even}$$
$$g : Y_{odd} \to X_{even}$$
and
$$f : X_\infty \to Y_\infty$$
?

 

[stevendaryl]

At first I thought this might have meant that for every $x \in g(Y)$ there is either a finite composition of inverse images of $x$ and $y$:
$$g^{-1}(f^{-1}(...g^{-1}(f^{-1}(y))...))=y$$
and
$$f^{-1}(g^{-1}(...f^{-1}(g^{-1}(x))...))=x$$
or there is no such finite composition, in which case $x \in X_\infty$ or $y \in Y_\infty$

If $g^{-1}(f^{-1}(...g^{-1}(f^{-1}(y))...))=y$, then that means that $y \in Y_\infty$. It means that you can keep going in either direction infinitely far (a cycle is a special case of an infinite chain). You only get a finite chain in the case where the last element in the chain (or first element, depending on how you are counting) has no pre-image.

 

[math771]

The proof is using the concept of "ancestry" to show that the injections $f$ and $g$ determine a bijection between $X$ and $Y$. The ancestry of an element is the sequence of its preimages under alternating copies of $f$ and $g$. This sequence can either be of finite even length, finite odd length, or infinite length.

The proof then shows that the elements with finite even length ancestry form a subset $X_{even}$ of $X$, and the elements with finite odd length ancestry form a subset $X_{odd}$ of $X$. Similarly, there are subsets $Y_{even}$ and $Y_{odd}$ of $Y$.

The injections $f$ and $g$ then restrict to functions $f : X_{odd} \to Y_{even}$ and $g : Y_{odd} \to X_{even}$. The proof shows that these restrictions are surjective, which means that every element in $X_{even}$ has a preimage in $Y_{odd}$ and vice versa. This is because every element in $X_{even}$ has a unique preimage in $Y_{odd}$ under $f$, and every element in $Y_{odd}$ has a unique preimage in $X_{even}$ under $g$.

Similarly, there is a surjective restriction $f : X_\infty \to Y_\infty$, which means that every element in $X_\infty$ has a preimage in $Y_\infty$ and vice versa. This is because every element in $X_\infty$ has a unique infinite sequence of preimages under $f$, and every element in $Y_\infty$ has a unique infinite sequence of preimages under $g$.

The restrictions to these subsets are necessary in order for the injections $f$ and $g$ to determine a bijection between $X$ and $Y$. This is because the elements in $X_{even}$ and $Y_{odd}$ do not have preimages in the other subset, and the elements in $X_\infty$ and $Y_\infty$ do not have finite preimages.

In summary, the surjective restrictions to these subsets are necessary in order for the injections $f$ and $g$ to