# Different ways for stating the recursion theorem

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?

Mathematics Asked on November 12, 2021

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.

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

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

Answered by user21820 on November 12, 2021

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=Ntimes A$$ and define $$fcolon Xto X$$ as $$f(langle n,arangle) = langle n^+,r(n,a)rangle$$. Then the existing $$u$$, composed with the projection $$Ntimes Ato A$$ is a valid solution for the first variant.

Answered by Hagen von Eitzen on November 12, 2021

## Related Questions

### Mathematical Writing: Can objects in a definition be assigned any name, even though this name is used elsewhere in the text?

1  Asked on February 11, 2021 by clapham

### $T:P_nlongrightarrow P_n : Tp(t)=frac{d}{dt}p(t)text{ Find the norm of the operator}$

1  Asked on February 11, 2021

### Method to solve an equation

1  Asked on February 10, 2021 by khosrotash

### Prove that $sum_{n=1}^infty frac{x^{2n}}{(n+x)^2}$ converges uniformly on $S=[0,1]$

0  Asked on February 10, 2021 by naturalmathlover

### Find moment generating function for $sqrt{n}(overline{X}-1)$

0  Asked on February 10, 2021 by diego-andres-gomez-polo

### Morley rank of group

2  Asked on February 10, 2021 by max-cylin

### If $H$ is any subgroup of $G$ and $N = bigcap_{ain G}a^{-1}Ha$, prove that $N triangleleft G$.

3  Asked on February 10, 2021

### Total number of combinations.

1  Asked on February 10, 2021 by hanu-goyal

### how is a first variation of a functional calculated?

1  Asked on February 10, 2021 by hosein-javanmardi

### All Covering spaces of the Annulus

1  Asked on February 10, 2021 by udalricus-s

### Discrete Structures question. Don’t know how to start really rusty, please explain like I’m five.

0  Asked on February 10, 2021 by i-want-to-become-a-shepherd

### Expected Value : Poker

2  Asked on February 10, 2021 by chase

### Rules when calculating with limits

0  Asked on February 9, 2021

### Prove this geometric inequality

2  Asked on February 9, 2021 by lupin

### Prove that $19| 2^{2^{6k+2}}+3$ for k = 0,1,2,3….

5  Asked on February 9, 2021 by shlok-jain

### Help with a prime number spiral which turns 90 degrees at each prime

13  Asked on February 9, 2021

### How to seat $n$ people in $n$ seats if each person must take a seat next to an already sitting person?

3  Asked on February 9, 2021

### Big Omega and Big Omega Infinity Differences

1  Asked on February 9, 2021 by tymind

### Evaluating real integral using complex analysis.

3  Asked on February 9, 2021 by doctork_

### I am having difficulty understanding this differentiation question

1  Asked on February 9, 2021