Answer to Question #284210 in Discrete Mathematics for wajji

Question

Prove that If A and B are any sets with the property that there is a one-to-one function from A to B and a one-to-one function from B to A, then A and B have the same cardinality.

Answer 1

Proof:

Given theorem is Schroeder-Bernstein Theorem

$\begin{aligned} &\text { We call an element } b \text { of } B \text { lonely if there is no element } a \in A \text { such that } f(a)=b . \text { We say that an element } b_{1} \text { of } B \text { is a descendent of an } \\ &\text { element } b_{0} \text { of } B \text { if there is a natural number } n \text { (possibly zero) such that } b_{1}=(f \circ g)^{n}\left(b_{0}\right) \text {. } \\ &\text { We define the function } h: A \rightarrow B \text { as follows: } \\ &\text { Note that } f(a) \text { cannot be lonely itself. If } f(a) \text { is the descendent of a lonely point, then } f(a)=f \circ g(b) \text { for some } b \text {; since } g \text { is injective, the } \\ &\text { element } g^{-1}(a) \text { is well defined. Thus our function } h \text { is well defined. We claim that it is a bijection from } A \text { to } B \text {. } \\ &\text { We first prove that } h \text { is surjective. Indeed, if } b \in B \text { is the descendent of a lonely point, then } h(g(b))=b ; \text { and if } b \text { is not the descendent of a } \\ &\text { lonely point, then } b \text { is not lonely, so there is some } a \in A \text { such that } f(a)=b ; \text { by our definition, then, } h(a)=b \text {. Thus } h \text { is surjective. } \\ &\text { Next, we prove that } h \text { is injective. We first note that for any } a \in A \text {, the point } h(a) \text { is a descendent of a lonely point if and only if } f(a) \text { is a } \\ &\text { descendent of a lonely point. Now suppose that we have two elements } a_{1}, a_{2} \in A \text { such that } h\left(a_{1}\right)=h\left(a_{2}\right) . \text { We consider two cases. } \\ &\text { If } f\left(a_{1}\right) \text { is the descendent of a lonely point, then so is } f\left(a_{2}\right) \text {. Then } g^{-1}\left(a_{1}\right)=h\left(a_{1}\right)=h\left(a_{2}\right)=g^{-1}\left(a_{2}\right) . \text { Since } g \text { is a well defined function, it } \\ &\text { follows that } a_{1}=a_{2} \text {. } \\ &\text { On the other hand, if } f\left(a_{1}\right) \text { is not a descendent of a lonely point, then neither is } f\left(a_{2}\right) \text {. It follows that } f\left(a_{1}\right)=h\left(a_{1}\right)=h\left(a_{2}\right)=f\left(a_{2}\right) . \text { Since } \\ &f \text { is injective, } a_{1}=a_{2} \text {. } \\ &\text { Thus } h \text { is injective. Since } h \text { is surjective and injective, it is bijective, as desired. } \end{aligned}$