Lemma
13
[27N](Solved on 2022-11-03) \(β n,hβ β, f_{S(h)}(n)=S(f_ h(n))\)
Proof
Recall that \(S(f_ h(n))=f_ h(S(n))\) by recursive definition; Consider
\[ P(n)β β hβ β, f_{S(h)}(n)=S(f_ h(n))\quad ; \]
\(P(0)\) is the clause
\[ β hβ β, f_{S(h)}(0)=S(f_ h(0))=S(h) \]
which is true because it is the initial value of the recursive definition \(f_{S(h)}\) and \(f_ h\). For the inductive step we assume that \(P(n)\) is true and we study \(P(S(n))\), within which we can say
\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*}
where in (1) we used the recursive definition of \(f_ h\) with \(S(h)\) instead \(h\), in (2) we used the inductive hypothesis, and in (3) we used the recursive definition of \(f_ h\). This completes the inductive step.
(Note, in the first step, how important it is that in the definition of \(P(n)\) there is \(β hβ β,\ldots \)).