自然数集ℕ₀上满足特定递归条件的运算θ的存在性证明思路合理性问询

嘿，大家好！咱们今天聚焦的是**非负自然数集合$\mathbb{N}_0$**上的一个递归运算存在性问题，先来梳理下背景和原定理：

我们的研究定义域是全体非负自然数$\mathbb{N}_0$。下面这个定理出自H.A. Thurston的《The Number System》一书：

定理3：存在唯一的运算$\theta$，使得对任意$x,y \in \mathbb{N}_0$，满足以下两个递归条件：
$$
\begin{align*}
(i)\quad \theta(x, 0) &= x \
(ii)\quad \theta(x, y') &= \theta(x, y)'
\end{align*}
$$
（注：这里的$y'$指的是自然数$y$的后继数，也就是$y+1$的递归定义形式）

Thurston给出的原证明 #

原证明分为唯一性和存在性两个核心部分，逻辑非常严谨：

1. 唯一性证明

假设存在另一个满足条件的运算$\phi$，它同样满足：
$$
\begin{align*}
(iii)\quad \phi(x, 0) &= x \quad \text{对所有}x \
(iv)\quad \phi(x, y') &= \phi(x, y)' \quad \text{对所有}x,y
\end{align*}
$$

我们定义集合$M = { y \in \mathbb{N}_0 \mid \phi(x,y) = \theta(x,y) \text{ 对任意}x }$：

• 首先，$0 \in M$：因为根据条件(i)和(iii)，对任意$x$都有$\phi(x,0)=x=\theta(x,0)$；
• 接下来做归纳步骤：如果$y \in M$，那么：
  $$
  \begin{align*}
  \phi(x, y') &= \phi(x, y)' \quad \text{（来自条件iv）} \
  &= \theta(x, y)' \quad \text{（因为}y \in M\text{，归纳假设成立）} \
  &= \theta(x, y') \quad \text{（来自条件ii）}
  \end{align*}
  $$
  这就说明$y' \in M$。

根据数学归纳法原理，$M$包含了所有非负自然数，也就是说$\phi$和$\theta$完全相等，所以满足条件的运算最多只有一个。

2. 存在性证明

这部分Thurston用了两次归纳，先定义集合$M = { x \in \mathbb{N}_0 \mid \text{对任意}y\text{，存在}\theta(x,y) \in \mathbb{N}_0\text{满足条件(i)(ii)} }$：

• 首先验证$0 \in M$：令$\theta(0, y) = y$，那么：
  $$
  \begin{align*}
  \theta(0, 0) &= 0 \quad \text{（满足条件i）} \
  \theta(0, y') &= y' = \theta(0, y)' \quad \text{（满足条件ii）}
  \end{align*}
  $$
• 归纳步骤：如果$z \in M$（也就是$\theta(z,y)$已经对所有$y$良定义），我们定义$\theta(z', y) = \theta(z, y)'$，然后验证：
  $$
  \begin{align*}
  \theta(z', 0) &= \theta(z, 0)' = z' \quad \text{（满足条件i，因为}z \in M\text{）} \
  \theta(z', y') &= \theta(z, y')' = \theta(z, y)'' = \theta(z', y)' \quad \text{（满足条件ii，因为}z \in M\text{）}
  \end{align*}
  $$
  所以$z' \in M$。

再一次用数学归纳法原理，$M$包含所有非负自然数，因此$\theta(x,y)$对任意$x,y$都存在且满足条件。

我的简化思路，求指点！ #

我在想，是不是不用这么绕？要证明$\theta$的存在性，其实只要证明对任意的$x \in \mathbb{N}_0$，满足条件(i)(ii)的函数$\alpha_x(y) = \theta(x,y)$是良定义的就行？

我直接对所有$x,y \in \mathbb{N}_0$定义：
$$
\begin{align*}
\alpha_x(y) &\in \mathbb{N}_0, \
\alpha_x(0) &= x, \
\alpha_x(y') &= \alpha_x(y)'.
\end{align*}
$$

然后我梳理了下逻辑：

• 当$x=0$时，$\alpha_0$显然是良定义的；
• 如果$x$是$\mathbb{N}_0$中的元素，那它的后继$x'$也属于$\mathbb{N}0$，所以$\alpha{x'}$同样良定义；
• 同理，$y$和$\alpha_x(y)$都是自然数，它们的后继$y'$和$\alpha_x(y)'$也肯定是自然数。

想请教各位，这个简化思路是不是足以证明Thurston定理中$\theta$的存在性？

备注：内容来源于stack exchange，提问作者Steven Thomas Hatton