Equivalent forms of the recursion theorem I have found the next two definitions on the theorem of recursion: 
Definition 1: 
For any set $A$, any $a\in A$ and any function $g:A\times \mathbb{N} \longrightarrow A$, there exists a unique funtion $f: \mathbb{N}\longrightarrow A$ such that 
$1) f(0)=a$
$2) f(n+1)= g(f(n), n)$
Definition 2:
For any set $A$, anty $a\in A$ and any function $g:A\longrightarrow A $, there exists a unique funtion $f: \mathbb{N}\longrightarrow A$ such that
$1) f(0)=a$
$2) f(n+1)=g(f(n))$ 
These are my questions: 
a) My first impression is that the the second definition is not very appropriate for examples in which we wanted to have the function $g$ explicitly. For example in defining the factorial function ($n!$) we can say that $g$ is defined as $g(x,n)=x(n+1)$ in such a way that using definition 1 we get $f(n+1)=g(f(n),n)=f(n)(n+1)$. If we use the second definition I don't know if we can give the function $g$ explicitly (???? I'd like to know).
b) Intuitivelly I see that both formulas are equivalent (They have to, I guess, because they are given as alternative definitions for the recursion theorem). My attempt to prove that $1\longrightarrow 2$ is by defining $g^{*}:A\times \mathbb{N}\longrightarrow A$ such that $g^{*}(x,n)=g(n)$, supossing $g$ is given. Then we have $f(n+1)=g^{*}(x,n)=g(f(n))$. I have not idea to prove $2\longrightarrow 1$ (I probably would do the same, namly define $g^{*}(x)=g(x,n)$, supposing $g$ is given. But I'm not sure because $g(x,n)$ might have different values depending on $n$). 
 A: Given the weaker-looking Definition $2$, here's how to "bootstrap" it up to the stronger-looking Definition $1$.  Let a set $A$, an element $a\in A$, and a function $g:A\times\mathbb N\to A$ be given as in Definition $1$.  Apply Definition $2$ to the set $A'$, element $a'\in A'$, and function $g':A'\to A'$ obtained as follows.  Let $A'=A\times \mathbb N$.  Let $a'=(a,0)$.  And let $g'(a,k)=(g(a,k),k+1)$ for all $(a,k)\in A'$ (i.e., for all $a\in A$ and $k\in\mathbb N$).  Definition $2$ gives us a function $f':\mathbb N\to A'=A\times\mathbb N$ such that $f'(0)=a'=(a,0)$ and $f'(n+1)=g'(f'(n))$.  Since $f'$ maps into the product $A\times\mathbb N$, we can define its two "component" functions, say $f$ and $h$, such that $f'(n)=(f(n),h(n))$, where $f:\mathbb N\to A$ and $h:\mathbb N\to\mathbb N$.  The recursion equations satisied by $f'$, when written in terms of $f$ and $h$, read:
$$
f(0)=a,\quad h(0)=0,\quad f(n+1)=g(f(n),h(n)),\quad\text{and}\quad h(n+1)=h(n)+1.
$$
Notice that the second and fourth of these formulas just say $h(n)=n$, by induction on $n$.  But then the first and third formulas say $f(0)=1$ and $f(n+1)=g(f(n),n)$.  Thus, our $f$, obtained as the first component of $f'$, satisfies the requirements of Definition $1$.  That proves the existence part of Definition $1$; the uniqueness of $f$ is easy by induction on $n$.
