# How prove the general recursion theorem

Theorem

Let be $$A$$ a set and let be $$S:=\bigcup_{n\in\Bbb{N}}(A^n)$$ and finally let be $$g:S\rightarrow A$$ a function. So there exist a unique function $$f:\Bbb{N}\rightarrow A$$ such that $$f(n)=g(f|_n)$$ for any $$n\in\Bbb{N}$$.

My text suggest to use the recursion to prove the last theorem: however I can't prove it and so could someone help me, please?

Define $$\varphi:S\to S$$ as follows: if $$\sigma\in A^n$$, then $$\varphi(\sigma)=\sigma\cup\{\langle n,g(\sigma)\rangle\}$$. If you think of $$\sigma$$ as a sequence $$\langle\sigma(0),\sigma(1),\ldots,\sigma(n-1)\rangle$$ of element of $$A$$, $$\varphi$$ simply extends that sequence by one term, so that $$\varphi(\sigma)$$ can be thought of as the sequence $$\langle\sigma(0),\sigma(1),\ldots,\sigma(n-1),g(\sigma)\rangle$$. By the recursion theorem there is a function $$\Phi:\Bbb N\to S$$ such that $$\Phi(0)=\varnothing$$ and $$\Phi(n+1)=\varphi(\Phi(n))$$ for each $$n\in\Bbb N$$.
• Prove by induction that $$\Phi(n)\in A^n$$ for each $$n\in\Bbb N$$.
• Prove that $$\Phi(n+1)\upharpoonright n=\Phi(n)$$ for each $$n\in\Bbb N$$.
Define $$f:\Bbb N\to A:n\mapsto\big(\Phi(n+1)\big)(n)$$.
• Show by induction that $$f\upharpoonright n=\Phi(n)$$ for each $$n\in\Bbb N$$.
• Show that $$f(n)=g(f\upharpoonright n)$$ for each $$n\in\Bbb N$$.