假设存在一个算数系统的模型满足 Peano 公理,即假定 Peano 公理相容,在此承认次假设的基础之上,我们即可建立如今最常用的算术公理系统。自然数的定义则是构建此算术公理系统的第一步。
先介绍 Peano 公理,共有五条:
0 是自然数;
任何自然数的后继存在且唯一,下文用 suc(n) 表示 n 的后继;
0 不是任何自然数的后继;
不同的自然数后继不同;
p(n) 是关于自然数 n 的一个命题,且满足两个条件:
- p(0) 是真命题;
- 由 p(n) 为真命题可以推理出 p(suc(n)) 为真命题。
则有,对于任意自然数 n,p(n) 为真命题。
这样就定义了自然数,自然数这个新的数学对象因我们的假设而确立。
自然数中最重要的运算当然是加法。
定义加法的运算规则:
- 若 n 是自然数,则 0+n 的运算结果为 n,即 0+n=n;
- 若 n,m 都是自然数,则 suc(m)+n=suc(m+n)。
下面我们需要证明对于任意两个自然数,都可以进行加法运算,也就是说,我们需要证明加法结果的存在性和唯一性。
n 是任意自然数,记 pn(m) 表示 m+n 是否是自然数,即 m+n 是否存在。
n 是自然数,由加法运算规则 I 有 0+n=n,进而有 0+n 是自然数; 即 pn(0) 得证。
m 和 m+n 是自然数,由 Peano 公理 II 有 suc(m) 和 suc(m+n) 是自然数; 根据加法運算規則 II 有 suc(m)+n=suc(m+n),进有 suc(m)+n 是自然数; 综上所述,若 m+n 是自然数,则 suc(m)+n 也是自然数; 即由 pn(m) 为真命题可以推出 pn(suc(m)) 为真命题。
由 pn(m) 的性质和 Peano 公理 V 有,对于任意自然数 m,pn(m) 成立,即 m+n 是自然数,再根据 n 的任意性,得出对于任意自然数 n,m,m+n 都是自然数。
n 是任意自然数,记 pn(m) 表示 m+n 是否唯一,即 m+n 的结果是否唯一。
n 是自然数,由加法運算規則 I 有 0+n=n,进而 0+n 是唯一的,就是 n; 即 pn(0) 得证。
m 是自然数,m+n 是唯一的,由 Peano 公理 II 有 suc(m) 是自然数且 suc(m+n) 唯一; 根据加法運算規則 II 有 suc(m)+n=suc(m+n),进有 suc(m)+n 唯一; 综上所述,若 m+n 唯一,则 suc(m)+n 也唯一; 即由 pn(m) 为真命题可以推出 pn(suc(m)) 为真命题。
由 pn(m) 的性质和 Peano 公理 V 有,对于任意自然数 m,pn(m) 成立,即 m+n 唯一,再根据 n 的任意性,得出对于任意自然数 n,m,m+n 都是唯一的。
在明确证明了自然数加法運算的良好性质,即任意两个自然数都可以进行加法運算,且加法運算的结果存在且唯一之后,我们终于可以对自然数加法的性质进行进一步的探索。
下面证明加法交换律,即对于任意自然数 n,m,有 n+m=m+n。
直接证明比较困难,考虑从加法運算的定义下手,即先证明加法的两条運算规则符合交换律。
试证 0+n=n=n+0,首先有
0+0=0=0+0
进而当 n 是自然数且 0+n=n=n+0 时有
0+suc(n)=suc(n)=suc(n+0)=suc(n)+0
根据 Peano 公理 V,得知 0+n=n=n+0 对任意自然数 n 成立。
试证 m+suc(n)=suc(m+n)=suc(m)+n,首先有
0+suc(n)=suc(n)=suc(0+n)=suc(0)+n
进而当 m 是自然数且 m+suc(n)=suc(m+n)=suc(m)+n 时有
suc(m)+suc(n)=suc(m+suc(n))=suc(suc(m+n))=suc(suc(m)+n)=suc(suc(m))+n
根据 Peano 公理 V,得知 m+suc(n)=suc(m+n)=suc(m)+n 对任意自然数 n,m 成立,将其称为新的加法運算規則 II。
证明了加法運算規則的交换律之后,试证加法交换律 n+m=m+n,首先由加法運算規則 I 有 0+m=m+0,进而当 n 是自然数且 n+m=m+n 时,有
suc(n)+m=suc(n+m)=suc(m+n)=m+suc(n)
根据 Peano 公理 V,得知 n+m=m+n 对任意自然数 n,m 成立,即加法交換律成立。
下面证明加法结合律,即对于任意自然数 a,b,c,有 (a+b)+c=a+(b+c)。
首先当 c=0 时,有
(a+b)+c=(a+b)+0=a+b=a+(b+0)=a+(b+c)
进而当 c 为自然数且 (a+b)+c=a+(b+c) 时有
(a+b)+suc(c)=suc((a+b)+c)=suc(a+(b+c))=a+suc(b+c)=a+(b+suc(c))
根据 Peano 公理 V,得知 (a+b)+c=a+(b+c) 对任意自然数 a,b,c 成立,即加法结合律成立。
下面证明加法消去律,即对于任意自然数 a,b,c,有 a+c=b+c⇔a=b。
试证 a=b⇒a+c=b+c。
首先当 c=0 时有
a+c=a+0=a=b=b+0=b+c
进而当 c 为自然数且 a=b⇒a+c=b+c 时有
a+suc(c)=suc(a+c)=suc(b+c)=b+suc(c)
即 a=b⇒a+c=b+c⇒a+suc(c)=b+suc(c),根据 Peano 公理 V,得知 a=b⇒a+c=b+c 对任意自然数 a,b,c 成立。
试证 a+c=b+c⇒a=b。
首先当 c=0 时有
a=a+0=a+c=b+c=b+0=b
进而当 c 为自然数且 a+c=b+c⇒a=b 时有
a+suc(c)suc(a+c)a+ca=b+suc(c)=suc(b+c)=b+c=b
即 a+suc(c)=b+suc(c)⇒a+c=b+c⇒a=b,根据 Peano 公理 V,得知 a+c=b+c⇒a=b 对任意自然数 a,b,c 成立。
综上所述,加法消去律 a+c=b+c⇔a=b,对任意自然数 a,b,c 成立。
自然数的序为两个自然数的关系。
定义自然数的序即定义 n≤m 当且仅当存在自然数 x 满足 n=m+x。定义 n<m 当且仅当 n≤m 且 n=m。
自然数的序是全序关系,它应该具有反对称性、传递性和完全性。
在考察序的性质之前,我们预先准备以方便证明。
定义正自然数为非 0 自然数。
正自然数与自然数相加为正自然数,即对于正自然数 a,其与自然数 b 的和 a+b 为正自然数。
首先,当 b=0 时,a+0=a 为正自然数。
进而当 b 为自然数且 a+b 为正自然数时有 a+suc(b)=suc(a+b),根据 Peano 公理 III,suc(a+b) 为正自然数,进而 a+suc(b) 为正自然数。
根据 Peano 公理 V,正自然数与自然数相加为正自然数。
若 a≤b 且 b≤a,则 a=b。
由 a≤b 有 b=a+m1,由 b≤a 有 a=b+m2。
因此 0+a=a=b+m2=a+m1+m2,由加法消去律得到 m1+m2=0,根据正自然数的性质得出 m1=m2=0,因此 a=a+0=a+m1=b。
若 a≤b 且 b≤c,则 a≤c。
由 a≤b 有 b=a+m1,由 b≤c 有 c=b+m2。
根据加法结果的存在性得到 m1+m2 是自然数,根据加法结合律得出 c=b+m2=(a+m1)+m2=a+(m1+m2),进而 a≤c。
任意两个自然数 a,b 都有序关系。
对于 a,b 两个自然数,当 b=0 时有 a=0+a=b+a 所以 a≤b。
当 b 为自然数时。若 a=b,则 suc(b)=a+suc(0),因此 a<suc(b);若 a<b,则 suc(b)=b+suc(0)=b+m+suc(0),因此 a<suc(b);若 a>b,则 a≥suc(b)。
由 Peano 公理 V 有任意两个自然数 a,b 都有序关系。
若 a≤b,则 a+c≤b+c。
由 a≤b 有 b=a+m,进而 b+c=(a+m)+c=a+m+c=(a+c)+m 因此 a+c≤b+c。
自然数的乘法也十分重要。
定义乘法的運算规则:
- 若 n 是自然数,则 0×n 的運算结果为 0,即 0×n=0;
- 若 n,m 都是自然数,则 suc(m)×n=m×n+n。
下面我们需要证明对于任意两个自然数,都可以进行乘法運算,也就是说,我们需要证明乘法结果的存在性和唯一性。
n 是任意自然数,记 pn(m) 表示 m×n 是否是自然数,即 m×n 是否存在。
n 是自然数,由乘法運算規則 I 有 0×n=0,进而有 0×n 是自然数; 即 pn(0) 得证。
n 和 m×n 是自然数,由加法结果的存在性有 m×n+n 存在; 根据乘法運算規則 II 有 suc(m)×n=m×n+n,进有 suc(m)×n 是自然数; 综上所述,若 m×n 是自然数,则 suc(m)×n 也是自然数; 即由 pn(m) 为真命题可以推出 pn(suc(m)) 为真命题。
由 pn(m) 的性质和 Peano 公理 V 有,对于任意自然数 m,pn(m) 成立,即 m×n 是自然数,再根据 n 的任意性,得出对于任意自然数 n,m,m×n 都是自然数。
n 是任意自然数,记 pn(m) 表示 m×n 是否唯一,即 m×n 的结果是否唯一。
n 是自然数,由乘法運算規則 I 有 0×n=0,进而 0×n 是唯一的,就是 0; 即 pn(0) 得证。
m 是自然数,m×n 是唯一的,由加法结果的唯一性有 m×n+n 唯一; 根据乘法運算規則 II 有 suc(m)×n=m×n+n,进有 suc(m)×n 唯一; 综上所述,若 m×n 唯一,则 suc(m)×n 也唯一; 即由 pn(m) 为真命题可以推出 pn(suc(m)) 为真命题。
由 pn(m) 的性质和 Peano 公理 V 有,对于任意自然数 m,pn(m) 成立,即 m×n 唯一,再根据 n 的任意性,得出对于任意自然数 n,m,m×n 都是唯一的。
在明确证明了自然数乘法運算的良好性质,即任意两个自然数都可以进行乘法運算,且乘法運算的结果存在且唯一之后,我们终于可以对自然数乘法的性质进行进一步的探索。
下面证明乘法交换律,即对于任意自然数 n,m,有 n×m=m×n。
直接证明比较困难,考虑从乘法運算的定义下手,即先证明乘法的两条運算规则符合交换律。
试证 0×n=0=n×0。
首先有 0×0=0=0×0。
进而当 n 是自然数且 0×n=0=n×0 时有
0×suc(n)=0=n×0=n×0+0=suc(n)×0
根据 Peano 公理 V,得知 0×n=0=n×0 对任意自然数 n 成立。
试证 m×suc(n)=m×n+m。
首先 m=0 时有
m×suc(n)=0×suc(n)=0=0×n=0×n+0=m×n+m
进而当 m 是自然数且 m×suc(n)=m×n+m 时有
suc(m)×suc(n)=m×suc(n)+suc(n)=m×n+m+suc(n)=m×n+suc(m)+n=m×n+n+suc(m)=suc(m)×n+suc(m)
根据 Peano 公理 V,得知 m×suc(n)=m×n+m 对任意自然数 n,m 成立,将其称为新的乘法運算規則 II。
证明了乘法運算規則的交换律之后,试证乘法交换律 n×m=m×n,首先当 n=0 时由乘法運算規則 I 有 0×m=m×0。
进而当 n 是自然数且 n×m=m×n 时,有
suc(n)×m=n×m+m=m×n+m=m×suc(n)
根据 Peano 公理 V,得知 n×m=m×n 对任意自然数 n,m 成立,即乘法交換律成立。
下面证明乘法分配律,即对于任意自然数 a,b,n,有 n×(a+b)=n×a+n×b。
首先当 n=0 时,n×(a+b)=0×(a+b)=0=0+0=0×a+0×b=n×a+n×b,进而当 n 为自然数且 n×(a+b)=n×a+n×b 时有
suc(n)×(a+b)=n×(a+b)+(a+b)=n×a+n×b+(a+b)=n×a+n×b+a+b=n×a+a+n×b+b=(n×a+a)+(n×b+b)=suc(n)×a+suc(n)×b
根据 Peano 公理 V,得知 n×(a+b)=n×a+n×b 对任意自然数 n,a,b 成立,即乘法分配律成立。
下面证明乘法结合律,即对于任意自然数 a,b,c,有 (a×b)×c=a×(b×c)。
首先当 c=0 时,有 (a×b)×c=(a×b)×0=0=a×0=a×(b×0)=a×(b×c)。
进而当 c 为自然数且 (a×b)×c=a×(b×c) 时有
(a×b)×suc(c)=(a×b)×c+a×b=a×(b×c)+a×b=a×(b×c+b)=a×(b×suc(c))
根据 Peano 公理 V,得知 (a×b)×c=a×(b×c) 对任意自然数 a,b,c 成立,即乘法结合律成立。
下面证明乘法消去律,即对于任意自然数 a,b 和 c,有 a×suc(c)=b×suc(c)⇔a=b。
试证 a=b⇒a×suc(c)=b×suc(c)。
首先当 c=0 时有
a×suc(c)=a×suc(0)=a×0+a=0+a=a=b=0+b=b×0+b=b×suc(0)=b×suc(c)
进而当 c 为自然数且 a×suc(c)=b×suc(c) 时有
a×suc(suc(c))=a×suc(c)+a=b×suc(c)+b=b×suc(suc(c))
即 a=b⇒a×suc(c)=b×suc(c)⇒a×suc(suc(c))=b×suc(suc(c)),根据 Peano 公理 V,得知 a=b⇒a×suc(c)=b×suc(c) 对任意自然数 a,b,c 成立。
试证 a×suc(c)=b×suc(c)⇒a=b,采用反证法,假设 a=b,则由加法運算規則 II 可知 a=b+m 或 b=a+m,其中 m=0,不妨设 a=b+m,m=0。
由 Peano 公理 III 有 suc(c)=0。
由 Peano 公理 III、IV 有,任意非零自然数 c 都有唯一的数 x 满足 suc(x)=c,不妨记作 pre(c)=x。
若有 a×suc(c)=b×suc(c),则有
a×suc(c)(b+m)×suc(c)=b×suc(c)=b×suc(c)=b×suc(c)+m×suc(c)=m×suc(c)=m×c+m=m×c+suc(pre(m))=suc(m×c+pre(m))
上述等式表明 0 是 m×c+pre(m) 的后继,这违背了 Peano 公理 III,由此知道假设不成立,即 a×suc(c)=b×suc(c)⇒a=b。
综上所述,乘法消去律 a×suc(c)=b×suc(c)⇔a=b,对任意自然数 a,b,c 成立。
通过上述步骤,我们成功地由 Peano 公理构建出了一个自然数代数系统。但 Peano 公理自身任有待研究。从上述步骤中我们看出 Peano 公理每一条公理都被使用过,少了任何一条都不足以构建出上述的自然数系统,这究竟是为什么呢?
下面我将阐述为什么每条公理都是必须的,通过举反例的方式。研究 Peano 公理自然不能从 Peano 公理系统内出发,我们将借助另一个公理系统——图论。
若 a≤b,则 a×suc(c)≤b×suc(c)。
由 a≤b 有 b=a+m,进而 b×suc(c)=(a+m)×suc(c)=a×suc(c)+m×suc(c) 因此 a×suc(c)≤b×suc(c)。
若 a×suc(c)≤b×suc(c),则 a≤b。
采用反证法,假设 a>b,则存在正自然数 m 满足 a=b+m,有
a×suc(c)=(b+m)×suc(c)=b×suc(c)+m×suc(c)
由此有 b×suc(c)≤a×suc(c),根据序的反对称性有 a×suc(c)=b×suc(c),根据乘法消去律有 a=b,这与 a>b 的假设矛盾,因此假设不成立,即证明了乘法消去的保序性。
自然数与有向图 rmG(rmV,rmE) 同构,这个图满足如下性质:
- 存在点 0,即 v0inrmV;
- 所有点的出度为 1,即 operatornameoutDeg(v)=1;
- 点 0 入度为 0,即 operatornameinDeg(v0)=0;
- 任意点的入度小于等于 1,即 operatornameinDeg(v)leq1;
- 存在从 0 到任意点的路径,即 existsoperatornamepath(0,v)。
下面我们试着通过删除公理的方法来寻找反例。
若去除,则允许不存在 0,可以构造出空集自然数系统。
若去除,则对点的出度无规定,可以构造出菊花图自然数系统。
若去除,则对 0 的入度无规定,可以构造出环状自然数系统。
若去除,则对一个数可以是多个数的后继,可以构造出 rho 状自然数系统。
若去除,则对连通性无要求,可以构造出分段状自然数系统。