嘿，我完全懂你看这段递归定理证明时的懵圈感——这种符号绕来绕去的地方确实容易让人抓不住重点，咱们一步一步把这两个困惑拆解清楚：

第一个困惑：为什么不是验证 $h'(s(s(n))) = g(h'(m))$？ #

首先大概率是你搞混了集合 $A(k)$ 的定义逻辑：

通常递归定理证明里，$A(n)$ 指的是所有定义在 ${0,1,...,n}$ 上的函数 $h$，满足「对所有 $m < n$，$h(s(m)) = g(h(m))$」——简单说就是这个函数从0到n的取值，完全符合递归规则（前n个点的后继值都由g作用在当前点得到）。

当我们要证明 $h' \in A(s(n))$ 时，$A(s(n))$ 要求的是定义在 ${0,1,...,s(n)}$ 上的函数，满足「对所有 $m < s(n)$，$h'(s(m)) = g(h'(m))$」。这里的 $m < s(n)$ 等价于 $m \leq n$，所以要分两种情况验证：

• 对于 $m < n$：因为 $h \in A(n)$，而 $h'$ 是 $h$ 的延拓（$h'(k)=h(k)$ 对所有 $k \leq n$），所以直接继承了 $h$ 的性质，也就是 $h'(s(m))=h(s(m))=g(h(m))=g(h'(m))$，这就是作者写的那部分；
• 对于 $m = n$：这是我们延拓函数时特意定义的——$h'(s(n))=g(h(n))=g(h'(n))$，这部分作者可能默认补充了，或者写在证明的后续环节里。

你误以为要验证 $h'(s(s(n)))$，是把 $A(k)$ 里的「函数定义域上限 $k$」和「递归变量 $m$」搞混了：$s(s(n))$ 是 $s(n)$ 的后继，根本不在 $h'$ 的定义域里（$h'$ 只定义到 $s(n)$），所以完全不需要考虑这个点。

第二个困惑：为什么作者写 $h'(s(m)) = g(h'(m))$？ #

这其实是你可能看错了原文里 $A(n)$ 的初始定义！你提到的「$\forall m< n: h(s(n)) = g(h(m))$」明显有逻辑问题——左边 $h(s(n))$ 和 $m$ 无关，右边 $g(h(m))$ 随 $m$ 变化，不可能对所有 $m < n$ 成立。

正确的 $A(n)$ 定义应该是 $\forall m < n: h(s(m)) = g(h(m))$，也就是对每个小于n的m，函数在m的后继点s(m)处的值，等于g作用在函数在m处的值。这样作者在归纳步骤里写的 $h'(s(m)) = g(h'(m))$，就完全对应了 $A(n)$ 的定义规则，只是把原来的 $h$ 换成了延拓后的 $h'$，变量 $m$ 的范围也对应调整到了 $m < n$（这是归纳假设能覆盖的部分）。

备注：内容来源于stack exchange，提问作者l337n00b