Chapter 2.5, Problem 41E

In this exercise, we prove the Schröder-Bernstein theorem. Suppose that A and B are sets where $\left|A\right|\le \left|B\right|$ and $\left|B\right|\le \left|A\right|$ . This means that there are injections $f:A\to B$ and $g:B\to A$ . To prove the theorem, we must show that there is a bijection $h:A\to B$ , implying that $\left|A\right|=\left|B\right|$ . To build h, we construct the chain of an element $a\in A$ . This chain contains the elements $a,f\left(a\right),g\left(f\left(a\right)\right),f\left(g\left(f\left(a\right)\right)\right),g\left(f\left(g\left(f\left(a\right)\right)\right)\right)$ , .... It also may contain more elements that precede a, extending the chain backwards. So, if there is a $b\in B$ with $g\left(b\right)=a$ , then b will be the term of the chain just before a. Because g may not be a surjection, there may not be any such b, so that a is the first element of the chain. If such a b exists, because g is an injection, it is the unique element of B mapped by g to a; we denote it by $g^{-1}\left(a\right)$ . (Note that this defines g1 as a partial function from B to A.) We extend the chain backwards as long as possible in the same way, adding $f^{-1}\left(g^{-1}\left(a\right)\right),g^{-1}\left(f^{-1}\left(g^{-1}\left(a\right)\right)\right)$ ,… To construct the proof, complete these five parts.

1. Show that every element in A or in B belongs to exactly one chain.

Show that there are four types of chains: chains that form a loop, that is, carrying them forward from every element in the chain will eventually return to this element (type 1), chains that go backwards without stopping (type 2), chains that go backwards and end in the set A (type 3), and chains that go backwards and end in the set B (type 4).

We now define a function $h:A\to B$ . We set $h\left(a\right)=f\left(a\right)$ when a belongs to a chain of type 1, 2, or 3. Show that we can define h(a) when a is in a chain of type 4, by taking $h\left(a\right)=g^{-1}\left(a\right)$ . In parts (d) and (e), we show that this function is a bijection from A to B, proving the theorem.

Show that h is one-to-one. (You can consider chains of types 1, 2, and 3 together, but chains of type 4 separately.)

Show that h is onto. (You need to consider chains of types 1, 2, and 3 together, but chains of type 4 separately.)