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

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

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


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

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