Define ancestors as follows: Consider , if then we call the first ancestor of . If then we call the second ancestor of and so on. Show that this divides into three disjoint subsets: where consists of the elements having an infinite number of ancestors. consist of elements having odd number of ancestor and consists of elements having an even number of ancestors.
So fixing an element of we can find no ancestors, some ancestors, or an infinite number ancestors. If we fix we can do the same. If then and and so on.
And ? How about ?
Now define
To show is a one to one correspondence between and we just check ?