集合和列表

8.3.3 数、集合和列表

数字可能是如何从微小的公理内核建立起一个大型理论的最生动实例。我们将在此描述关于自然数或者说非负整数的理论。我们需要一个谓词 NatNum，如果是自然数，则为真；我们还需要一个常数符号0，一个函数符号S（后继）。皮亚诺公理（Peano axiom）定义了自然数和加法[23]。自然数通过递归的方式定义：

NatNum(0)

也就是说，0是一个自然数，而且对于每个对象n，如果n是一个自然数，那么S(n)是一个自然数。因此，自然数是0、S(0)、S(S(0))等等。我们还需要一些公理来约束后继函数：

∀ n 0 ≠ S(n)

现在我们可以按照后继函数来定义加法：

以上的第一条公理表明，0加上任何自然数m得到m本身。注意二元函数符号“+”在项+(m, 0)中的用法；在普通数学中，该项应该用中辍表示法写成m+0。（我们在一阶逻辑中采用的表示法称为前缀。）为了使我们与数字有关的语句更易于阅读，我们将允许使用中辍表示法。我们也可以把S(n)写成n+1，因此第二条公理变成：此公理把加法简化为后继函数的反复应用。

中缀表示法的使用是句法便利的一个实例。句法便利就是标准语法的一个扩展或缩写，它不改变语句的语义。任何使用句法便利的语句可以“反便利”，生成普通一阶逻辑的一个等价语句。

一旦我们有了加法，就可以直接把乘法定义为反复的加法、求幂定义为反复的自乘、整数除法和余数、质数等等。因此，整个数论（包括密码学）可以从一个常数、一个函数、一个谓词和4条公理建立起来。

集合域对于数学以及常识推理也是基本的。（实际上，在集合论之上建立数论是可能的。）我们希望能够表示单个集合，包括空集。我们需要一种方法，它可以通过把元素添加到集合中或者对集合进行合并或求交集等操作来建立集合。我们希望知道一个元素是否属于某个集合，而且能够将集合与非集合的对象区分开。

我们将把集合论的标准词汇用作句法便利。空集是一个常量，用{}表示。一元谓词 Set 对于集合为真。二元谓词为x ∈ s（x是集合s的一个元素）和s1⊆ s2（集合s1是集合s2的子集，不一定是真子集）。二元函数为s1∩s2（两个集合的交）、s1∪s2（两个集合的并）和{x|s}（把元素x添加到集合s而产生的集合）。一个可能的公理集如下所示：

① 集合就是空集或通过将一些元素添加到一个集合而构成。

∀ s Set(s) ⇔ (s = { }) ∨ (∃x, s2Set(s2) ∧ s = {x|s2})

② 空集没有任何元素，也就是说，空集无法再分解为更小的集合和元素。

¬∃x, s {x|s} = { }

③ 将已经存在于集合中的元素添加到该集合，无任何变化。

∀ x, s x ∈ s ⇔ s = {x|s}

④ 集合的元素仅是那些被添加到集合中的元素。我们采用递归的方式来表示：x是集合s的元素，当且仅当s等价于包含元素y的集合s2，其中y与x相同或者x是s2的元素。

∀ x, s x ∈ s ⇔ [∃y, s2(s = {y|s2} ∧ (x = y ∨ x ∈ s2))]

⑤ 一个集合是另一个集合的子集，当且仅当第一个集合的所有元素都是第二个集合的元素。⑥ 两个集合是相同的，当且仅当它们互为子集。

∀ s1, s2s1= s2⇔ (s1⊆ s2∧ s2⊆ s1)

⑦ 一个对象是两个集合的交集的元素，当且仅当它同时是这两个集合的元素。

∀ x, s1, s2x ∈ (s1∩s2) ⇔ (x ∈ s1∧ x ∈ s2)

⑧ 一个对象是两个集合的并集的元素，当且仅当它是其中某一集合的元素。

∀ x, s1, s2x ∈ (s1∪s2) ⇔ (x ∈ s1∨ x ∈ s2)

列表与集合非常相似，它们的差别在于列表是有顺序的，而且同一个元素可以在一个列表中出现不止一次。我们可以在列表中采用Lisp语言的词汇：Nil是没有元素的列表常量；Cons、Append、First和Rest都是函数；Find是谓词，在列表中的功能与Member在集合中的类似。List？是一个只对列表为真的谓词。和集合一样，在涉及列表的逻辑语句中也经常使用句法便利。空列表用[ ]表示。项Cons(x, y)写成[x|y]，其中，y为非空列表。项Cons(x, Nil)（即只包含元素x的列表）用[x]表示。有多个元素的列表，诸如[A,B,C]相当于嵌套项Cons(A,Cons(B,Cons(C,Nil)))。习题8.14要求你写出列表的公理。