如何证明行为类似pred的函数M是原始递归函数？

嘿，这个问题其实挺直观的，你的函数M本质上就是我们常说的前驱函数（pred）——当输入是0时返回0，输入正整数x时返回x-1。要证明它是原始递归函数，我们只需要对照原始递归函数的定义一步步构造就行啦！

首先先明确原始递归函数的核心规则：

• 有三个基本原始递归函数：零函数$Z(x)=0$，后继函数$S(x)=x+1$，投影函数$P_i^n(x_1,...,x_n)=x_i$（返回第i个输入参数）。
• 可以通过两种操作生成新的原始递归函数：复合（嵌套调用已有原始递归函数）和原始递归（用初始值加递归步骤定义）。

接下来我们用最直接的原始递归操作来构造M：

1. 初始条件：$M(0)=0$，这正好是零函数$Z$的输出，而零函数是基本原始递归函数，完全符合要求。
2. 递归步骤：对于任意$x \ge 0$，$M(x+1)=x$。这里我们可以把右边的$x$看作二元投影函数$P_1^2(x, M(x))$——这个投影函数的作用是忽略第二个参数，直接返回第一个参数$x$，而投影函数本身也是基本原始递归函数。

把这两部分结合起来，完全符合原始递归函数的标准定义格式：
$$
\begin{cases}
M(0) = 0 \
M(S(x)) = P_1^2(x, M(x))
\end{cases}
$$
（这里用$S(x)$表示$x$的后继，也就是$x+1$，是原始递归体系里的标准符号）

另外还有一种更直观的思路：如果你已经知道截断减法（记为$x \dot{-} y$，当$x \ge y$时返回$x-y$，否则返回0）是原始递归函数，那$M(x)$其实就是$x \dot{-} 1$——因为当$x=0$时，$0 \dot{-}1=0$；当$x>0$时，$x \dot{-}1=x-1$，正好和M的行为一致。不过这种方法需要依赖截断减法的原始递归性，而第一种直接构造的方法更基础，不需要额外前提。

总结一下：因为M可以通过基本原始递归函数（零函数、投影函数）加上原始递归操作生成，所以它是原始递归函数。

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