MATHESIS :: Essential
< All Topics

The recursion theorem

Posted
Updated
ByM4t_6_onL

From Peano’s axioms, we prove the following theorem, which serves as the basis for all definitions by induction, in particular the definitions of the addition and the multiplication of natural numbers.

Theorem 1 (Recursion theorem)
If f:E\to E is an application from a set E into itself and a\in E, then there exists a unique application g:\mathbb N\to E such that g(0)=a and g(s(n))=f(g(n)) for all n\in\mathbb N.

Demonstration
The demonstration is done in two steps.

i) We show by induction that for all n\in \mathbb N, there exists a unique application h:[[0,n]]\to E such that h(0)=a and for all i<n, h(s(i))=f(h(i)).

For n=0, the only function h:[[0,0]]=\{0\}\to E such that h(0)=a (the second condition is “empty”) is defined by this condition, so the property is verified at rank n=0.

Let us suppose that it is verified at rank n: there exists a unique function h:[[0,n]]\to E such that h(0)=a and h(s(i))=f(h(i)) for all i<n. Let us define a function g:[[0,n+1]]\to E by putting g(i)=h(i) for all i<n+1 and g(n+1)=f(h(n)). We have g(0)=h(0)=a, and for all i<n, g(s(i))=h(s(i))=f(h(i)) by induction hypothesis; since g(s(n))=f(g(n)) by definition, g:[[0,n+1]]\to E has the desired property.

Suppose that k:[[0,n+1]]\to E is another function with these properties: in particular, we have k(0)=a and for any i<n, k(s(i))=f(k(i)) and by induction hypothesis, h being unique with these properties the restriction k|_{[[0,n]]} of k to [[0,n]] is equal to h. It also follows that k(n+1)=k(s(n))=f(k(n))=f(h(n))=f(g(n))=g(s(n))=g(n+1), so finally k=g and uniqueness is also proved at rank n+1. We conclude by induction that the property is verified for all n\in\mathbb N.

ii) We deduce that there exists a unique application g:\mathbb N\to E such that g(0)=a and for all n\in\mathbb N, g(s(n))=f(g(n)).

For this, let n\in\mathbb N : by (i) there exists a unique function h_n:[[0,n]]\to E with the given properties, and we then define g(n) as h_n(n). We thus obtain a function g:\mathbb N\to E. By definition, we have g(0)=h_0(0)=a, and for any n\in\mathbb N, we have g(s(n))=h{s(n)}(s(n))=f(h_{s(n)}(n))=f(h_n(n)) (because by uniqueness in (i), we have h_{s(n)}|_{[[0,n]]}=h_n) =f(g(n)), so g has the desired properties.

As for uniqueness, if k:\mathbb N\to E is an application such that k(0)=a and k(s(n))=f(k(n)) for all n\in\mathbb N, we easily prove by induction that \{n\in\mathbb N : g(n)=k(n)\} is the whole set \mathbb N, and thus that k=g, and the theorem is proved. \square

In practice, the definition by induction proceeds by a “construction” of the graph R of the sequence g, that is to say a functional relation R on \mathbb N\times E, for which for any n\in\mathbb N, there exists x\in E with (n,x)\in R.

In principle, one defines g(0) (one chooses an element a of E starting from an essential property, and one describes a process (the function f) which makes it possible to define g(n+1) from g(n), in the form of an expression which translates the constraints of definition of the function g.

By Theorem 1, the unique function g having the desired properties is the sequence defined by induction.

Example 1

Let us define by induction the expression a^n, for a a real number and n a natural number: we let a^0:=1 and a^{n+1}=a^n\times a. Here we define a mapping g:\mathbb N\to \mathbb R, which associates to the natural number n the real number a^n. The application f:\mathbb R\to \mathbb R which is appropriate is the “multiplication by a“, which associates to x\in\mathbb R the real number a.x. By putting g(0)=1 (the value of a^0), Theorem 1 assures us that there exists a single function g:\mathbb N\to \mathbb R such that g(0)=a and g(n+1)=a.g(n) for all n\in\mathbb N: this is the function we are seeking. \square

Table of Contents