皮亚诺公理¶
皮亚诺公理(文字说明)
- PA1: 1是自然数。
- PA2: 对于任意自然数 n,其后继数 n' 都是自然数。
- PA3:对于任意自然数 n,n'\not=1都成立。
- PA4:对于任意自然数 m,n,若m'=n',则 m=n。
- PA5:假设对自然数 n 的谓词 P(n) 而言,下面的(a)和(b)都成立。
(a) P(1)
(b) 对于任意自然数 k,P(k)成立,则P(k')成立。
此时,对于任意自然数 n,P(n)都成立。
皮亚诺公理(逻辑公式)
- PA1: 1\in\mathbb{N}
- PA2: \forall n\in\mathbb{N}[n'\in\mathbb{N}]
- PA3:\forall n\in\mathbb{N}[n'\not=1]
- PA4:\forall m,n\in\mathbb{N} [m'=n'\Rightarrow m=n]
- PA5:(P(1)\wedge \forall k\in\mathbb{N}[P(k)\Rightarrow P(k')])\Rightarrow \forall n\in\mathbb{N} [P(n)]
皮亚诺公理定义了自然数。更深层次地,皮亚诺公理定义了一种数学结构,这种数学结构由无数个元素组成,无数个元素排列成一条序列的形状,每个元素后面都有且只有一个元素。在计算机科学中,这样的结构常常称为链表,更具体地,是单向无穷链表。单向指只有前一项指向后一项,没有后一项指向前一项。无穷指这个链表只有头,没有尾,包含无穷项。
皮亚诺公理通过5条性质,定义出了自然数这一数学基本结构。下面我们分别分析一下这5条性质。
PA1¶
PA1: 1\in\mathbb{N}
PA1明确了自然数集合 \mathbb{N}包含 1 这个元素,粉碎了 \mathbb{N} 是空集的可能。
PA2¶
PA2: \forall n\in\mathbb{N}[n'\in\mathbb{N}]
PA2使用了后继的概念,称 n' 是 n 的后继。后继只作用于一个元素上,这是与加法的本质不同。加法作用与两个元素上,如 a+b,是将加法作用在 a 和 b 上。这里使用后继而没有使用加法,原因是后继更本质。倘若从加法定义,如\forall a,b\in\mathbb{N}[a+b\in\mathbb{N}],那么就暗含了 a 和 b 之间有某种关系,它们一起可以产生另一个自然数。这对于自然数是没有必要的,每个自然数可以只由另一个自然数产生。另一方面,若 a,b,c,d\in\mathbb{N},e=a+b,f=c+d,判断 e 和 f 是否相同也是一件麻烦事。所以PA2选择了后继这个操作来产生新的自然数。
PA3¶
PA3: \forall n\in\mathbb{N}[n'\not=1]
PA3回答了为什么后继操作能产生新的自然数。目前 1\in\mathbb{N},根据PA3有 1'\not=1,即 1'和 1 不同。根据PA2,有1'\in\mathbb{N}。这样 \mathbb{N}中有了两个元素。那么 1'' 和 1' 是否相同呢?这是PA4需要回答的问题。
另外,PA3说明了 1前面没有自然数。从而 1可以看成是构造自然数的一个起点。那么还有没有其他起点?同样PA4回答了这个问题。
PA4¶
PA4: \forall m,n\in\mathbb{N} [m'=n'\Rightarrow m=n]
假设 1''=1',则根据PA4有1'=1,与PA3矛盾。故1''\not=1'。
实际上,我们可以得到 \underbrace{1^{'\cdots'}}_{m个'}\not=\underbrace{1^{'\cdots'}}_{n个'},若 m\not=n。
更为重要的,PA4明确了各个元素组成链的结构,而没有环和交叉。如 a,b,c,d\in\mathbb{N},且互不相同,则不可能 a\rightarrow b\rightarrow\cdots\rightarrow a,也不可能 a\rightarrow b\rightarrow d,c\rightarrow d等等。这样我们就知道只有 1一个起点。
注意PA4只说明了 m'=n'\Rightarrow m=n,而没有说 m'=n'\Leftarrow m=n。主要原因是后者没有必要成立。
PA5¶
PA5: (P(1)\wedge \forall k\in\mathbb{N}[P(k)\Rightarrow P(k')])\Rightarrow \forall n\in\mathbb{N} [P(n)]
PA5是数学归纳法。最耐人寻味的是,皮亚诺公理将数学归纳法包含进来,意思是数学归纳法作为一个公理不需要怀疑,同时也暗示着数学归纳法和自然数的本质有关。