Is it possible to prove this version of recursion theorem from the simpler one?

Question

The simpler version:

Let $A$ be a set, $a\in A$, and $f \colon A\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))$

The version I want to prove:

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

I would like to ask whether it is possible to apply the first version to prove the second one.

Many thanks for your help!

Answer 1

We can replace $A$ by $A \times \mathbb{N}$ and $a$ by $(a,0)$. Then we define $$ \hat{f}:\left\{ \begin{array}{rcl} A \times \mathbb{N} &\to &A \times \mathbb{N}, \\ (b,n)&\mapsto&\big(f(b,n),n+1\big). \end{array}\right. $$ By your first version, we obtain a $g : \mathbb{N} \to A \times \mathbb{N}$ (we will write $g(n) = (g_1(n),g_2(n))$) which satisfies $g(0) = (a,0)$ and \begin{align} g(n+1) = \hat{f}(g(n)) = \big(f(g(n)),n+1\big) \end{align} we can split this equation in two equation (one equation for each component) \begin{align} g_1(n+1) &= f(g_1(n),g_2(n)) %\tag{1} \\ g_2(n+1) &= n+1 %\tag{2} %\big(g_1(n+1),g_2(n+1)\big) = \big(f(g_1(n),g_2(n)),n+1\big) \end{align} Hence, we can see that $g_2(n) = n$, which gives us \begin{align} g_1(n+1) &= f(g_1(n),n) \end{align} So $g_1$ is the desired function.

Answer 2

Let $A^*=A\times \Bbb N.$ For $(b,n)\in A^*$ let $f^*(b,n)=(f(b,n),n+1).$

By version 1, for any $a\in A$ there exists a unique $g^*:\Bbb N\to A^*$ such that $g^*(0)=(a,0)$ and $g^*(n+1)=f^*(g^*(n))$ for all $n\in \Bbb N.$

Let $p_1:A^*\to A$ be the projection to the first co-ordinate (i.e. $p_1(b,n)=b$).

Let $g(0)=a$ and let $g(n+1)=p_1(g^*(n+1)).$