Help to prove this inductively defined function is surjective Suppose that $A$ is a infinite subset of $\mathbb{Z}^+$.
We construct a bijection $f:\mathbb{Z}^+ \rightarrow A$ and define $f(n)$ inductively as follows:
Base case: Let $f(1)$ be the least element of the set $A$.
Inductive step: Suppose that $f(k)$ has been defined for some $k\ge 1$ Let $f(k+1)$ be the least element of the set $\{a\in A | a> f(k)\}$.
To see $f$ is a surjection notice that $f(n)\ge n$. Given an element $a\in A$ then let $m$ be the least integer such that $f(m)\ge a$[we must have $m\le a$ since $f(a) \ge a$]. Then, by the definition of $f$ we have $f(m)=a$.
I am unable to follow the argument presented for showing that $f$ is a surjection.
I can see that $f(n)\ge n$, $n\in\mathbb{Z}^+$ and can understand the idea of selecting the smallest $m\in\mathbb{Z}^+$ such that $f(m)\ge a$. But I don't get how we can conclude that $m\ge a$ from knowing that $f(a)\ge a$. Also, from $f(m)\ge a$ how do we conclude that $f(m)=a$ and cannot be $f(m)>a$ (I don't how to use the definition to conclude this).
Please shed some light on these matters.
 A: We know that $f(n) \geq n$ for all $n \in \mathbb Z^+$. Now given any $a \in A$, let:
$$
B = \{b \in A \mid f(b) \geq a\}
$$
Notice that since $f(a) \geq a$, we know that $a \in B$ so that $B \neq \emptyset$. Hence, since $B \subseteq A \subseteq \mathbb Z^+$, it follows by the Well-Ordering Principle that $B$ contains some least element, say $m$. In particular, this means that $\boxed{m \leq a}$ (since $m$ is the least element) and $\boxed{f(m) \geq a}$ (since $m \in B$). Notice that if $m = 1$, then since $f(1) \geq a$ and (by the definition of $f$) $f(1) \leq a$, we have that $f(1) = a$.
Thus, we may assume that $m \geq 2$. With this in mind, consider the set:
$$
C = \{c \in A \mid c > f(m - 1)\}
$$
We claim that $\boxed{a > f(m - 1)}$. 


*

*Otherwise, suppose instead that $a \leq f(m - 1)$. Then it follows that $m - 1 \in B$. But since $m - 1 < m$, this contradicts the minimality of $m$.


Thus, since $a > f(m - 1)$, we know that $a \in C$. But observe that by the definition of $f$, $f(m)$ is the least element of $C$. Thus, it follows that $f(m) \leq a$ so that $f(m) = a$, as desired.
