Exercise 8.7

Proof. We show this by induction on $n$. First, for $n=1$, clearly the function $f:\left\{1\right\}\to A$ defined by $f(1)=a_0$ satisfies $\text{(∗)}$. Now suppose that $\text{(∗)}$ holds for some function $f^{\prime }:\left\{1,\dots ,n\right\}\to A$ for $n\in {\mathbb{Z}}_{\text{+}}$. Now define $f:\left\{1,\dots ,n+1\right\}\to A$ by

for any $i\in \left\{1,\dots ,n+1\right\}$. Note that $f$ is not defined in terms of itself but in terms of $f^{\prime }$ and $\rho$.

First, we clearly have $f^{\prime }=f\upharpoonright \left\{1,\dots ,n\right\}$ since $f(i)=f^{\prime }(i)$ for all $i\in \left\{1,\dots ,n\right\}$. Then, clearly $f(1)=f^{\prime }(1)=a_0$ since $1\le n$ and $f^{\prime }$ satisfies $\text{(∗)}$. Consider any $i\in \left\{1,\dots ,n+1\right\}$ where $i>1$. Then we have

if $1<i\le n$ since $f^{\prime }$ satisfies $\text{(∗)}$. Lastly, if $i=n+1$, then

again. This shows that $f$ satisfies $\text{(∗)}$, thereby completing the induction. □

Proof. Suppose that this is not the case and let $i$ be the smallest integer (in the domain of both $f$ and $g$) for which $f(i)\ne g(i)$. Hence $f(j)=g(j)$ for all $1\le j<i$ so that clearly $f\upharpoonright \left\{1,\dots ,i-1\right\}=g\upharpoonright \left\{1,\dots ,i-1\right\}$. Now, it cannot be that $i=1$ since clearly $f(1)=a_0=g(1)$. So then it must be that $1<i$ so that $f(i)=\rho (f\upharpoonright \left\{1,\dots ,i-1\right\})$ and $g(i)=\rho (g\upharpoonright \left\{1,\dots ,i-1\right\})$ since they both satisfy $\text{(∗)}$. Since $f\upharpoonright \left\{1,\dots ,i-1\right\}=g\upharpoonright \left\{1,\dots ,i-1\right\}$, we then clearly have

in contradiction with the definition of $i$. Thus the result must be true as desired. □

Proof. Lemmas 1 and 2 show that there exists a unique function $f_n:\left\{1,\dots ,n\right\}\to A$ satisfying $\text{(∗)}$ for every $n\in {\mathbb{Z}}_{\text{+}}$. We then define $h={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in {\mathbb{Z}}_{\text{+}}}{f}_n$ and claim that this is the unique function from ${\mathbb{Z}}_{\text{+}}$ to $A$ satisfying $\text{(∗)}$.

First we must show that $h$ is a function at all. So consider any $i\in {\mathbb{Z}}_{\text{+}}$ and suppose that $(i,x)$ and $(i,y)$ are in $h$. Then there are $n,m\in {\mathbb{Z}}_{\text{+}}$ where $(i,x)\in f_n$ and $(i,y)\in f_m$ since $h={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in {\mathbb{Z}}_{\text{+}}}{f}_n$, noting that it must be that $i\le n$ and $i\le m$. Since $f_n$ and $f_m$ both satisfy $\text{(∗)}$ and clearly $i$ is in the domain of both, it follows from Lemma 2 that $x=f_n(i)=f_m(i)=y$. This shows that $h$ is a function since $(i,x)$ and $(i,y)$ were arbitrary. Also, clearly the domain of $h$ is ${\mathbb{Z}}_{\text{+}}$ since, for any $i\in {\mathbb{Z}}_{\text{+}}$, $i$ is in the domain of $f_i$ and so in the domain of $h$. Lastly, clearly, the range of $h$ is $A$ since that is the range of all the $f_n$ functions.

Now we show that $h$ satisfies $\text{(∗)}$. First we have that $1$ is clearly in the domain of $h$ and $f_1$ so that it has to be that $h(1)=f_1(1)=a_0$ since $h$ is a function, $f_1\subset h$, and $f_1$ satisfies $\text{(∗)}$. Now suppose that $i>1$. Then clearly $i$ is in the domain of $h$ and $f_i$ so that it has to be that $h(j)=f_i(j)$ for $1\le j\le i$ since $h$ was shown to be a function and $f_i\subset h$. It then follows that $h\upharpoonright \left\{1,\dots ,i-1\right\}=f_i\upharpoonright \left\{1,\dots ,i-1\right\}$. Thus we have

since $f_i$ satisfies $\text{(∗)}$. This completes the proof that $h$ also satisfies $\text{(∗)}$.

Lastly, we show that $h$ is unique, which is very similar to the proof of Lemma 2 . So suppose that $f$ and $g$ are two functions from ${\mathbb{Z}}_{\text{+}}$ to $A$ that both satisfy $\text{(∗)}$. Suppose also that $f\ne g$ so that there is the smallest integer $i$ such that $f(i)\ne g(i)$. Now, it cannot be that $i=1$ since we have $f(1)=a_0=g(1)$ since they both satisfy $\text{(∗)}$. Hence $i>1$ and, since $i$ is the smallest integer where $f(i)\ne g(i)$, it follows that $f(j)=g(j)$ for all $1\le j<i$. Therefore we have that $f\upharpoonright \left\{1,\dots ,i-1\right\}=g\upharpoonright \left\{1,\dots ,i-1\right\}$ so that

since $f$ and $g$ both satisfy $\text{(∗)}$ and $i>1$. This, of course, contradicts the definition of $i$ so it has to be that in fact $f=g$. This shows the uniqueness of $h$ constructed above. □