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

2 Answers

2 Answers

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

  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

Add your own answers!

Related Questions

Morley rank of group

2  Asked on February 10, 2021 by max-cylin


Total number of combinations.

1  Asked on February 10, 2021 by hanu-goyal


Expected Value : Poker

2  Asked on February 10, 2021 by chase


Rules when calculating with limits

0  Asked on February 9, 2021


Ask a Question

Get help from others!

© 2021 All rights reserved.