EDB — 27N

view in whole PDF view in whole HTML

View

Italian

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 \)).

Download PDF
Managing blob in: Multiple languages
This content is available in: Italian English