4

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.

zrbecker
  • 4,048

2 Answers2

3

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

Hagen von Eitzen
  • 374,180
  • I see how $f_a$ satisfies $f(0, x) = g(x)$. But if we have $n + 1 \not \in A$, then $n \not \in A$. Therefore $f_a(n, x) = a$ and $f_a(n + 1, x) = a$. So $f_a(n + 1, x) \neq f_a(n, x) + 1 = h(f(n, x), n, x)$. Right? Is there another way to say $f_a$ obeys the recursion without assuming all of $n$ is already in $A$? – zrbecker Feb 28 '13 at 23:40
  • @Danikar Sorry, it was necessary to adjust $h$ a bit. I hope now you see how it works. – Hagen von Eitzen Feb 28 '13 at 23:48
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}$.

Trevor Wilson
  • 16,989
  • If I could show that $f(n) = n$, I would be done. But don't I need induction to show this? $f(n) - n \neq 0 \implies f(n - 1) - (n - 1) \neq 0$ is the only kind of thing I could come up with. – zrbecker Feb 28 '13 at 23:29
  • @Danikar Good point. I was thinking that $f = \text{id}$ followed from uniqueness, but one would really need uniqueness of $f \restriction n$ for all $n$. – Trevor Wilson Feb 28 '13 at 23:34