Question

EXERCISE 6.4. In the proof of the Schröder-Bernstein Theorem, define a function 19-'(x) if TEX GC) = f(x) if TEX (5'(x) if X.. Prove that G:X Y

Answer 1

As per the notations in the proof of the Schroder-Bernstein Theorem, X_e,X_o and X_i are the sets of all those elements of X which have an even or odd or infinite number of ancestors, respectively. Similarly, for Y.

Now, {X_e,X_o,X_i} and {Y_e,Y_o,Y_i} are partitions of X and Y respectively.

I. The restriction f|_{​​​​​​Xe} : X_e$\rightarrow$ Y_o as given x in X_e, f(x) is in Y_o and since x has an even number of predecessors g^-1(x),f^-1(g^-1(x)),g^-1(f^-1(g^-1(x)))........f^-1(g^-1(....g^-1(x)..)), hence f(x) clearly has an odd number of predecessors (namely x = f^-1(f(x)) and all the above in the previous list).

Now, since f is injective, hence the above restriction is injective.

Further , given y in Y_o, then y has an odd number of predecessors and hence, y has at least one predecessor and hence the immediate predecessor f^-1(y). Obviously f^-1(y) has an even number of predecessors and hence f^-1(y) is in X_e. Further, f(f^-1(y)) = y. Thus, f|_Xe is surjective. Thus, f|_Xe : X_e$\rightarrow$ Y_o is a bijection.

II. Consider g^-1 : g(Y) $\rightarrow$ Y. Since, x is in X_i U X_o implies that x has at least one predecessor and hence, an immediate predecessor, then g^-1(x) exists as an element in Y. In other words, x = g(g^-1(x)) is in g(Y). Thus, X_i U X_o is a subset of g(Y).

Consider the restriction g^-1|_Xo : X_o$\rightarrow$ Y. Since each x in X_o has an odd number of predecessors, hence g^-1(x) has an even number of predecessors(namely all the predecessors of x except g^-1(x) itself). Thus, g^-1|_Xo : X_o$\rightarrow$ Y_e. Since g is injective, hence g^-1 is injective. Thus, the restriction g^-1|_Xo is injective. Now, let y be in Y_e. Then, g(y) has an odd number of predecessors(namely y = g^-1(g(y)) and all the evenly many predecessors of y). Thus g(y) is in X_o and further, g^-1(g(y)) = y. Thus, g^-1|_Xo is surjective. Hence, g^-1|_Xo : X_o$\rightarrow$ Y_e is bijective.

Again, consider the restriction g^-1|_Xi : X_i$\rightarrow$ Y. If x is in X_i, then x has infinitely many predecessors g^-1(x),f^-1(g^-1(x), ...... Thus, g^-1(x) has infinitely many predecessors(all predecessors of x except g^-1(x) itself). Thus, g^-1|_Xi : X_i$\rightarrow$ Y_i. Again, since g is injective, so is g^-1|_Xi. Finally, given y in Y_i, since y has infinitely many predecessors, hence g(y) has infinitely many predecessors (namely, y = g^-1(g(y)) and all the predecessors of y). Thus, g^{​​​​​​}(y) is in X_i and g^-1(g(y)) = y. Thus, g^-1|_Xi is surjective. Hence, g^-1|_Xi : X_i$\rightarrow$ Y_i is bijective.

Now, stitching all the bijective maps f|_Xe : X_e $\rightarrow$ Y_o, g^-1|_Xo : X_o$\rightarrow$ Y_e and g^-1|_Xi : X_i$\rightarrow$ Y_i together and using the fact that {X_e,X_i,X_o} and {Y_e,Y_i,Y_o} are partitions of X and Y respectively, we observe that the map

G : X $\rightarrow$ Y given by,

G(x) = { g^-1(x) if x is in X_i

f(x) if x is in X_e

g^-1(x) if x is in X_o

is a bijection.

Here is a picture representing this proof:

*Note that f maps X_e onto Y_o, g^-1 maps X_o onto Y_e and g^-1 maps X_i onto Y_i.

a dud be ?, 72.07. it of 66 Xi x ex Sway hogy