- #1

- 10

- 0

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

?