Teorema
2
Sia \(A\) un insieme non vuoto; sia \(a∈ A\) fissato, siano date funzioni \(g_ n:A→ A\) per ogni \(n∈ℕ\). Allora esiste ed è unica la funzione \(f:ℕ→ A\) tale che
\(f(0)=a\), e
per ogni \(n∈ℕ\) si ha \(f(S(n))=g_ n(f(n))\).
Si dice che la funzione \(f\) è definita per ricorrenza dalle due precedenti condizioni.
Proof
Più in generale date \(g_ n:A^{n+1}→ A\), si mostra che esiste ed è unica la funzione \(f:ℕ→ A\) tale che \(f(0)=a\) e per ogni \(n∈ℕ\) si ha \(f(S(n))=g_ n(f(0),f(1),\ldots f(n))\).