Krdytkyu

This question regards Fundamentals of Mathematics, Volume 1: Foundations of Mathematics: The Real Number System and Algebra Edited by H. Behnke, F. Bachmann, K. Fladt, W. Süss and H. Kunle.

First Peano's Axioms starting with $1,$ rather than $0,$ are used to define the universe of numbers. Addition is developed as a set of functions, one for each number such that

$$fleft[1right]=a^prime text{ and } fleft[x^primeright]=fleft[xright]^prime text{ for all } xinmathbb{N}.tag{1}$$

Then we are told:

The fact that for every number $a$ there exists exactly one function $f$ with the properties (1) is a special case of the following general theorem:

Let $c$ be a number and let $F$ be a function of two arguments defined in $mathbb{N}$ and with values in $mathbb{N}.$ Then there exists exactly one function $f$ defined in $mathbb{N}$ such that

$$fleft[1right]=c text{ and } fleft[x^primeright]=Fleft[x,fleft[xright]right] text{ for all } xinmathbb{N}.tag{2}$$

It is clear that (1) is obtained from (2) by setting $c=a^prime$ and $F[x,y]=y^prime.$ The definition of a function $f$ by the conditions (2), which is possible in view of the general theorem is called a recursive definition, since the determination of $fleft[x^primeright]$ is reduced to that of $fleft[xright]$ and thereby finally to that of $fleft[1right].$

The name given by the authors to the above quoted theorem is the principle of recursion; which they promise to make more general in the sequel.

It appears to me that the authors have made a diligent effort to obscure the fact that, for the natural numbers, their principle of recursion is equivalent to a definition of addition. That is, the function $f$ associated with each number $a$ is simply the operation of adding $a$ to the argument of $f$. For clarity lets write $f_a$ for the $f$ associated with the number $a$. Then, when the universe of numbers is $mathbb{N}$ the only $f_a$ we will obtain by applying the principle of recursion is $f_{a}left[xright]=a+x.$

Is my understanding correct regarding the applicability of the above stated principle of recursion to the natural numbers?

As the fictional Winston Smith wrote in his diary in Orwell's 1984

Freedom is the freedom to say that two plus two makes four. If that is granted, all else follows.

No, you're missing the role of the other function $F$. Recursion - at least in the less-general form presented here - takes in two inputs, a "starting value" $c$ (I think this is what you call $a$?) and also a "next-step-getting" function $F$, and spits out the desired $f$.

To get a sense for the role $F$ plays, let's look at a couple examples (with $c=1$ always):

• 
  

  $F(x,y)=x$. We have:

  
  
  
  
  

  • $f(1)=c=1$,

  
  

  • $f(2)=F(1,f(1))=1$,

  
  

  • $f(3)=F(2,f(1))=2$,

  
  

  • $f(4)=F(3,f(2))=3$, ...

  
  

  • It's easy to see that the $f$ we produce is just $f(x)=max{x-1,1}$.

  
  
  
  


• 
  

  $F(x,y)=x+y$. We have:

  
  
  
  
  

  • $f(1)=c=1$,

  
  

  • $f(2)=F(1,f(1))=1+1=2$,

  
  

  • $f(3)=F(2,f(2))=2+2=4$,

  
  

  • $f(4)=F(3,f(3))=3+4=7$,

  
  

  • Can you figure out what the $f$ we're producing now is?

  
  
  
  

It's also instructive to go the other direction. The function $f(x)=2^x$ can be defined recursively as $f(1)=2, f(x+1)=2cdot f(x)$.

Exercise: check that setting $c=2, F(x,y)=2y$ in the above recursive construction produces $2^x$.