Question

Let X ⊆ N be an infinite set of natural numbers. Let f :N → X be defined

  by

f(n+1) = min(X−{f(1),f(2),...,f(n)}) forall n∈N.

f(1) = minX,

(i) Justify the definition of f. (i.e Show that f is well defined.)

(ii) Prove that f is a strictly increasing bijection.

Answer 1

(i) $f:N\rightarrow X$

$f(n+1)=\text{ min }(X-[f(1),f(2),....,f(n)]) \forall n\in N$

$f(1)=\text{ min} (X)$ , As n belongs to the set of natural number So $f(n+1)$ can only be get values for $n\ge 1$ , Thus the given function $f:N\rightarrow X$ is well defined.

(ii) $f(n+1)=\text{ min }(X-[f(1),f(2),...,f(n)] \forall n\in N$

As we get the minimum value of the function at n=0, and function gives the minimum at x=1, So the given function is strictly increasing.

Also for every different values of n we get different values means f is bijective. Hence Given function is strictly incresing bijection.