# Need help with Recursion Theorem (Set Theory)

The recursion theorem

In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set $X$, an element $a$ of $X$ and a function $f\colon X \to X$, the theorem states that there is a unique function

$F:\mathbb{N} \to X$ (where $\mathbb{N}$ denotes the set of natural numbers including zero) such that

$F(0) = a$

$F(n + 1) = f(F(n))$

for any natural number $n$.

Source: "Recursion," Wikipedia

My question: How do you apply this in practice? How, for example, do you apply it to prove the existence of the factorial function?

-

The Recursion Theorem simply expresses the fact that definitions by recursion are mathematically valid, in other words, that we are indeed able correctly and successfully to define functions by recursion. Mathematicians implicitly use this fact whenever they define a function by recursion.

A more general version of the Recursion Theorem would allow the function $f$ to use the argument $n$ as well as $F(n)$. A still more general version of the Recursion Theorem, called course-of-values recursion, allows $f$ to use as an argument the entire restriction of the function $F\mid n$ to earlier values. (These more complex versions of the Recursion theorem can be derived solely from the single-value theorem you have stated, by using a function $f$ that takes a partial function $F\mid n$ (a finite object) and returns $F\mid (n+1)$ the partial function with one additional value in the domain.)

In the case of the factorial function, we define $0!=1$ and $(n+1)!=(n+1)\cdot n!$. This defines factorial recursively, once mulitplication has been defined. The fact that this does indeed define a function is because of the Recursion Theorem.

If one wants to start a bit earlier, then you may consider how the hierarchy of the primitive recursive functions are built up. Starting with the successor function $s(n)=n+1$, one may define addition by recursion: $a+0=a$, $a+(n+1)=s(a+n)$. Then one gets multiplication: $a\cdot 0=0$, $a\cdot(n+1)=(a\cdot n)+a$. Then exponentiation, factorial, etc. all in the usual way.

Set theorists tend to dwell on the recursion theorem in part because of the version of it that applies to transfinite recursion.

-
How does this apply the theorem? Don't you need to prove the existence of the function f as defined in the statement of the theorem? – Dan Christensen Jun 2 '11 at 17:33
I edited to explain. If you allow $F$ to have argument $n$, you can get it straight away, otherwise you should use the function that maps $f\mid n$ to $f\mid (n+1)$. But that is not really natural, and you're better off simply proving a better version of the recursion theorem, where you can also use $n$ as an argument. – JDH Jun 2 '11 at 17:47
don't you want $f$ to have argument $n$? (Not "$F$", as you said.) – Quinn Culver Jun 2 '11 at 17:50
Oh, you are right, I mixed up $f$ and $F$. I have now edited to fix this. – JDH Jun 2 '11 at 17:51

In the form you have stated, you can't get the factorial function without a little bit of extra work. Nonetheless, it can be done.

Let $X = \mathbb{N} \times \mathbb{N}$ be the set of ordered pairs of natural numbers. Set $f(x, y) = (x + 1, (x + 1) y)$. Set $F(0) = (0, 1)$. Then, by the recursion theorem, there is a function $F : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ such that $F(n + 1) = f(F(n))$ for every $n$. A standard induction argument shows that $F(n) = (n, n!)$. Let $p_2 : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ be the projection map $p(x, y) = y$. Then $p_2 \circ F : \mathbb{N} \to \mathbb{N}$ is the factorial function you seek.

-

Follow up: With the aid of my DC Proof program, I as able to formally prove that given a set X and element a in X and a function g: N x X --> X, there exists a function f: N --> X such that

1. f(1)=a

2. For all k in N, f(k+1) = g(k+1, f(k))

where N is set of natural numbers {1, 2, 3... }

Example: For the factorial function, we have X=N, a=1 and g(x,y) = x*y (multiplication on N).

1. Factorial(1)=1

2. For all k in N, Factorial(k+1) = (k+1) * Factorial(k)

I was able to construct f from the sets N and X using only Cartesian product, power set and subset rules.

See HTML version at http://www.dcproof.com/recursive.html (669 lines)

-

It seems F(n+1) = f(F(n)) should have been F(n+1)=fn+1(F(n)). In the case of the factorial function, a = 1 and fn(x) = nx.

This approach does not cover all recursive functions on N. For Fibonacci numbers:

F(0) = F(1) =1

F(n+2) = (n+1) + n =  fn+2(F(n+1)) + fn+1(F(n))

where fn(x) = x for any natural number n.

-
The theorem states that there is a unique $f$. Not a sequence of $f_n$. – Asaf Karagila Jun 3 '11 at 5:08
Asaf, the theorem states that there is a unique $F$, and allowing functions $f_n$ is essentially equivalent to allowing $n$ as an argument to $f$, i.e. $F(n)=f(n,F(n))$, as I mention in my answer. The most general form of the recursion theorem, course-of-values recursion (like strong induction), would have $F\mid (n+1)=f(F\mid n)$, and this would of course cover the Fibonacci case. – JDH Jun 3 '11 at 10:24
Asaf, I am suggesting that the original statement of the theorem is in error. In the case of the factorial function, there is no such unique f: F(0)=1, F(1)=f(F(0))=f(1)=1, F(2)=f(F(1))=f(1)=2. Thus, f(1) would be ill-defined. – Dan Christensen Jun 3 '11 at 14:06
Dan, the theorem is not in error, and it can be used to show that the factorial function and Fibonacci functions exist, by using course-of-values recursion, as I have mentioned. That is, let $f$ be the function that takes a sequence of length $n$ that obeys the factorial function recursion, and returns the sequence of length $n+1$ adding the appropriate next value. Using the stated theorem and this function $f$, one arrives at the factorial function. But truthfully, it will be better simply to use this method to prove the more general recursion theorems that have been mentioned. – JDH Jun 4 '11 at 1:22