Les exercices de la feuille 4 utilisent le principe de récurrence sur les entiers naturels mis sous forme de règle de déduction comme suit :

    P (0)      ∀n P(n) => P (S(n))
    ------------------------------ nat-rec
            ∀b P(n)
            
Dans ce format, S(n) désigne le successeur de l'entier n, noté habituellement n+1 ; mais l'addition n'est pas encore disponible, l'opération S permet est plus élémentaire que l'addition générale.
Cette notation suppose simplement que les entiers peuvent être construits de deux manières :
- O est un entier naturel
- si n est un entier naturel, S(n) est aussi un entier naturel

Ainsi, l'entier noté habituellement 3 est représenté par S (S (S (0))).

On peut alors définir l'addition (puis d'autres opérations) au moyen des axiomes suivants

                    
     ------------- +0     ------------------------  +S
       ∀n  n+0 = n         ∀n∀m  n + S(m) = S (n+m)

On peut alors prouver les propriétés algébriques bien connues de l'addition en utilisant uniquement le principe de récurrence, les propriétés de l'égalité, et bien entendu les règles de déduction vues auparavant.