Proving induction from basic recursion lemma Induction Principle: Let $A$ be a set such that $0 \in A$ and $n \in A \implies n + 1 \in A$. Then for all $n \in \mathbb{N}$, $n \in A$.
Basic Recursion Lemma: For all sets $X, W$ and given functions $g : X \to W$, $h : W \times \mathbb{N} \times X \to W$, there exists a unique function $f : \mathbb{N} \times X \to W$ such that
$$f(0, x) = g(x)$$
$$f(n + 1, x) = h(f(n, x), n, x).$$
My book tells me that these two statements are equivalent. I know how to prove the basic recursion lemma from the induction principles, but I cannot figure out how to do the reverse. Everything I have tried ends up requiring me to use induction. Can anyone point me in the right direction?
Thanks.
 A: Assume $0\in A$ and $n\in A\Rightarrow n+1\in A$.
Let $X=\{\bullet\}$, $W=A$. Then we can define $g\colon X\to W$ by $g(\bullet)=0$ because $0\in A$.
And we can define $h\colon W\times \mathbb N\times X\to W$ by 
$$h(x,y,z)=\begin{cases}y+1&\text{if }y+1\in A\\x&\text{otherwise}\end{cases}$$
Then there exists a unique function $f\colon \mathbb N\times X\to W$ such that 
$$f(0,x)=g(x) $$
$$f(n+1,x)=h(f(n,x),n,x)$$
Note that for any element $a\in A$, the function  $f_a\colon \mathbb N\times X\to W$, $f_a(n,x)=\begin{cases}n&\text{if }n\in A\\a&\text{otherwise}\end{cases}$ obeys this recursion:


*

*$f_a(0,\bullet)=0=g(\bullet)$ because $0\in A$.

*If $n+1\in A$ then $f_a(n+1,\bullet)=n+1=h(f_a(n,\bullet),n,\bullet)$

*If $n+1\notin A$ then also $n\notin A$, hence $f(n+1,\bullet)=a =h(a,n,\bullet)=h(f_a(n,\bullet),n,\bullet)$


By uniqueness, any two such functions are equal. As $0\in A$ immediately and $1=0+1\in A$, we have $f_0=f_1$. Because $0\ne 1$, this is only possible if the "otherwise" in the definition of $f_a$  never occurs, that is: for all $n\in \mathbb N$, we also have $n\in A$.
A: Okay, I fixed my answer.  It's similar to Hagen's now, but I think it's a bit simpler.
We may assume without loss of generality that $A$ is an initial segment of $\mathbb{N}$.
Let $h:A \cup \{\infty_0,\infty_1\} \to A \cup \{\infty_0,\infty_1\}$ by given by $h(n) = n+1$ for $n \in A$ and $h(\infty_i) = \infty_i$ for $i<2$.
For $i<2$, define the function $f_i: \mathbb{N} \to A \cup \{\infty_0,\infty_1\}$ by
$$ f_i(n) = 
\begin{cases}
n & \text{if $n \in A$}\\
\infty_i & \text{otherwise}
\end{cases}
$$
These functions both satisfy $f_i(0) = 0$ and $f_i(n+1) = h(f_i(n))$ so by the uniqueness assumption for recursive definitions, they are the same (we do not need the existence assumption.) Assuming $\infty_0 \ne \infty_1$ this means that the second case in the definition cannot occur, so $A$ is all of $\mathbb{N}$.
