Confusion with Recursion Theorem

Question

I am confused with certain aspects of the proof given in Hrbacek and Jech. The following link gives a similar proof to that in the book: Prove the Recursion Theorem

1) Firstly, why do we need to show the existence of a function from $f:N\rightarrow A$. Can't we just define a function from $N$ to $A$ s.t $$f(0)=a$$ $$f(n+1)=g(f(n),n) $$

2) Secondly in the proof of the existence of f, approximations of f are defined (In the book they are called $m$-step computations). However, these approximations seem to be defined recursively as well but isn't that what we are trying to proof?

"Say that the finite sequence $\sigma$ of elements of A of length $k+1$ is a $k$-approximation... "

P.s. I have no trouble understanding the actual proof but just the 2 issues above.

Answer 1

In (1) you have given a set of properties of $f$ but not actually shown that a function with these properties exists. In your head you are probably saying something like "the function is defined for zero, and for each $n$, if the function is defined for $n,$ then it is defined for $n+1$." But when you start a sentence with 'the function', you are presupposing its existence. If it helps, remember that we must show the function is a set whose existence follows from the axioms , i.e. we establish its existence using pairing, unions, etc.

So for each $k\in \mathbb N$, we the replace the vague "$f$ is defined at $k$" with the rigorous "$f_k$ exists." You can show by induction on $k$ that for each $k,$ there is a unique function $f_k$ with domain $\{0,\ldots k\}$ that satisfies your properties up to $f(k) = g(f(k-1),k-1).$ The proof of the induction step that if an $f_k$ with the properties exists, then an $f_{k+1}$ does is just adding the ordered pair $\langle k+1,g(f(k),k)\rangle$ to $f_k$. Then as you've showed all the $f_k$ exist, you can define $f = \{\langle(k,f_k(k)\rangle\mid k\in \mathbb N\}.$