c) A set A is finite if either it is empty or if A ~ {1, 2, 3, ..., n} for some n E N, where here X ~ Y will mean that there is a one to one function from X onto Y, ie that (X| = |Y| . A set is infinite if it is not finite. It can be proved by induction that if a set X is finite and if Y is a proper subset of X, that is if Y C X, then there is no one to one function from X onto Y. We will now show that if X is not finite, this statement is not true. Observation: (*) Given an infinite set X we can extract a sequence of distinct terms recursively from X as follows: Let f : P(X) \\ {0} - X be a choice function. Let x1 = f(X) and if n 2 1, let Cn+1 = f(X\\{x1, x2, ..., Xin}) i) Show that N ~ {2, 3, 4,...} by giving a 1 - 1 and onto function from g : N -> {2, 3, 4, .. .}. [4 marks ii) Using the observation (*) and your solution to 2) above, show that for every infinite set X there is a proper subset A C X (A * X) such that X ~ A. [4 marks] (Hint: We can assume that we have the sequence {In} as above. Now define ? if x = In for some n, f (20) = 3 ? if x 4 {x1, X2, 23, . .. }.)