递归的魅力 - 定义自然数系和自然数加法


作为Rudin的《数学分析原理》的补充,最近在读《陶哲轩实分析》,读Rudin的时候五体投地,读了《陶实》发现还有更神的。《数分》没有讲自然数和加法乘法,而是直接讲了域的公理,将加法乘法作为公理,然后从戴德金分割讲$\mathbb{R}$,十分乏味。然而《陶实》从Peano公理定义自然数讲起,并且涉及到数学思想,比如公理化构造数系、归纳、递归。读过《陶实》再回去看《数分》会觉得十分清晰。

这里作为一个笔记和民科,总结一下公理化定义自然数系$\mathbb{N}$到自然数加法的过程,一些我们认为理所当然的东西的证明,比如加法交换律结合律的正确性,让工科生文科生感受一下数学的严谨和递归的魅力(不属于上述两个范围的同学出门左转去看CS类文章谢谢 :P)。

Peano公理

首先引入一种运算,或者说表示方法,学计算机的同学会比较熟悉:$n++$表示n的“自增“,即$n = n + 1$,这个奇怪的等式在数学中不会这么用,一个变量定义两次容易引起混淆,在这里我们取$n++$的值,即$n++$表示紧跟在$n$后面的自然数。

要定义自然数,首先我们要有a priori,即证明前假定为真的东西,就是Peano公理。

公理1:$0$是自然数
公理2:若$n$是自然数,则$n++$也是自然数

接下来就可以用公理1,2递归地给所有自然数定义

$1 := 0++$
$2 := 1++$ 即 $(0++)++$
$3 := 2++$ 即 $((1++)++)$,$((0++)++)++$
等等

里面的符号:=的意思是“根据定义相等”。

为使自然数系不会因达到一个值之后就回归0(比如计算机中用表示2 bytes(16 bits)表示unsinged,到$65535_{(10)}$即$1111 1111 1111 1111_{(2)}$之后就溢出变0,不懂计算机的也可以想一个可以表示3个数字的里程表,999之后就会变成000)引入另一个公理:

公理3:0不是任何自然数的后继,即$\forall n \in \mathbb{N}, n++ \neq 0$

这样并没有禁止类似$5 = 6$即$4++ = 5++$的情况,为了保证所有自然数的独特性,引入

公理4:不同自然数有不同后继,即$\forall n,m \in \mathbb{N}, n \neq m$,则$n++ \neq m++$,用逆否命题等价地说,若$n++ = m++$,则$n = m$

回顾公理1 - 4,我们的公理至此只是定义了自然数,但还没有说类似0.5 1.5这种数不属于自然数系,所以我们引入:

公理5:设$P(n)$是一个关于自然数的性质,若$P(0)$是真的,并假设只要$P(n)$是真的,则$P(n++)$也是真的,那么对于每个自然数$n$,$P(n)$都是真的

Behold,公理5就是著名的数学归纳原理了,与其说它是一个公理,它其实是一个公理框架(axiom schema),它是一个产生无限公理的模板,因为并没有限制性质$P$是什么。

公理5如何将0.5或1.5排除?将性质$P$定为“$n$不包含小数部分“就可以了。根据公理5很容易证明这个$P$是成立的。但是这个证明并不完善,因为我们刚刚定义了自然数,还不知道什么小数部分,但是这给了我们一个方向。

公理1 - 5就是Peano 公理了,有了这些公理我们就有了健康的自然数系。

我们的定义是公理化的,除了这种方式,还有构造性的,比如一开始我提到的由戴德金分割构造$\mathbb{R}$,可能将来会讲讲。公理化的定义已经足够了,这些公理没有说自然数是什么,由什么构成,也不管是罗马数字表示、二进制表示、还是阿拉伯数字,等等,我们只是定义了它的性质,它能干嘛,数学本身就是抽象地,不关注细节,只要能服从所有的公理正确运作,对于数学就足够好了。

接下来我们看看数学归纳原理能干什么神奇的事情。

由于数学归纳是我们继续给出加法定义以及很多其他自然数性质推论的基础,十分重要,首先我们复习一下初中数学 - 如何使用数学归纳原理,我们通过一个命题来说明

Q: 证明某种性质$P(n)$对每个自然数都成立
证明:首先验证基础情形$n = 0$时,即证明$P(0)$成立,{插入对$P(0)$的证明};归纳地假定对任意自然数$n$也被证明即$P(n)$为真,{插入对$P(n++)$的证明}。根据数学归纳原理,即可得证

自然数的递归定义

有了公理化的自然数定义,我们就可以用递归的方法来定义自然数了,注意此时还没有引入数系的概念,所以严格地说,我们定义的是一个自然数序列:

设对每个自然数n,都有某个函数$f_n:\mathbb{N}\rightarrow\mathbb{N}$把自然数映射成自然数。设$c$是一个自然数,那么可以对每个自然数$n$指定唯一一个自然数$a_n$使得$a0=c$且$a{n++}=f_n(a_n)$

我们用归纳法结合Peano公理证明这个定义:

当$n = 0$,$a_n = c$,符合为了防止回归的公理3,$a_0$不是任何数的后继。
现归纳地假设此过程给$a_n$一个唯一的值,那么它赋予$an++$一个唯一的值$a{n++}:=f_n(an)$,符合公理4,$a{n++}$没有其它的定义。
根据归纳原理,定义成立。

你可能要问,归纳法原理不是自然数的一个性质吗,为什么证明这个自然数定义的时候可以使用?注意,我们是在数列的下标进行的归纳,所以使用归纳法没有问题。另外,由于递归地从$a0$开始定义,不可能出现$a{0.5}$这样的定义。

自然数的加法

现在我们的自然数系还很朴素,只有一堆公理和增长运算,我们继续用递归做一些神奇的事情,比如完美地定义加法乘法。

以$5 + 3$为例我们思考一下该如何定义,$5 + 3$等同于让5增加三次,等同于$5 + 2$增长一次即$(5 + 2)++$,等同于$5 + 1$增长两次即$((5 + 1)++)++$,等同于$5 + 0$增长三次,即$(((5 + 0)++)++)++$,而$5 + 0$恰恰是5。根据这个规律,我们可以如下定义自然数的加法:

设$m$是自然数,为使$m$加上零,定义$0 + m := m$。归纳地假设已经定义好$m + n$,那么$m$加于$n++$则定义为$(n++) + m := (n + m)++$。

由上面的递归定义,我们就能对每个$n$给出$n + m$的定义。例如,根据$0 + m = m$,$1 + m = (0++) + m = (0 + m)++ = m++$,$2 + m = (1++) + m = ((0 + m)++)++ = (m++)++$。

现在我们知道关于加法的东西只有两个:$0 + m = m$以及$(n++) + m = (n + m)++$,但是这已经足以演绎出一切关于加法的性质,比如:

以及一系列的引理、推论。证明的主要思想就是使用归纳法,无一例外,说到这里已经很trivial了,具体的证明留给感兴趣的读者自己去做。

总结

到这里我们的目的就达到了,我们从“0”(真正的0)定义了自然数,递归地定义了自然数加法,并且使用归纳法,证明了自然数的性质,结合律交换律不再是数学书里面的一行规定,我们知道它是真确的了。接下来可以用类似的方法定义乘法,减法和除法只是加乘的逆运算,很简单就能得到,然后就要向实数系进发了,而实数系的性质是数学分析的基础,如果你感兴趣,可以期待后续。