# Prove the Recursion Theorem

Let $g$ be a function on a subset $A\times\Bbb N$ into $A$, and $a \in A$

Prove there is a unique sequence, $f$ of elements of $A$ such that

a) $f_{0} = a$

b) $f_{n+1} = g(f_{n}, n)$ for all $n \in\Bbb N$ such that $(n+1) \in\operatorname{dom}f$

c) $f$ is either an infinite series or $f$ is a finite sequence of length $k+1$ and $g(f_{k}, k)$ is undefined

I have no idea how to approach this :(

• Uniqueness: Assume the opposite and look for a smallest counterexample... Existence: You might want to prove it by induction on $n$. It's straight forward. May 25, 2013 at 19:14
• @user79202 could you show me how to do the induction proof? Jun 2, 2013 at 15:34
• Brian M. Scott has posted a series of hints how to prove this. Have you tried to fill in the gaps? If so: Where are you stuck? Jun 3, 2013 at 8:18
• @user79202 If I am to use induction, would I start at n=0? and since we know $f_{0}=a$ then say let $n=k$ therefore we get the second condition $f_{k+1}=g(f_{k},k)$ and now show that we can define the function for $n=k+1$ ? With regards to uniqueness, can I simply say if there exists 2 functions, $f$ and $h$ which satisfy the conditions, then they are NOT unique since $f_{0 }= a = h_{0}$ Jun 3, 2013 at 15:50

Uniqueness is very often easier to prove than existence, so I’d start there. Suppose that $f$ and $h$ both satisfy (a)-(c):

• $f_0=h_0=a$;
• $f_{n+1}=g(f_n,n)$ for all $n\in\Bbb N$ such that $n+1\in\operatorname{dom}f$;
• $h_{n+1}=g(h_n,n)$ for all $n\in\Bbb N$ such that $n+1\in\operatorname{dom}h$;
• $f$ is either an infinite sequence or a finite sequence of length $k+1$ such that $g(f_k,k)$ is undefined; and
• $h$ is either an infinite sequence or a finite sequence of length $k+1$ such that $g(h_k,k)$ is undefined.

If $f\ne h$, one of two things must be true: either there is a least $n\in\Bbb N$ such that $f_n$ and $h_n$ are both defined, but $f_n\ne h_n$, or $f$ and $h$ agree wherever both are defined, but one has a larger domain than the other. In the second case we may without loss of generality assume that $f$ is a finite sequence of length $k+1$ such that $g(f_k,k)$ is undefined, that $f_n=h_n$ for $n\le k$, and that $k+1\in\operatorname{dom}h$. In either case it’s not hard to derive a contradiction, thereby showing that in fact $f=h$.

You can prove existence by looking at approximations to $f$. Say that finite sequence $\sigma$ of elements of $A$ of length $k+1$ is a k-approximation to $f$ if $\sigma_0=a$ and $\sigma_{n+1}=g(\sigma_n,n)$ for $n<k$. Clearly $f$ has a $1$-approximation. Now show that either

• there is some $k\in\Bbb N$ such that $f$ has a $k$-approximation $\sigma$ such that $g(\sigma_k,k)$ is undefined,

or

• $f$ has a $k$-approximation for each $k\in\Bbb N$.

Show that in the first case the $k$-approximation $\sigma$ is the desired $f$. Show in the second case that if $k,\ell\in\Bbb N$ with $k\le\ell$, $\sigma$ is a $k$-approximation to $f$, and $\tau$ is an $\ell$-approximation to $f$, then $\sigma=\tau\upharpoonright(k+1)$ (i.e., $\tau_i=\sigma_i$ for all $i\le k$) and that the union of these $k$-approximations over $k\in\Bbb N$ is the desired $f$.

• If I am to use induction to prove existence, would I start at n=0? and since we know $f_{0}=a$ then say let $n=k$ therefore we get the second condition $f_{k+1}=g(f_{k},k)$ and now show that we can define the function for $n=k+1$ ? With regards to uniqueness, can I simply say if there exists 2 functions, $f$ and $h$ which satisfy the conditions, then they are NOT unique since $f_{0 }= a = h_{0}$ Jun 3, 2013 at 15:52