I have read the proofs of Recursion Theorem at Prove the Recursion Theorem and at Confusion with Recursion Theorem, but I feel that these two proofs are not in detail. So I present my proof and would like to receive your comments!
Many thanks for your help ^^
Recursion Theorem:
Let $A$ be a set, $a\in A$, and $f\colon A\times\Bbb N \to A$ a mapping. Then there exists a unique mapping $g \colon \Bbb N\to A$ such that
1. $g(0)=a$
2. $g(n+1)=f(g(n),n)$
Let $T$ be the set of all finite functions satisfying recursion relation.
$T=\{t:n\to A\mid n\in \Bbb N, t(0)=a, \forall k\in \text{dom}(t)\setminus \{0\}: t(k)=f(t(k-1),k-1)\}$.
Let $g=\bigcup_{t\in T}t$.
Lemma 1: Let $t,u\in T, \text{dom}(t)=n\in \Bbb N, \text{dom}(u)=m\in \Bbb N$, and $n\leqslant m\implies t(k)=u(k)$ for all $k<n$.
This can be done by induction: It is clear that $t(0)=a=u(0)$. Assume $t(k)=u(k)$ for some $k$ such that $k+1<n$. Then $t(k+1)=f(t(k),k)=f(u(k),k)=u(k+1)$. Thus $t(k)=u(k)$ for all $k<n$.
- $g$ is a function.
Assume $(p,a)\in g$ and $(p,b)\in g \implies \exists t,u\in T$ such that $t(p)=a$ and $u(p)=b$. Assume $\text{dom}(t)=n \leqslant \text{dom}(u)=m$. Apply Lemma 1, we get $t(k)=u(k) \text{ for all } k<n\implies a=t(p)=u(p)=b$. Thus $g$ is a function.
- $\text{dom}(g)=\Bbb N$.
This can be done by induction: Clearly, $\{(0,a)\}\in T \implies 0\in \text{dom}(g)$.
Assume $n\in\operatorname{dom}(g)\implies \exists t\in T,n \in \operatorname{dom}(t)$. Let $u:n+2\to A$ such that $u(k)=t(k)$ for all $k \leqslant n$ and $u(n+1)=f(t(n),n)\implies u \in T$. Since $n+1\in \operatorname{dom}(u) \implies n+1\in \operatorname{dom}(g)$. Thus $\operatorname{dom}(g)=\Bbb N$.
- $g$ satisfies conditions 1. and 2.
$t(0)=a$ for all $t\in T\implies g(0)=a$.
Let $t\in T:\text{ dom}(t)=n+2\implies g(k)=t(k)$ for all $k\in \text{dom}(t)\implies g(n+1)=t(n+1)=f(t(k),k)=f(g(k),k)$.
- $g$ is unique.
Let $h:\Bbb N \to A$ is another mapping satisfying the conditions. We show that $h(k)=g(k)$ for all $k\in\Bbb N$. We again prove this by induction. Clealy, $h(0)=g(0)$. Assume $h(n)=g(n)\implies h(n+1)=f(h(n),n)=f(g(n),n)=g(n+1)$. Thus $g$ is unique.
