Lemma
13
[27N](Svolto il 2022-11-03) \(∀ n,h∈ ℕ, f_{S(h)}(n)=S(f_ h(n))\)
Proof
Ricordiamo che \(S(f_ h(n))=f_ h(S(n))\) per definizione ricorsiva; consideriamo
\[ P(n)≐ ∀ h∈ ℕ, f_{S(h)}(n)=S(f_ h(n))\quad ; \]
\(P(0)\) è la proposizione
\[ ∀ h∈ ℕ, f_{S(h)}(0)=S(f_ h(0))=S(h) \]
che è vera perché è il valore iniziale della definizione ricorsiva di \(f_{S(h)}\) e di \(f_ h\); per il passo induttivo assumiamo che \(P(n)\) sia vera e studiamo \(P(S(n))\) al cui interno possiamo dire
\begin{eqnarray*} f_{S(h)}(S(n)) \stackrel{(1)}{=} S(f_{S(h)}(n)) \stackrel{(2)}{=}\\ SS(f_ h(n)) \stackrel{(3)}{=} S(f_{h}(S(n)) \end{eqnarray*}
dove in (1) abbiamo usato la definizione ricorsiva di \(f_ h\) con \(S(h)\) invece di \(h\), in (2) abbiamo usato la ipotesi induttiva, e in (3) la definizione ricorsiva di \(f_ h\); e questo completa il passo induttivo.
(Notate come nel primo passaggio è importante che nella definizione di \(P(n)\) vi sia \(∀ h∈ ℕ,\ldots \)).