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 :( 
 A: 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$.
