数学证明与数学/逻辑/公理和等式原理

我们现在已经涵盖了大部分被称为一阶逻辑的内容，或者至少我们已经涵盖了本书其余部分需要的内容。还存在二阶和更高阶逻辑，我们只简要介绍一下。二阶逻辑涉及以一阶谓词为参数的谓词，而不是论域的物体。例如，关系 $P(x,y)$ 如果

对所有 $x$，$P(x,x).$

谓词

$P$ 是一个自反关系

然后是一个二阶谓词。在这个方向上必须小心，以避免谓词被应用于自身，否则可能会出现前面讨论的“说谎者悖论”之类的自指语句，导致矛盾，整个系统可能会崩溃。我们将在后面看到更多关于这一点的信息。

虽然我们有时会在二阶谓词的形式下进行定义，但这些应该被认为是语言上的捷径，可以用它们的定义来替换。

公理系统

在没有引入公理的情况下，我们已经尽可能地走了，但我们需要它们来前进，所以现在是详细谈谈它们的时候了。

到目前为止，仅使用推理规则，我们只证明了重言式，换句话说，这些语句并没有真正表达任何有意义的内容。它们可以作为练习，但在表达关于宇宙的任何有趣内容方面，它们并不是有用的。早在欧几里得之前就意识到，为了避免循环论证，必须做出一些初始假设，正如你可能称之为逻辑上的自举。

这个过程是这样的

1. 列出关于论域的假设。这些假设被称为公理。
2. 使用逻辑来证明新的、有希望的有趣陈述。这些陈述被称为定理。

这个公理列表有时被称为公理系统。公理从哪里来是一个有趣的问题。它们可能来自哲学、经验，或者通过抽象其他系统的属性而来。

公理系统的有用性质

为了有用，公理最好具有以下性质

• 一致性（存在一些不是定理的陈述）：这是必须具备的特性，否则该系统无法区分定理和非定理，因此毫无用处。另一种说法是语句 $False$ 不是一个定理，换句话说，不可能从公理中推导出矛盾。

• 完备性（每个命题都有证明或反证）：这是必备的功能，因为能够判断给定命题的真假是可取的。换句话说，不应该存在无法解决的猜想，即既不可能证明也不可能找到反例。请注意，这与说命题 $P$ 是定理或不是定理不同，因为我们可能知道 $P$ 是真还是假，而不知道它是哪个。 （不过，这有点争议；请参阅非标准逻辑部分。）另请注意，有很多猜想，其中一些很著名，我们目前还没有找到 $P$ 的证明或非 $P$ 的证明。但这仅仅意味着尚未找到证明，并不意味着证明是不可能的。

• 独立性（公理之间不能互相证明）：这既出于审美原因，也出于实际原因。从审美角度来看，如果系统没有多余的、不需要的公理，系统会更干净、更优雅。在实用方面，假设您有一个系统，您试图用公理对其进行建模。您首先需要做的是验证公理是否确实在您的系统中成立。不必要的公理增加了此工作量，而没有额外的好处。

旁注：为了证明公理独立于其他公理，人们需要找到一个所有公理都成立但给定公理不成立的数学系统。这表明给定公理不能从其他公理中证明出来，因为如果能证明出来，它就会在给定系统中成立。

• 无争议性（关于应包含哪些公理，存在普遍共识）：如果这一点不成立，则理论的结论可能会受到争议。

• 效力（公理应该易于描述，但能推导出大量丰富的数学结果）：这最终决定了理论的实用性。有时，同一组公理可以用来对不同的系统进行建模，而您从理论中学习到的知识可以应用于两者。

给定一个公理系统，能够以某种方式证明它是一致的和完备的，这会令人欣慰。不幸的是，这在 1930 年代被库尔特·哥德尔证明是不可能的，至少对于任何可用于数学的系统而言都是如此。

使用公理

我们现在可以引入另一个推理规则

如果 $P$ 是一个公理，那么推导出 $P.$

换句话说，您可以在证明中使用任何公理，无需其他理由，只需它是一个公理即可。

等式公理

我们的第一个公理与等式有关。虽然从技术上讲，这仍然属于逻辑的范畴，但我们现在已经足够接近，可以从地平线上看到数学了。

请注意，我们永远不会真正定义短语 $x$ 等于 $y$，因为这样做不可能不循环。我们可以列出一些公理，这些公理告诉我们相等的对象如何表现，从某种意义上说，这等同于定义。我们还可以对 $x$ 等于 $y$ 的含义给出非正式的描述，这旨在作为直观的指南，并有助于使公理看起来合理，但这没有逻辑上的意义，不能在证明中使用。我们假设您已经对 $x$ 等于 $y$ 的含义有直观的了解，因此在这种情况下我们将跳过这一部分。

公理 E0： 在论域的宇宙中定义了一个关系 “=”，写作 $x=y$，读作 $x$ 等于 $y$。

关系通常使用中缀表示法 $(xRy)$ 来表示，而不是前缀表示法 $(R(x,y))$。这个公理实际上只是保留了 “=” 符号，赋予它一个特殊的含义。

公理 E1（同一性）： 对于所有 $x$，$x=x$。

鉴于对等式的直观概念，这似乎是不言而喻的。安·兰德的粉丝可能会认出这是《阿特拉斯耸耸肩》中的 “A 是 A” 这句话。这也被称为自反性。

公理 E2（替换）： 如果 $P(x),$ 是一个谓词，那么对于所有 $x$ 和 $y$，$x=y$ 并且 $P(x)$ 意味着 $P(y)$。

这实际上不是一个单独的公理，而是一个所谓的公理模式。（这里的 “模式” 这个词是一个非常专业的术语，基本上是指食谱或蓝图；只要每次看到它就用 “食谱” 来代替 “模式”，你就不会错得太远。） 对于每个谓词，你都会得到一个新的公理，因此，这是一种获得任意数量公理的紧凑方式。 我们在这里开始放松逻辑形式主义，并在措辞中使用它。 它的意思很清楚，因此没有必要严格遵守前几页中使用的措辞和括号。

等式的性质

我们现在可以从公理中证明等式的两个最重要的性质。

定理 E3（对称性）： 对于所有 $x$ 和 $y$，$x=y$ 意味着 $y=x$。

证明： 选择 $a$ 和 $b$，并假设 $a=b$。 令 $P(z)$ 为谓词 $z=a$。 那么根据公理 E1，$P(a)$ 成立。 同时，$a=b$，所以 $P(a)$ 意味着 $P(b)$。 所以 $P(b)$，这等同于说 $b=a$。 我们有 $a=b$ 意味着 $b=a$，对于任意 $a$ 和 $b$，因此对于所有 $x$ 和 $y$，$x=y$ 意味着 $y=x$。

请注意，我们将在文本中逐渐淘汰表格式证明，将其作为读者练习来完成所有细节。

定理 E4 (传递性)： 对于所有 $x$，$y$ 和 $z$，$x=y$ 和 $y=z$ 意味着 $x=z$。

证明： 这个问题留作练习，以下是一点提示。选择 $a$，$b$ 和 $c$，并假设 $a=b$ 以及 $b=c.Let<math>P(w)$ 是谓词 $a=w$。（此时，我们留给读者完成证明的剩余部分。）

定义对象

除了公理之外，数学家还将定义作为基本原则。我们可以像一直以来那样，使用逻辑联结词和之前定义的语句和谓词来定义新的语句和谓词。但我们还想能够根据一个对象的属性来定义它。那么，要使这样的定义有意义，需要哪些条件？让我们考虑一个谓词 $P(x)$，并试着找出使以下语句成为有效定义所需的条件。

定义 $X$ 为使 $P(X)$ 为真的对象。

成为一个有意义的定义。

首先，我们需要这样的 $X$ 存在。因此，我们需要以下语句

(存在性) 对于某个 $x$，$P(x)$

为真。要求这一点是合理的，否则我们将同时拥有 $P(X)$ 和 对于所有 $x$，非 $P(x)$，这将导致矛盾。

不过，我们还需要另一个要求。假设一个人选择了一个 $X$ 作为使 $P(X)$ 为真的 “唯一” 对象，而另一个人选择了一个 $Y$ 作为使 $P(Y)$ 为真的 “唯一” 对象。现在假设 $X$ 具有某种 $Y$ 不具备的属性，换句话说，存在一个谓词 $Q(x)$，使得 $Q(X)$ 为真，而 $Q(Y)$ 为假。这再次导致矛盾，因为 $X$ 和 $Y$ 被认为是同一个对象，但 $Q$ 对其中一个为真，而对另一个为假。因此，我们需要确保如果 $P(X)$ 和 $P(Y)$ 为真，那么不存在一个谓词 $Q(x)$，使得 $Q(X)$ 为真，而 $Q(Y)$ 为假。但公理 E2 在 $X=Y$ 时就给出了这个条件。因此，我们添加了另一个条件，即该语句

(唯一性) 对于所有 $x$ 和 $y$，$P(x)$ 和 $P(y)$ 意味着 $x=y$

为真。

这两个条件，存在性和唯一性，似乎就足够了。我们可以说这个表达式

满足 $P(X)$ 的 $X$

是定义明确的，如果 $P(x)$ 具有存在性和唯一性属性。我们可以宣布 $X$，或者任何我们想要使用的其他符号，作为我们论域中对象的名称，并取

$P(X)$

作为公理。如果 $P(x)$ 不具有存在性和唯一性属性，那么我们当然可以写下这个表达式，但它没有任何意义，换句话说，它是未定义的。我们将在后面介绍更简洁的符号，但首先我们将推广这个想法。

函数关系

不用谓词，我们从关系 $P(x,y)$ 开始。这一次我们想知道是否

定义 $Y(x)$ 是满足 $P(x,y)$ 为真的对象。

是有意义的。这开始接近函数的概念，但我们将“函数”这个词保留到下一章中涉及集合的更复杂结构中。我们已经使用过“函数”这个词，但只是作为直觉的引导，而不是定义。

遵循上一节中的类似推理，我们说

满足 $P(x,y)$ 的 $Y(x)$

是定义明确的，如果

对于某些 $y$，$P(x,y)$

并且

对于所有 $x$，$y$ 和 $z$，$P(x,y)$ 和 $P(x,z)$ 意味着 $y=z.$

我们说一个关系 $P(x,y)$ 是一个函数关系，如果它满足第二个条件。

类似地，对于一个三变量的关系 $P(x,y,z)$，我们说

对于那些 $Z(x,y)$，使得 $P(x,y,z)$

是定义明确的，如果

对于某个 $z$，$P(x,y,z)$

并且

对于所有 $x$，$y$，$z$ 和 $w$，$P(x,y,z)$ 和 $P(x,y,w)$ 意味着 $z=w.$

我们可以将此扩展到任意多个变量。关系 $P(x,y,z)$ 是一个函数关系，如果它像之前一样满足第二个条件。

如果表达式 "The $Z(u,v,\dots )$ for which $P(u,v,\dots ,z)$" 是定义良好的，那么我们将 $P(u,v,\dots )$ 写作该 $Z$ 的标准符号。我们在这里重载了括号符号，但这不应该是一个问题，因为您可以通过计数参数来判断其含义。

回到谓词，我们将 $P()$ 解释为 $X$，对于它 $P(X)$。

概括一下，如果 $P(u,v,\dots ,z)$ 是至少一个变量的关系，我们将 $P(u,v,\dots )$ 解释为 $z$ 的值，对于它 $P(u,v,\dots ,z)$，前提是

对于某些 $z$，$P(u,v,\dots ,z)$

并且

对于所有 $u$，$v$，... $z$ 和 $w$，$P(u,v,\dots ,z)$ 和 $P(u,v,\dots ,w)$ 意味着 $z=w$.

如果两个条件不满足，则表达式 $P(u,v,\dots )$ 未定义，不代表任何有意义的东西。如果 $P(u,v,\dots )$ 已定义，则

$P(u,v,\dots ,P(u,v,\dots ))$

是一个公理。

作为一个练习，将此应用于相等关系。也就是说，如果 $E(x,y)$ 被定义为 $x=y$，那么证明对于所有的 $x$，$E(x)$ 已定义，并且 $E(x)=x$.

其他方法（可选）

我们在这里使用的方法并不是唯一可用的方法。另一种方法是简单地声明一个函数接受 0 个或多个对象作为参数并返回另一个对象，而不是像关系那样返回一个真值。因此，0 个变量的函数与常数相同。在这种情况下，您需要一个额外的公理用于 '='

如果 $F(x)$ 是任何函数，那么对于所有的 $x$ 和 $y$，$x=y$ 并且 $F(x)$ 已定义意味着 $F(y)$ 已定义并且 $F(x)=F(y)$.

注意，我们不想假设 $F(x)$ 对于所有的 $x$ 都具有一个值，因为这会过分限制概念的有用性。

另一种方法是 Bourbaki 采用的方法，它遵循 Hilbert 的 epsilon 演算，不过使用了不同的符号。在这种情况下，短语

一些 $X$，对于它 $P(X)$

“总是”定义了一个$X$。为了避免不同的人可能选择不同值的问题，假设值$X$ 由谓词$P(x)$ 以某种方式确定，因此每个人选择一个$X$ 都将得到相同的答案。这需要以下额外的公理

(对于所有$x$，$P(x)$ 当且仅当$Q(x)$) 意味着 (存在一个$X$ 使得$P(X)$)=(存在一个$X$ 使得$Q(X)$)

选择满足$P(X)$ 的每个人都得到相同的$X$ 似乎要求很高。当$P(X)$ 具有存在性和唯一性属性时，短语“存在一个$X$ 使得$P(X)$” 和 “满足$P(X)$ 的$X$” 等同于同一个东西。

我们选择这里使用的这种方法，因为在后面的章节中，我们会遇到一些情况，很容易被错误的定义所欺骗。换句话说，你可能认为你已经定义了一个函数，但实际上并没有定义任何东西，因为逻辑要求没有满足。我们使用的方法明确地列出了这些要求，这样一旦这些要求被检查，我们就可以放心地继续前进，因为没有隐藏的错误。