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