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

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

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

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

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

  • $\begingroup$ Looks pretty much right to me, except for some "grammatical" weirdness in (2). I think what you mean is "...and $u(n+1) = f(t(n), n)$. Then $u \in T$ and...", right? $\endgroup$ Feb 27, 2018 at 0:55
  • $\begingroup$ Just added the [proof-verification] tag to the question. $\endgroup$ Feb 27, 2018 at 1:10
  • $\begingroup$ @DanielSchepler, you meant the dot (.) next to $u$ is weird ? In my Tex commands, i did not add that dot, but I can not figure out why it still appears there. $\endgroup$
    – Akira
    Feb 27, 2018 at 2:07
  • $\begingroup$ I mean the whole sequence "and $u(n+1) = f(t(n), n) \Longrightarrow u$ . Thus $\in T$ and $\operatorname{dom}(u) = n+2 \Longrightarrow n+1 \in \operatorname{dom}(g)$ $\operatorname{dom}(g) = \mathbb{N}$." reads weird. But if that's an unintended formatting issue, I could take a look at the source and see if I could figure out what's going on. $\endgroup$ Feb 27, 2018 at 2:13
  • $\begingroup$ That part should hopefully read better now. Now my comment on (2) would be: you seem to be mixing up whether you're proving $\forall n \in \mathbb{N}, n \in \operatorname{dom}(g)$ by induction on $n$, or whether you're proving $\forall n \in \mathbb{N}, \exists t \in T, \operatorname{dom}(t) = n + 1$ by induction on $n$. To increase clarity, you should choose one or the other. $\endgroup$ Feb 27, 2018 at 2:22


You must log in to answer this question.

Browse other questions tagged .