Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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$? –  Danikar 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
    
thanks, I got it. –  Danikar Feb 28 '13 at 23:57
add comment

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

share|improve this answer
    
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. –  Danikar 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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.