## Cantor Schroeder

Define ancestors as follows: Consider $\displaystyle a \in A$, if $\displaystyle g(B)$ then we call $\displaystyle g^{-1}(a)$ the first ancestor of $\displaystyle a$. If $\displaystyle g^{-1}(a) \in f(A)$ then we call $\displaystyle f^{-1}(g^{-1}(a))$ the second ancestor of $\displaystyle a$ and so on. Show that this divides $\displaystyle A$ into three disjoint subsets: $\displaystyle A_{\infty}, A_{e}, A_o$ where $\displaystyle A_{\infty}$ consists of the elements having an infinite number of ancestors. $\displaystyle A_o$ consist of elements having odd number of ancestor and $\displaystyle A_e$ consists of elements having an even number of ancestors.

So fixing an element of $\displaystyle a \in A$ we can find no ancestors, some ancestors, or an infinite number ancestors. If we fix $\displaystyle b \in B$ we can do the same. If $\displaystyle a \in A_{\infty}$ then $\displaystyle a \notin A_e$ and $\displaystyle a \notin A_o$ and so on.

And $\displaystyle f(A_{\infty}) = B$? How about $\displaystyle f(A_e)$?

Now define $\displaystyle F(a) = \begin{cases} f(a) \ \ \ \ a \in A_{\infty} \cup A_{e} \\ g^{-1}(a) \ \ \ \ a \in A_o \end{cases}$

To show $\displaystyle F$ is a one to one correspondence between $\displaystyle A$ and $\displaystyle B$ we just check $\displaystyle F(a) = F(a') \implies a = a'$?