跳至内容
Topos Uranos
中文 (中国)

自然数的基本运算与序关系

摘要

本课从皮亚诺公理中的后继出发，借助递归定理来定义自然数的加法、乘法和乘方；递归定理保证递归定义确定唯一的运算。本课承认其中关于存在性的部分，用归纳法证明关于唯一性的部分，并推出这些运算的性质：交换律、结合律、分配律和消去律。随后用加法定义序关系，给出它的三歧性、传递性和单调性，并定义逆运算，即减法和除法，以及它们存在的条件。数学归纳原理是所有证明的工具。

学习目标

  1. 叙述递归定理，并用它写出自然数加法、乘法和乘方的递归定义。
  2. 从运算的定义出发，用归纳法证明运算的性质。
  3. 用加法定义自然数的序，并应用它的三歧性、传递性和单调性。
  4. 判断两个自然数的减法和除法何时可以进行，并在不离开自然数的前提下用它们进行运算。

加法

自然数的运算从中学起就为人熟知；这里要做的是以数学的精确性为它们奠定基础。在关于皮亚诺公理的课中，自然数是从 11 和后继运算出发定义的，后继运算给每个自然数 nn 指定紧随其后的数 S(n)S(n)。加法由后继出发，通过两条规则来定义：加 11 就是取后继；加上 mm 的后继，就是取与 mm 之和的后继。

n+1=S(n),n+S(m)=S(n+m)n + 1 = S(n), \qquad n + S(m) = S(n + m)

这类定义称为递归的：第一条规则确定在 11 处的值，第二条规则把每种情形归结为前一种情形。然而，说两条这样的规则确实定义了一种运算，其中包含两个不同的断言：存在一个函数对所有自然数满足这两条规则（存在性），并且不存在两个不同的函数都满足它们（唯一性）。两者合起来构成递归定理，它归功于戴德金：本课程承认存在性的部分（理由在方框之后说明），并证明唯一性的部分。定理以一般的形式叙述，以便也适用于乘法、乘方以及后续各课中的递归定义。

不加证明的事实（递归定理）。设 XX 是一个集合，cc 是 XX 的一个元素，并设对每个自然数 nn 给定一条规则 gng_n，它把 XX 的每个元素对应到 XX 的另一个元素。那么存在一个函数 ff（从 N\mathbb{N} 到 XX），使得 f(1)=cf(1) = c 且 f(S(n))=gn(f(n))f(S(n)) = g_n(f(n)) 对任意自然数 nn 成立，并且这个函数是唯一的。

存在性在本课程中不加证明地承认。它的证明需要把函数 ff 构造成一个由序对组成的集合：即包含 (1,c)(1, c)、并且对每个序对 (n,x)(n, x) 都包含 (S(n),gn(x))(S(n), g_n(x)) 的最小序对集合；然后再用归纳法验证，每个自然数在其中对应唯一的第二个元素。这一构造属于集合论，对后面的算术没有任何帮助。相反，唯一性是皮亚诺第五条公理的直接推论。

引理递归定义的函数的唯一性

若两个函数 ff 和 hh（从 N\mathbb{N} 到 XX）都满足递归定理的两个条件，则它们相等。图中画出了两者在最初几个自然数上的值。

证明

  1. A={n∈N:f(n)=h(n)}\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}

    设 AA 是两个函数取值相同的自然数组成的集合。只需证明 AA 是全体自然数的集合。

  2. f(1)=c=h(1)f(1) = \resaltar{c} = h(1)

    11 属于 AA，因为两个函数的值都是 cc（在 11 处）。

  3. f(S(k))=gk(f(k))=gk(h(k))=h(S(k))f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))

    若 kk 属于 AA，则 S(k)S(k) 也属于它：两个函数对同一个值应用同一条规则 gkg_k。

  4. A=N,(∀n∈N) (f(n)=h(n))A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))

    由皮亚诺第五条公理，AA 是全体自然数的集合：两个函数相等。

固定第一个加数 nn，取 X=NX = \mathbb{N}、c=S(n)c = S(n)，并对任意 mm 取规则 gmg_m（它把每个自然数对应到其后继），就从定理得到加法：定理给出的函数 ff 正是把每个 mm 对应到数 n+mn + m 的函数，而加法的两条规则正是定理的两个条件。同样，取 c=nc = n 和加上 nn 的规则，就得到乘法；取 c=bc = b 和乘以 bb 的规则，就得到乘方。总之，加上 mm 就相当于应用后继 mm 次。

例题二加二等于四

算术中最著名的命题是一个定理，它用加法的两条规则和名称 2=S(1)2 = S(1)、3=S(2)3 = S(2) 与 4=S(3)4 = S(3) 来证明。

证明

  1. 2+2=2+S(1)2 + 2 = 2 + S(1)

    把第二个加数写成 11 的后继。

  2. 2+S(1)=S(2+1)2 + S(1) = S(2 + 1)

    由第二条规则，加上一个后继就是取和的后继。

  3. S(2+1)=S(S(2))S(2 + 1) = S(S(2))

    由第一条规则，加 11 就是取后继。

  4. S(S(2))=S(3)=4S(S(2)) = S(3) = 4

    由于 S(2)=3S(2) = 3 且 S(3)=4S(3) = 4，得到结果。

由加法的规则可以用归纳法推出它的性质。对所有自然数 aa、bb 和 cc：

  1. 交换律：a+b=b+aa + b = b + a。
  2. 结合律：(a+b)+c=a+(b+c)(a + b) + c = a + (b + c)。因此可以不加括号地写成 a+b+ca + b + c。
  3. 消去律：若 a+c=b+ca + c = b + c，则 a=ba = b。

交换律已在关于皮亚诺公理的课的例题 5 中证明，结合律是那里的一道练习题。消去律在本课的例题 1 中证明。