Different ways for stating the recursion theorem

Question

I've been trying to understand the recursion theorem for quite a while now and I still don't think I understand it 100%, I've checked multiple books and pdfs and I've noticed that this theorem is often stated in two different ways

1. Let $A$ be a set, $a ∈ A$, and $r : N × A → A$ any function. Then there exists a function $f : N → A$ such that (i) $f(0) = a$, and (ii) $f(n + 1) = r(n, f(n))$ for all $n ∈ N$.

2. Let $X$ be a set, $a ∈ X$, and $f : X → X$. Then there exists a function $u : ω → X$ such that $u(0) = a$ and $u(n^ +) = f(u(n))$ for all $n ∈ ω$

Why sometimes $N×A$ is used as domain for the function $r$ in the first case and $f$ in the second case, and sometimes just $X$ is used? What is the difference?

Answer 1

At first glance, it seems that the first variant is more general (to compute the next term, you can use the previous term - but also the current index). More formally, if the first version holds and you are given $X,a,f$ as in the second, then apply the first to $A:=X$, $r(n,a):=f(a)$. Then the $f$ (in the notation of 1) is a valid $u$ (in the notation of 2).

Interestingly, however, we can also infer the first variant from the second: Assume we are given $A,a,r$ as in the first. Let $X=N\times A$ and define $f\colon X\to X$ as $f(\langle n,a\rangle) = \langle n^+,r(n,a)\rangle$. Then the existing $u$, composed with the projection $N\times A\to A$ is a valid solution for the first variant.

Answer 2

Another answer has already explained why both versions are equivalent. However, I want to add that there is a third version that is actually preferable if you want to be able to use the recursion theorem easily.

3. Given any set $X$ and function $R∈F→F$ where $F = \{ g : k∈ω ∧ g∈k→X \}$, there is a function $h∈ω→X$ such that $h(k) = F(h↾k)$ for every $k∈ω$.

This version allows you to define the value of the recursive function $h$ on an input $k$ based on not just $k$ but also all the values of the recursive function on inputs less than $k$, since this information can all be obtained from $h↾k$. (In case you are not familiar with $ω$, treat it as the naturals such that $k = \{ j : j∈ω ∧ j<k \}$ for every $k∈ω$.)

You should be able to see how version (2) can be used to prove version (3), by applying it to $R$ and then taking the union.

~ ~ ~

I also want to point out a significantly stronger version of the recursion theorem:

3. Given any object $c$ and a 2-parameter predicate $Q$ such that $∀x\ ∃!y\ ( Q(x,y) )$, there is a function $h$ with domain $ω$ such that $h(0) = c$ and $Q(h(k),h(k^+))$ for every $k∈ω$.

This version cannot be proven without using the replacement schema in ZFC, because it can be used to construct $V_{ω+ω}$, which is a model of ZFC minus replacement. Replacement also does not immediately furnish a suitable codomain for the desired $h$, since the "$∀x$" in "$∀x\ ∃!y\ ( Q(x,y) )$" is an unbounded quantifier. So to prove (3) we need to do something else. One easy way is to prove $∀k{∈}ω\ ∃!g\ ( \ FD(g,k^+) ∧ g(0)=c ∧ ∀j{∈}k\ ( \ Q(g(j),g(j^+)) \ ) \ )$ where $FD(g,d)$ is a predicate that says "$g$ is a function with domain $d$", which would require using the well-ordering of $ω$, and then use replacement to get $∃F\ ∀k{∈}ω\ ∃!g{∈}F\ ( \ FD(g,k^+) ∧ g(0)=c ∧ ∀j{∈}k\ ( \ Q(g(j),g(j^+)) \ ) \ )$, and finally construct $h = \bigcup \{ \ g : g∈F ∧ k∈ω ∧ FD(g,k^+) ∧ g(0)=c ∧ ∀j{∈}k\ ( \ Q(g(j),g(j^+)) \ ) \ \}$ and prove that $h$ is a function witnessing the claim.