数学证明与数学/数字/自然数原理

之前，我们根据集合论公理，将自然数构造为集合。

现在，我们从算术的角度来研究自然数，我们将看到如何从后继运算推导出我们熟悉的加法和乘法的概念。由于我们正在从集合论转向算术，我们将用 $\mathbb {N}$ 来代替 $\omega$ 表示自然数。由于我们即将引入算术，但尚未进行，在本节中我们将暂时使用S(n) 代替n + 1 来表示n 的后继。

定义

定义加法由 0 和后继函数通过以下两条规则定义：

定义 1	a + 0 = a
定义 2	a + S(b) = S(a + b)

我们将首先看到这个定义如何证明我们之前对a + 1 作为a 后继的使用是合理的。

对于每个自然数a，我们有：

	S(a)
=	S(a + 0)	[根据定义 1]
=	a + S(0)	[根据定义 2]
=	a + 1	[根据 1 的定义]

归纳原理

我们现在将展示如何从定义中推导出你在学校学习过的所有加法的性质。

这些证明依赖于归纳原理。回忆一下定理：

归纳原理 假设 $P(x)$ 是自然数的一个性质，对于该性质， $P(0)$ 成立，并且对于所有自然数 $n$ ，如果 $P(n)$ 成立，那么 $P(n+1)$ 也成立。那么 $P(n)$ 对于每个自然数 $n$ 成立。

当使用归纳原理进行证明时，我们称 $P(0)$ 的证明为基本情况，称 $P(a+1)$ 从 $P(a)$ 的证明为归纳步骤。在归纳步骤的证明中，我们将使用我们可以假设 $P(a)$ 的事实，并将其称为归纳假设。让我们看看它在实践中的应用。

与 0 的加法

定义 [定义 1] 直接说明 0 是一个右单位元，也就是说，对于任何数a，a + 0 = a。

我们证明 0 是一个左单位元，也就是说，0 + a = a，方法是对自然数a 进行归纳。

定理对于每个自然数a，0 + a = a.

对于基本情况a = 0，根据定义 [定义 1]，0 + 0 = 0。

因此，我们继续进行归纳步骤。我们可以假设归纳假设，即 0 + a = a。那么

	0 + S(a)
=	S(0 + a)	[根据定义 2]
=	S(a)	[根据归纳假设]

因此，我们已经证明了0 + S(a) = a，前提是假设 0 + a = a。因此，我们可以根据归纳原理得出结论，0 + a = a，对于每个自然数a 都成立。

结合律

让我们尝试一个更复杂的例子，结合律。

定理对于任何三个自然数a, b 和c，(a + b) + c = a + (b + c).

首先要注意的是，我们这里有三个数字，*a*、*b* 和 *c*。所以我们将固定 *a* 和 *b* 为任意数字，并将归纳原理应用于 *c*。

更准确地说，性质 $P(c)$ 是 $(a+b)+c=a+(b+c)$ .

对于基本情况 *c* = 0，

(*a*+ *b*) + 0 = *a* + *b* = *a* + (*b* + 0)

每个等式都根据定义 [Def. 1] 得出；第一个是 *a* + *b*，第二个是 *b*。

现在，对于归纳步骤。我们假设归纳假设，也就是说，我们假设对于某个自然数 *c*，

(*a* + *b*) + *c* = *a* + (*b* + *c*)

然后它随之而来，

	(a + b) + S(c)
=	S((a + b) + c)	[根据定义 2]
=	S(a + (b + c))	[根据归纳假设]
=	a + S(b + c)	[根据定义 2]
=	a + (b + S(c))	[根据定义 2]

换句话说， $P$ 对 *S*(*c*) 成立。因此，关于 *c* 的归纳是完整的。

交换律

另一个你从学校就会知道的重要的性质是交换律：当加两个数字时，顺序无关紧要。

定理对于任意两个自然数 *a* 和 *b*，*a* + *b* = *b* + *a*。

由于这更加复杂，我们首先介绍一个引理。

一个有用的引理

引理对于任意两个自然数 *a* 和 *b*，*S(a) + b = S(a + b)*。

让我们对 *b* 进行归纳，从基本情况 *b = 0* 开始

	S(a) + 0
=	S(a)	[根据定义 1]
=	S(a + 0)	[根据定义 1]

现在是归纳步骤

	S(a) + S(b)
=	S(S(a) + b)	[根据定义 2]
=	S(S(a + b)	[根据归纳假设]
=	S(a + S(b))	[根据定义 2]

就这样 - 关于 *b* 的归纳是完整的。

交换律的证明

从这个简短的离题，我们获得了可以用来证明交换律的性质。

我们将再次通过对 *b* 进行归纳来进行，从基本情况开始

	a + 0
=	a	[根据定义 1]
=	0 + a	[根据右单位元定理]

请注意，基本情况只是我们上面显示的单位元性质的直接结果。

现在，假设对于所有自然数 *a*，我们有 *a* + *b* = *b* + *a*。我们必须证明对于所有自然数 *a*，我们有 *a* + *S*(*b*) = *S*(*b*) + *a*。我们有

	a + S(b)
=	S(a + b)	[根据定义 2]
=	S(b + a)	[根据归纳假设]
=	S(b) + a	[根据引理]

这完成了关于 *b* 的归纳。

乘法

到目前为止，我们介绍了加法，并推导出关于自然数上加法的基本性质。但算术不仅仅是加法，当然。因此，就像我们从后继关系推导出加法一样，我们将从加法推导出乘法

定义乘法由 0、加法和后继函数根据以下两个规则推导出

Def. 3	$a\cdot 0=0$
Def. 4	$a\cdot S(b)=a\cdot b+a$

我们可以很快地在脑海中检查这两个方程是否确实在我们对自然数的直觉中成立。

由于您现在熟悉了如何使用归纳法解决问题，我们把交换律和结合律的证明留给您。

分配律

但是，在我们让您去做之前，让我们再了解一个由两个不同的运算符的存在而产生的性质。它被称为分配律。

定理对于任意三个自然数 *a*、*b* 和 *c*， $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ .

我们通过对 *c* 进行归纳来证明分配律

从基本情况开始

	$a\cdot (b+0)$
=	$a\cdot b$	[根据定义 1]
=	$a\cdot b+0$	[根据定义 1]
=	$a\cdot b+a\cdot 0$	[根据定义 3]

...并通过归纳法继续

	$a\cdot (b+S(c))$
=	$a\cdot S(b+c)$	[根据定义 2]
=	$a\cdot (b+c)+a$	[根据定义 4]
=	$(a\cdot b+a\cdot c)+a$	[根据归纳假设]
=	$a\cdot b+(a\cdot c+a)$	[根据加法的结合律]
=	$a\cdot b+a\cdot S(c)$	[根据定义 4]

这就是要证明的结论。

练习

现在您已经看到了各种归纳论证技术的应用，您应该尝试自己找出乘法的剩余属性。

尝试逐行写出这些属性，并在等式的右侧注明所用恒等式的来源，就像本页中的布局一样。

为了帮助您，右侧图表显示了属性之间相互依赖关系的简要概述。它还包括我们已经见过的属性的推导，以及乘法和加法的定义。

祝你好运！

参考文献

本页中归纳证明的经典参考书是 Edmund Landau 的 *Foundations of Analysis*，Chelsea Pub Co. ISBN 0-8218-2693-X。您可以在其中找到大量进一步的属性和练习，以及关于指数运算的介绍。

	(a + b) + S(c)
=	S((a + b) + c)	[根据定义 2]
=	S(a + (b + c))	[根据归纳假设]
=	a + S(b + c)	[根据定义 2]
=	a + (b + S(c))	[根据定义 2]