Need help understanding the Recursion Theorem (Set Theory) I'm reading through Introduction to Set Theory by Jech and Hrbacek (3rd edition). I am going through the section on recursion theorem, and I am stuck on two things:


*

*I usually see the theorem presented in this way:


Recursion Theorem:  Given a set $X$, an element $a$ of $X$ and a function $f:X\rightarrow X$, then there is a unique function $F:\mathbb{N}\rightarrow X$ such that
1) $F(0)=a$
2)$F(n+1)=f(F(n))$
My first question is, why do we need a second function $f$? If we want our sequence to be factorial, fibonacci, etc, where does this second function $f$ (which to me seems like it kind of came out of nowhere) come into play?


*While the above form of the theorem is used in most books I have looked up, the main one I am using (Introduction to Set Theory, Jech & Hrbacek) uses the following form:
My next question is, why does the function in this case need to be from a product of sets into our original? How come this one uses the $n$ in the argument unlike the one above? Which one is "better"? Thanks in advance for any reponse.
 A: In order to define a function $F$ by recursion, what we need is an initial condition ($F(0)$) together with a rule telling us how to figure out what $F(\alpha)$ should be if we know $F(\beta)$ for every $\beta<\alpha$. (Note the way I've phrased it here allows us to consider defining functions with domain an arbitrary ordinal, not just the natural numbers.)
This is what the "second" function - $f$ in your first version, and $g$ in your second version - is doing. The difference between the two versions is what sort of information we consider when defining subsequent values of $F$. In the first version, $F(n+1)$ is only allowed to depend on $F(n)$; in the second, it's allowed to take into account what $n$ is. 
This latter approach is much broader and more natural. For instance, defining factorial via recursion in the second method is easy: let $g(x, y)=x(y+1)$. In the former, it's much more complicated to come up with the right $f$. In fact, there are some functions which just can't be defined by the first scheme, which can be defined by the second scheme - for instance, let $F(n)$ be the leading digit of $n!$. Since $F$ is neither injective nor eventually periodic, $F$ can't be defined by the first scheme (exercise), but you can define it according to the second.

We can analyze the strength of a recursion scheme as follows. Fix some starting set of functions, and consider what functions we can build from that starting set using different recursion schemes. For a really striking example of this, look at the distinction between primitive recursion and general recursion in computability theory.
