# Bernstein-Schröder Theorem

• I
• Wendel
So the last element has no pre-image under ##f^{-1}## or the second-to-last element has no pre-image under ##g^{-1}##. If the last element has no pre-image under ##f^{-1}##, then we say that the chain is even. If the second-to-last element has no pre-image under ##g^{-1}##, then we say that the chain is odd.In summary, the theorem states that if there are injections from one set to another and vice versa, then those sets are equivalent. The proof involves using composition telescopes to show that each element in the sets has a unique ancestry under the injections, which can be grouped into even, odd, and infinite chains. These chains

#### 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$$
?

Wendel said:
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.

Last edited:
Wendel

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