1. Prove that for any countably infinite set S, there is a 1-1 function from N onto S. Hint: Let h be a function from N onto S. Define f using h and recursion. The problem is to show that some form of recursion actually applies (1.3.2).

2. To understand the situation in the equivalence theorem: if, in the notation of 1.4.1, f (x ) = y and g(v) = u, say x is an ancestor of y and v an ancestor of u. Also, say that any ancestor of an ancestor is an ancestor. If h is a 1-1 function from A onto B such that for all x in A, either h(x ) = f (x ) or h(x ) = g-1(x ), show that:

(a) If x has a finite, even number of ancestors, say 2n, then h(x ) = f (x ). Hints: Use induction on n.

(b) If x has a finite, odd number of ancestors, then h(x ) = g-1(x ).

(c) If x has infinitely many ancestors, then how is h(x ) chosen according to the proof of the equivalence theorem (1.4.1)?