Exercise 9.3

Proof. First, let $a_0=f_1(1)\in A$. Now consider any function $g:S_n\to A$. If $g=\varnothing$ then set $\rho (\varnothing )=\rho (g)=a_0$. Otherwise let $I_g=\left\{i\in S_{n+1}\mid f_n(i)\notin g(S_n)\right\}$. Suppose for the moment that $I_g=\varnothing$. Consider any $x\in f_n(S_{n+1})$ so that there is a $k\in S_{n+1}$ where $f_n(k)=x$. Then it has to be that $x=f_n(k)\in g(S_n)$ since otherwise we would have $k\in I_g$. Since $x$ was arbitrary, this shows that $f_n(S_{n+1})\subset g(S_n)$. Thus the identity function $h_1:f_n(S_{n+1})\to g(S_n)$ is an injection. Clearly, $g$ is a surjection from $S_n$ to its image $g(S_n)$ so that there is we can construct a particular injection $h_2:g(S_n)\to S_n$ by Corollary 6.7. Lastly, $f_n$ is an injection from $S_{n+1}$ to $f_n(S_{n+1})$. Therefore $h=h_2\circ h_1\circ f_n$ is an injection from $S_{n+1}$ to $S_n$. Hence $h$ is a bijection from $S_{n+1}$ to $h(S_{n+1})$, which is clearly a subset of $S_n$ since $S_n$ is the range of $h$. But, since $S_n⊊S_{n+1}$, clearly $h(S_{n+1})⊊S_{n+1}$ as well so that $h$ is a bijection from $S_{n+1}$ onto a proper subset of itself. As $S_{n+1}$ is clearly finite, this violates Corollary 6.3 so we have a contradiction.

So it must be that $I_g\ne \varnothing$ so that it is a non-empty set of positive integers, and hence has a smallest element $i$. So simply set $\rho (g)=f_n(i)$. Now, it then follows from the principle of recursive definition that there is a unique $f:{\mathbb{Z}}_{\text{+}}\to A$ such that

We claim that this $f$ is injective.

To see this we first show that $f(n)\notin f(S_n)$ for all $n\in {\mathbb{Z}}_{\text{+}}$. If $n=1$ we have that $f(n)=f(1)=a_0=f_1(1)$ and $f(S_n)=f(\varnothing )=\varnothing$ so that clearly the result holds. If $n>1$ then $f(n)=\rho (f\upharpoonright S_n)=f_n(i)$ for some $i\in I_{f\upharpoonright S_n}$ since clearly $S_n\ne \varnothing$ so that $f\upharpoonright S_n\ne \varnothing$. Since $i\in I_{f\upharpoonright S_n}$ we have that $f(n)=f_n(i)\notin (f\upharpoonright S_n)(S_n)=f(S_n)$ as desired. This shows that $f$ is injective. For consider any $n,m\in {\mathbb{Z}}_{\text{+}}$ where $n\ne m$. Without loss of generality, we can assume that $n<m$. Then clearly $f(n)\in f(S_m)$ since $n\in S_m$ since $n<m$. However, by what was just shown, we have $f(m)\notin f(S_m)$ so that it has to be that $f(n)\ne f(m)$. This shows $f$ to be injective since $n$ and $m$ were arbitrary.

Lastly, since $f:{\mathbb{Z}}_{\text{+}}\to A$ is injective, it follows that $f$ is a bijection from ${\mathbb{Z}}_{\text{+}}$ to $f({\mathbb{Z}}_{\text{+}})\subset A$. Hence $f({\mathbb{Z}}_{\text{+}})$ is infinite since ${\mathbb{Z}}_{\text{+}}$ is, and since it is a subset of $A$, it has to be that $A$ is infinite as well. □