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:

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


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?

  1. 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:enter image description here

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.