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