弗雷格定理和算术基础（四）

4.2 关系R的祖先

接下来，弗雷格定义了关系 x 是 R 级数中 y 的祖先。这个新关系被称为“关系 R 的祖先”，我们从此将这个关系指定为 R^*。弗雷格首先在 Begr 中定义了关系 R 的祖先（第三部分，命题 76），尽管术语“祖先关系”来自 Whitehead 和 Russell 1910-1913 (I, *90·01)。弗雷格对祖先的说法是：“在 R 级数中，x 出现在 y 之前”；或者，“在 R 级数中 y 跟随 x”。 （另请参见 Gl，§79 和 Gg I，§45。）如果我们认为关系 x 是 y 的父亲，那么直观的想法就很容易理解。假设a是b的父亲，b是c的父亲，c是d的父亲。然后定义“x是父亲系列中y的祖先”，使得a是b、c和d的祖先，b是c和d的祖先，c是d的祖先。

弗雷格对 R 祖先的定义需要一个初步定义：

F 在 R 级数中是遗传的，当且仅当每对与 R 相关的对象 x 和 y 都使得只要 x 落入 F 之下，y 就落入 F 之下

正式来说：

\mathit{Her}(F,R) \eqabbr \forall x\forall y(Rxy \to (Fx \to Fy))

直观上，这个想法是，如果只要 x 和 y 是一对与 R 相关的对象，F 总是从 x “传递”到 y，那么 F 在 R 系列中是遗传的。 （我们在这里警告读者，符号 '\mathit{Her}(F,R)' 只是一个更长的语句的缩写。它不是我们语言中形式为 'R(x,y)' 的公式在下文中，我们有时会介绍其他此类缩写。）

弗雷格对 R 祖先的定义现在可以表述如下：

在 R 级数 \eqdef 中 x 出现在 y 之前 y 属于所有那些 R 遗传概念 F，其中 x 与 R 相关的每个对象都属于这些概念 F。

换句话说，只要 y 属于每个 R 遗传概念 F（由与 x 直接 R 相关的所有事物例证），y 就在 R 系列中跟随 x。正式来说：

R^*(x,y) \eqdef \forall F[(\forall z(Rxz \to Fz) \amp \mathit{Her}(F,R)) \to Fy]

例如，克林顿的父亲与切尔西有父亲*（即祖先）的关系，因为她属于克林顿和他的兄弟从克林顿父亲那里继承的每一个遗传概念。然而，克林顿的兄弟不是切尔西的祖先之一，因为他不是她的父亲、她的祖父，也不是切尔西后裔的父亲链中的任何其他环节。

掌握关系 R 与其祖先 R^* 之间的差异非常重要。 Rxy 意味着 R^*(x,y)（例如，如果克林顿是切尔西的父亲，那么克林顿是切尔西的祖先），但反之则不成立（克林顿的父亲是切尔西的父亲*，但他是不是切尔西的父亲）。事实上，掌握 R^* 的定义应该能够证明以下简单的推论，其中许多推论对应于 Begr 和 Gg 中的定理：[11]

关于 R^* 的事实：

Rxy \ 到 R^*(x,y)

\neg\forall R\forall x\forall y(R^*(x,y)\to Rxy)

[R^*(x,y) \amp \forall z(Rxz \to Fz) \amp \mathit{Her}(F,R)] \to Fy[12]

R^*(x,y) \to \存在 z \, Rzy

[Fx \amp R^*(x,y) \amp \mathit{Her}(F,R)] \to Fy

Rxy \amp R^*(y,z) \to R^*(x,z)

R^*(x,y) \amp R^*(y,z) \to R^*(x,z)

读者应该考虑当 R 被视为关系（立即）在先时会发生什么。诉诸我们对数字的直觉把握，我们可以说这是事实 (1) 的一个实例，即如果 10 先于 11，则 10 先于* 11。此外，preces 是事实 2 的见证：10 先于* 12 确实如此并不意味着 10 先于 12。先于 * 的传递性是事实 (7) 的一个实例。下面，当我们将自己限制在自然数时，我们可以直观地将前置和前置*之间的差异视为直接前置和小于之间的差异。

4.3 R的弱祖先

给定关系 R 祖先的概念，弗雷格定义了它的弱祖先，他将其称为“y 是从 x 开始的 R 级数的成员”（参见 Begr，第 III 部分，命题 99；Gl，§81，和 Gg I，§46）：

当且仅当 x 具有 y 的 R 祖先或 x = y 时，y 才是以 x 开头的 R 系列的成员。

正式来说：

R^{+}(x,y) \eqdef R^*(x,y) \lor x\eqclose y

弗雷格还将 R^{+}(x,y) 读作：x 是以 y 结尾的 R 级数的成员。逻辑学家将 R^{+} 称为 R 的“弱祖先”，因为它是 R^* 的弱化版本。当我们定义下面的自然数，并取R为preces时，我们可以直观地把它的弱祖先preces^{+}视为自然数上的小于或等于关系。

R 的弱祖先的一般定义产生以下事实，其中许多对应于 Gg 中的定理：[13]

关于 R^{+} 的事实：

R^*(x,y) \ 到 R^{+}(x,y)

Rxy \到 R^{+}(x,y)

Rxy \amp R^{+}(y,z) \to R^*(x,z)

R^{+}(x,y) \amp Ryz \到 R^*(x,z)

R^*(x,y) \amp Ryz \到 R^{+}(x,z)

R^{+}(x,x)（自反性）

R^*(x,y) \to \exists z[R^{+}(x,z) \amp Rzy]

（事实证明6：弱祖论）

[Fx \amp R^{+}(x,y) \amp \mathit{Her}(F,R)] \to Fy

R^*(x,y) \amp Rzy \amp R \text{ 为 1-1} \to R^{+}(x,z)[14]

这些事实的证明留作练习。

4.4 自然数概念

弗雷格对自然数的定义还需要一个初步的定义。弗雷格将数字0定义为非自同概念的数字，那就是：

0 \eqdef \[\lambda：x \, x\neq x]

由于同一性逻辑保证没有任何对象是非自同一的，因此没有任何东西属于非自同一的概念。如果弗雷格对 \F：的明确定义如他所愿，那么数字 0 实际上将被等同于由所有那些没有任何东西属于的概念的扩展组成的扩展。然而，就目前的目的而言，我们可能会注意到 0 是根据 (a) 基本概念“F 的数量”和 (b) 概念 ([\lambda x \, x\neq x]) 来定义的，其存在由具有同一性和理解性的二阶逻辑保证。从 0 的定义可以直接证明以下关于零的引理：

关于零的引理：

\F\eqclose：0 \equivwide \neg\exists xFx

（关于零的引理证明）

请注意，该证明诉诸于休谟原理和有关等数性的事实。

弗雷格对自然数概念的定义现在可以用前身的弱祖先来表述：

x 是自然数当且仅当 x 是从 0 开始的前驱系列的成员

该定义作为“有限数”的定义出现在 Gl，§83 和 Gg I，§46 中。事实上，自然数正是有限基数。用正式的术语来说，弗雷格的定义是：

Nx ~ \eqdef ~ \mathit{前面}^{+}(0,x)

在下文中，我们有时会使用变量 m、n 和 o 来表示自然数的范围。换句话说，我们将使用 \forall n(\ldots n\ldots) 形式的公式来缩写 \forall x(Nx \to \ldots x\ldots) 形式的公式，并使用 \exists 形式的公式n(\ldots n\ldots) 缩写为 \exists x(Nx \amp \ldots x\ldots) 形式的公式。

5.弗雷格定理

弗雷格定理是数论的五个戴德金/皮亚诺公理可以从二阶逻辑中的休谟原理推导出来。在本节中，我们重构该定理的证明；它可以使用迄今为止汇总的定义和定理从弗雷格的著作中提取出来。这个证明中的一些步骤可以在 Gl 中找到。 （有关重建，请参阅 Boolos 1990 的附录。）我们的重建在精神上和大多数细节上都遵循弗雷格的 Gg，但我们尝试在几个地方简化表示。对于 Frege 的 Gg 证明的更严格的描述，读者可以参考 Heck 1993。以下内容应该有助于读者为 Heck 的优秀论文做好准备。

5.1 零是自然数

零是自然数的陈述是自然数定义的直接结果：

定理1：

诺0

证明：“弱祖先”定义的一个简单结果是 R^{+} 是自反的（参见第 4 节弱祖先小节中关于 R^{+} 的事实 4）。所以 \mathit{ 位于}^{+}(0,0) 之前。因此，根据自然数的定义，0是自然数。

看来弗雷格实际上从未在 Gl 中明确地识别出这个事实，或者在 Gg I 中将此事实标记为编号定理。

5.2 零不是任何自然数的后继

这也是上述的一个简单结果：0 不能接在任何自然数之后。这可以正式表示如下：

定理2：

\neg\存在 x(Nx \amp \mathit{先于}(x,0))

证明：对于约简，假设某个数字（例如 n）满足 \mathit{Precedes}(n,0)。然后，根据前驱的定义，可以得出有一个概念（例如 Q）和一个对象（例如 c），使得 Qc \amp 0\eqclose \Q：\amp n\eqclose \[\lambda：z\, Qz \amp z\neq c]。但是根据关于零的引理（上面），0 = \Q：意味着 \neg\存在 xQx，这与 Qc.

参见 GL，第 78 条，第 (6) 项；和 Gg I，§109，定理 126。

5.3 没有两个自然数有相同的后继

没有两个自然数具有相同后继的事实在某种程度上更难证明（参见 Gl，§78，第 (5) 项；Gg I，§95，定理 89）。我们可以将这个定理表述如下，其中 m、n 和 o 作为范围在自然数范围内的受限变量：

定理3：

\forall m\forall n\forall o[\mathit{先于}(m,o)\amp \mathit{先于}(n,o) \to m = n]

换句话说，该定理断言前驱是自然数上的一对一关系。为了证明这个定理，只要证明前驱是一对一的关系句号就足够了。从休谟原理可以证明前驱是一对一的，借助下面的等数引理，其证明相当长且复杂。等数引理断言，当 F 和 G 等数时，x 属于 F，y 属于 G，则除 x 之外属于 F 的概念对象与除了 y 之外属于 G 的概念对象是等数的。图片是这样的：

图形说明等数引理

图3

根据图 3，等数引理告诉我们，如果存在一个关系 R，它见证了 F 和 G 的等数性，那么就存在一个关系 R'，它见证了以下概念的等数性：将 F 和 G 分别限制为除 x 和 y 之外的对象。

为了帮助我们形式化等数引理，让 F^{-x} 缩写概念 [\lambda z \, Fz \amp z\neq x] 并让 G^{-y} 缩写概念 [\lambda z \, Gz \amp z \neq y]。然后我们有：

等数引理：

F\apprxclose G \amp Fx \amp Gy \to F^{-x}\apprxclose G^{-y}

（等数性引理证明）

现在我们可以根据这个引理和休谟原理证明前驱是一对一的关系（参见 Gg I，§108）：

前任是一对一的：

\forall x\forall y\forall z[\mathit{先于}(x,z) \amp \mathit{先于}(y,z) \to x\eqclose y]

证明：假设a和b都是c的前驱。根据前驱的定义，我们知道存在概念和对象 P、Q、d 和 e，使得：

\begin{align*} & Pd \amp c\eqclose \P：\amp a\eqclose \P^{-d}：\\ & Qe \amp c\eqclose \Q：\amp b\eqclose \Q^：{-e} \end{对齐*}

但如果 c = \P：且 c = \Q，则：\P：= \#Q。因此，根据休谟原理，P \approx Q。因此，根据等数引理，可以得出 P^{-d} \approx Q^{-e}。如果是这样，那么根据休谟原理，\P^{-d}：= \#Q^{-e}。但是，a = b。

因此，如果 Predecessor 是一对一关系，那么它也是自然数上的一对一关系。因此，没有两个数字具有相同的后继者。至此完成了定理3的证明。

这里需要提到的是，Predecessor 不仅是一对一的关系，而且还是一个函数关系：

前驱是函数关系：

\forall x\forall y\forall z[\mathit{先于}(x,y)\amp \mathit{先于}(x,z)\to y\eqclose z]

这个事实可以借助等数引理的一种逆推来证明：

等数引理‘Converse’：

F^{-x}\apprxclose G^{-y} \amp Fx \amp Gy \towide F\apprxclose G

我们将等数引理的证明“逆”和前驱是函数关系的证明作为读者的练习。

5.4 数学归纳法原理

假设概念 F 在自然数上是遗传的，以防每对“相邻”数字 n 和 m（n 在 m 之前）使得只要 n 落在 F 之下，m 就落在 F 之下，即，

\mathit{HerOn}(F,N) \eqabbr \forall n\forall m[\mathit{先于}(n,m)\to (Fn \to Fm)]

那么我们可以将数学归纳原理表述如下：如果（a）0属于F并且（b）F在自然数上是遗传的，那么每个自然数都属于F。用正式术语来说：

定理 4：数学归纳法原理：

F0 \amp \mathit{HerOn}(F,N) \to \forall n Fn

弗雷格实际上从支配任何 R 级数的更一般原理证明了数学归纳原理。我们将后者称为归纳法一般原理。它断言，每当 a 属于 F 时，并且 F 在以 a 开头的 R 级数上是遗传的，那么该 R 级数的每个成员都属于 F 。我们可以在严格理解的帮助下将归纳法的一般原理形式化“R系列上的遗传性以a开头”。这是一个定义：

\begin{align*} &\mathit{HerOn}(F, {}^{a}R^{+}) \eqabbr \\ &\quad \forall x\forall y[R^{+}(a,x )\amp R^{+}(a,y) \amp Rxy \towide (Fx \to Fy)] \end{对齐*}

换句话说，F 在 R 系列的成员上是遗传的，以 a 开头，以防万一该系列中的每个相邻对 x 和 y（其中 x 包含 R 到 y）使得每当 x 落在 F 下时 y 就落在 F 下现在给出这个定义，我们可以将归纳法的一般原理更严格地重新表述为：

归纳法的一般原理：

[Fa \amp \mathit{HerOn}(F, {}^{a}R^{+})] ~\to~ \forall x[R^{+}(a,x) \to Fx]

这是《Gg I》第 117 节中弗雷格定理 152 的一个版本。

我们可以将证明策略概述如下。假设归纳法一般原理的先行词适用于任意选择的概念，例如 P。也就是说，假设：

Pa \amp \mathit{HerOn}(P, {}^{a}R^{+})

现在要显示 \forall x(R^{+}(a,x) \to Px)，选择一个任意对象，例如 b，并进一步假设 R^{+}(a,b)。然后我们只需显示 Pb。我们通过调用关于 R^{+} 的事实 (7) 来做到这一点（在第 4 节中关于弱祖先的小节中）。回想一下事实 (7) 是：

[Fx \amp R^{+}(x,y) \amp \mathit{Her}(F,R)] \to Fy

这是一个包含自由变量 x、y 和 F 的逻辑定理。首先，我们将 x 和 y 分别实例化为 a 和 b。然后，我们将 F 实例化为概念 [\lambda z \, R^{+}(a,z) \amp Pz] 并应用 \lambda-Conversion（尽管弗雷格可以简单地使用他的替换规则来实现相同的推论） F 实例化的概念是以 a 开头且属于 P 的 R 系列的概念成员。实例化 Fact (7) 中的自由变量然后应用 lambda-Conversion 的结果是一个相当长的结果。有条件，先行词中有许多连词，而后词中有 Pb。这样，如果前件成立，证明就完成了。对于那些用铅笔和纸跟随的人来说，先行词中的所有连接词都是我们已经知道的，除了 [\lambda z \, R^{+}(a,z)\amp Pz] 是然而，这个断言可以从我们已知的真实事物中直接成立（特别是从我们试图证明的原理的前提中包含的事实，我们假设这是我们条件的一部分）我们鼓励读者完成证明作为练习。对于那些想要检查自己工作的人，我们在这里给出了归纳法一般原理的完整证明：

归纳法一般原理的证明