Proving induction from basic recursion lemma

Question

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.

Answer 1

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$.

Answer 2

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}$.