第5章
集合

集合 （set）是相互可区分的对象的汇集，这些对象被称为该集合的 成员 （member）。在第1章我们已经给出了集合的定义，本章将重温集合的概念。例如，一个集合可以由三个数字2、5和7构成，用花括号来表示。集合仅含有2、5和7，记为{2，5，7}。集合的成员本身也可以是一个集合。例如，集合{{2，5，7}}仅包含一个成员，这个成员就是集合{2，5，7}。前面提到的两个集合是不相同的，即

{2，5，7}≠{{2，5，7}}

第一个集合有三个成员，第二个集合有一个成员。它们与集合{{2}，{5}，{7}}又不相同，后者有三个成员，每个成员本身又是一个集合，即只包含一个成员的集合。

当我们说集合的成员是相互 可区分 （distinct）时，是指集合中没有重复的对象。例如，如果五名学生参加考试，获得的分数分别为83、90、90、100和100，那么这五名学生考试分数的集合就是{83，90，100} ；集合中成员之间的顺序无关，即集合{90，100，83}与集合{83，90，100}相等，因为它们具有相同的成员。

下面介绍一些常用的集合，它们有专门的名称：

ℤ={…，-3，-2，-1，0，1，2，3，…}=整数的集合

ℕ={0，1，2，3，…}=非负整数的集合，也是 自然数 （natural number）的集合

ℝ= 实数 （real number）的集合

ℚ= 有理数 （rational number）的集合

∅={}= 空集 （empty set），即不包含任何元素的集合

一个集合的 子集 （subset）是由该集合中抽取出来的元素（可以不是全部元素）构成的集合。例如，ℕ是ℤ的子集，ℤ是ℚ的子集，而空集∅是任意集合的子集。我们用 A ⊆ B 表示 A 是 B 的子集（ A 也可能等于 B ）。如果我们要定义 A 是 B 的一个子集但不等于 B 时，记作 。如果 ，则称 A 为 B 的 真子集 （propersubset）。（有时也用⊂表示，因为⊂既像 又像 ，会导致意义不清晰，所以近来的数学记法中避免使用。）

计算机科学家们将集合和数字（整数和实数）定义为基本 数据类型 （data type）。然而，从基础数学的观点来看，如果我们能够构造集合，就没有必要将数字视为基本数据类型，因为数字可以用集合来定义，计算机科学家们称之为编码技巧。一旦有更复杂的归纳定义和证明技术，我们便可以探讨这些编码了（见习题8.7）。

如果 A 是 B 的子集，则 B 称为 A 的 超集 (superset)。如果 A 是 B 的真子集，则 B 称为 A 的 真超集 (proper superset)。

前面说过，集合的成员也可以是集合。一个很重要的例子就是集合 A 的 幂集 （power set），我们用 P （ A ）来表示，它是 A 的所有子集的集合。例如，当 A ={3，17}时，有

P （ A ）={∅，{3}，{17}，{3，17}}

我们使用符号∈表示集合与成员的关系。例如， a ∈ S 表示 a 是集合 S 的成员，并且下述命题

2∈{2，5，7} 为真

而 3∈{2，5，7} 为假

类似地，有ℤ∈ P （ℚ），因为所有整数的集合是有理数集合的子集。符号∉表示给定的元素不在给定的集合中，例如，3∉{2，5，7}。空集是唯一没有元素的集合，即不存在 x ，使得 x ∈∅。

下列情况不能被混淆。

• 1和{1}：1是一个数字，而{1}是一个只包含一个对象的集合，即数字1。

• 0和∅：0是一个数字，而∅是一个特别的集合，即空集。{∅}是不同于前两者的第三种事物，即只包含一个元素的集合，其元素是空集∅。

• ∈和⊆：1∈{1，2}，因为1是{1，2}中的元素之一。但是，1⊆{1，2}不为真，1不是集合，因此就不能是子集。（计算机科学家们会说1⊆{1，2}是类型匹配错误，因为⊆两边的实体必须是集合。）此外，有{1}⊆{1，2}，并且 ，但是{1}∉{1，2}，因为{1，2}的元素不是集合而是数字 。

一个集合可以是 有限的 或 有穷的 （finite）也可以是 无限的 或 无穷的 （infinite）。如果它的成员数等于某个非负整数，那么它是有限的。例如，∅有0个成员，所以它是有限的；如果 A ={3，17}，那么 P （ A ）={∅，{3}，{17}，{3，17}}有4个成员，因此它也是有限的。计算 P （ A ）时，要记住它是一个集合的集合，而不是数字的集合，所以我们要计算它所包含的集合数，而不是这些集合中的数字数。

我们用| S |表示集合 S 的大小，称之为 S 的 基数 （cardinality）。因此，有|∅|=0。如果 A ={3，17}，那么| A |=2，| P （A）|=|{∅，{3}，{17}，{3，17}}|=4。

整数集合是无限的，所有偶数的集合{…,-4,-2,0,2,4,…}也是无限的。可以充分地说明，任意集合不是有限的就是无限的。对于两个无限集合来说，可以是相同大小的，也可以是不同大小的。例如，整数集合和偶数集合，它们是不相同的无限集合，却具有相同的大小。也存在大小不同的无限集合，例如，整数集合和实数集合。我们将在第6章再回到无限集合大小问题的讨论。

|{ℤ}|是什么？像 P （ A ）一样，这是一个由集合构成的集合，所以我们不在意内部集合的大小，即使它们是无限的。所以|{ℤ}|=1，因为{ℤ}只包含单个对象ℤ，而不考虑ℤ是否是一个无穷集。

有时我们需要更规范的方式表示“整数”或“有理数”。不像前面那样，以列出成员样例的方式来表示“偶数”的集合，我们使用下面的表示法 ^[1] ：

{ n ∈ ^ℤ ： n 是偶数}

或者等价地表示为

{ n ∈ ^ℤ ： n =2 m ， m ∈ ^ℤ }

又或者表示为

{2 m ： m ∈ ^ℤ }

一般来说， A 中满足谓词 P 的元素的集合表示为

{ x ∈ A : P ( x )}

对 P （ x ）的另一种解释是： x 具有性质 P 。

用现有的集合构建新的集合有多种方法。当有两个集合 A 和 B 时，我们可以得到它们的 并集 （union），即包含在 A 或 B 中的元素构成的集合，以及它们的交集（intersection），即既在 A 中又在 B 中的元素构成的集合。这些概念通常使用 文氏图 （Venn diagram）来说明，如图5.1~图5.3所示，图中展示了两个有重叠的集合 A 和 B ，以及它们的并集和交集。

A 和 B 的并集记为

A ∪ B ={ x : x ∈ A 或 x ∈ B }

A 和 B 的交集记为

A ∩ B ={ x : x ∈ A 且 x ∈ B }

像数字的加法和乘法一样，集合的“并”和“交”也具有 可结合 （associative）性，即

（ A ∪ B ）∪ C = A ∪（ B ∪ C ）

对于任意的集合 A 、 B 和 C ，同样地，有

（ A ∩ B ）∩ C = A ∩（ B ∩ C ）

我们将在第9章再回到这个主题，此刻只要注意到“或”和“且”在自然语言中是可结合的就足够了。例如，“你是17岁以上的女性，并且还是美国人”与“你是17岁以上，并且是女性美国人”是完全一样的。构造“17岁以上的人”、“女性”和“美国人”三个集合，通过“先对前两个集合取交集，然后再与第三个集合取交集”和“先对后两个集合取交集，然后再与第一个集合取交集”，两种方式都可以获得三个集合的交集。类似地，集合的并和交的运算都是可 交换的 （commutative），即对于任意的集合 A 和 B ，有 A ∪ B = B ∪ A 和 A ∩ B = B ∩ A 成立。

我们还可以求集合的 补集 （complement），表示为 。全集 U （universe）可以是任何可能事物 x 的集合， x 没有确切的定义，它的意义是由上下文决定的，但是意义并不模糊。如果 B ={ x ∈ U ： P （ x ）}，那么我们可以得到 。例如，如果 B ={星期六，星期天}，那么假设“星期三” 是没有问题的，但“一月” 可以吗？这完全取决于 U 是“星期几的集合”，还是“自然语言中所有单词的集合”，或者其他的集合含义。

当我们有了补集的概念，便可以做 A 和 B 的 差 （difference），即在 A 中而不在 B 中的元素，表示为：

图5.3展示了图5.1中的集合 A 和 B 的 A - B 和 B-A 。这两个表达式意义完全不同，在示例中，两者都不为空。一般来说，有

A ∪ B =（ A - B ）∪（ B - A ）∪（ A ∩ B ）

也就是说， A ∪ B 是两个集合之差（两边的部分）的并集，再与集合交集（中间“缺失部分”）的并。

集合差 A - B 有时也表示为 A \ B 。

集合的并和交运算满足分配律，类似于算术运算中加法和乘法的分配律，即 a ·( b + c )= a · b + a · c 。这里有一个重要的区别：集合的并和交运算的分配律是对称的。

定理5.1 分配律。

A ∩（ B ∪ C ）=（ A ∩ B ）∪（ A ∩ C ）

A ∪（ B ∩ C ）=（ A ∪ B ）∩（ A ∪ C ）

我们只证明第一个等式，第二个等式留作习题5.2。

证明 ：考虑任意元素 x ，首先假设 x ∈ A ∩( B ∪ C )。

根据∩和∪的定义，可以得到：

（a） x 是集合 A 的成员。

（b）（b1） x 是集合 B 的成员。

（b2） x 是集合 C 的成员。

当（b1）为真时， x 是 A 和 B 的成员；当（b2）为真时， x 是 A 和 C 的成员，即 x ∈（ A ∩ B ）∪（ A ∩ C ）。

现在假设 x ∈（ A ∩ B ）∪（ A ∩ C ）。我们可以按照上述相同的推理过程反向推理。无论 x ∈（ A ∩ B ）还是 x ∈（ A ∩ C ）， x 都是 A 的成员，并且也必须是 B 或 C 的成员，即 x ∈ A ∩（ B ∪ C ）。■

上述论证过程在集合及其∪、∩运算的规律与命题及其连接词“或”和“且”的推理之间交替进行。形式化“复合命题的真值取决于组成该命题的原子命题的真值”的推理过程是 命题演算 的主要内容，也是第9章的主题。事实上，集合运算具有与命题逻辑中同样的结合律、交换律和分配律（见第9章）。

并和交运算的符号∪和∩如同扩展和与扩展积的符号Σ和Π一样。例如，ℕ是所有具有一个元素的集合{ n }的并集，即对于任意的 n ∈ℕ，ℕ可以表示为

集合 S 是全集 U （除了不在 S 中的单个元素之外的所有事物）的所有子集的交集，则 S 表示为

有序对 （ordered pair）〈 x , y 〉是一种数学结构，它将 元素 （component） x 、 y 组合成一个顺序结构。也就是说，〈 x , y 〉不同于〈 y , x 〉，除非 x 与 y 相同。总之，只有在 x = z 和 y = w 的情况下，才有〈 x , y 〉=〈 z , w 〉。

〈 x , y 〉也不同于{ x , y }（{ x , y }与{ y , x }是相同的）。我们将把有序对〈 x , y 〉视为不同于集合的另一种基本数据类型。

事实上，可以用集合来定义有序对，如同可以用集合来定义数字一样。数学的纯粹主义者和基本教义派有时会将有序对〈 x , y 〉定义为{ x ,{ x , y }}，他们认为，基本概念尽可能地少是很重要的。根据这种定义，有序对具有如下基本性质，即两个有序对是相等的当且仅当它们中的第一、第二个元素分别对应相等（见习题5.11）。

有序对的概念可以扩展到有序三元组。我们用〈 x , y , z 〉表示由三个元素 x 、 y 和 z 构成的有序三元组。一般地，我们统称为 有序 n 元组 （ordered n-tuple），其中 n 是非负整数，表示有 n 个元素的序列。两个有序 n 元组是相等的，当且仅当对于每个 i ，它们的第 i 个元素都是相等的，1≤ i ≤ n 。

由第一元素来自集合 A 和第二元素来自集合 B 的所有有序对构成的集合称为 A 和 B 的 笛卡儿积 （Cartesian product）或 叉积 （cross product），表示为 A × B 。例如，如果 A ={1,2,3}， B ={-1,-2}，则

A × B ={〈1,-1〉,〈1,-2〉,〈2,-1〉,〈2,-2〉,〈3,-1〉,〈3,-2〉}

很明显， A × B 通常不同于 B × A 。如果 A 和 B 都是有穷集，那么有| A × B |=| A |·| B |。在上面的例子中，有| A |=3、| B |=2，且| A × B |=6。我们也可以构造无穷集的笛卡儿积，如ℕ×ℤ是所有整数的有序对集合，其中第一个元素是非负的整数，有

{1，2，3}×{-1，-2}⊆ ^ℕ ×ℤ

本章小结

• 集合 是 可区分 的事物或 元素 的无序汇集。集合的元素称为 成员 。

• 空集 是不包含任何对象的集合，表示为∅或者{}。

• 某些数字的集合有特定的名称，如整数ℤ、自然数ℕ、实数ℝ和有理数ℚ。

• 集合的 子集 是由集合的某些成员（可能一个也没有或者也可能包括全部）组成的集合。

• A ⊆ B 表示 A 是 B 的子集（ A 也可能等于 B ）。 A B 表示 A 是 B 的 真 子集（绝对不等于 B ）。

• 如果 A 是 B 的（真）子集，那么 B 是 A 的（真）超集。

• 符号∈表示集合成员，它的否定用符号∉表示。

• 一个集合本身可以成为另一个集合中的元素。区分一个对象是元素还是集合是很重要的。成员符号用于表明元素与集合的关系，而子集符号用于表明两个集合之间的关系，即一个集合的所有元素都是另一个集合的成员。

• 集合 S 的 幂集 表示为 P ( S )，是 S 的所有子集的集合。

• 集合 S 的大小也称为 S 的基数，表示为| S |。大小是非负整数的集合为有穷集，否则为无穷集。

• 集合 S 的补集表示为 ，是有关的 全集 中不在中的所有元素的集合。

• 可以通过求集合的并（∪）、交（∩）以及差（-或者\）得到新的集合。

• 集合的并和交的运算满足结合律、交换律和分配定律：

• 有序对 由两个元素按顺序构成。以 x 为第一元素、以 y 为第二元素的有序对表示为〈 x , y 〉。 有序 n 元组 是该定义对于 n 个元素的扩展。

• 由第一元素来自集合 A 、第二元素来自集合 B 的所有有序对构成的集合称为 A 和 B 的 笛卡儿积 或 叉积 ，表示为 A × B 。

习题

5.1 下面是什么集合？列出它们的成员。

（a）{{2,4,6}∪{6,4}}∩{4,6,8}

（b） P （{7,8,9}）- P （{7,9}）

（c） P （∅）

（d）{1，3，5}×{∅}

（e）{2，4，6}×{∅}

（f） P （{0}）× P （{1}）

（g） P （ P （{2}））

5.2 证明分配定律的第二个等式：

A ∪（ B ∩ C ）=（ A ∪ B ）∩（ A ∪ C ）

5.3 证明：如果 A 是有穷集，并且| A |= n ，那么有| P ( A )|=2 ^{| A |} 。

5.4 如果| A |= n ，那么| P ( A )-{{ x }: x ∈ A }|是什么？

5.5 （a）假设 A 和 B 都是有穷集。比较| P （ A × B ）|与| P （ A ）|·| P （ B ）|的数量关系。在什么情况下，其中一个会比另一个大，它们的比是多少？

（b）（ A - B ）∩（ B - A ）=∅ 一定为真吗？证明或者给出反例。

5.6 用形式化集合表示法表示下列集合。

（a）无理数集合。

（b）能被3或5整除的所有整数的集合。

（c）集合 X 的幂集。

（d）三位数的集合。

5.7 确定下述命题的真假，并说明原因。

（a）∅={∅}

（b）∅={0}

（c）|∅|=0

（d）| P |（∅）=0

（e）∅ ∈{}

（f）∅={ x ∈ ^ℕ ： x ≤0并且 x ＞0}

5.8 证明：如果 A 、 B 、 C 、 D 都是有穷集，并且有 A ⊆ B 和 C ⊆ D ，那么 A × C ⊆ B × D 。

5.9 证明下列各式：

（a） A ∩（ A ∪ B ）= A

（b） A -（ B ∩ C ）=（ A - B ）∪（ A - C ）

5.10 有100名学生和三门课程，每名学生至少需要注册一门课程。在这些学生中，有60人注册了化学课，有45人注册了物理课，有30人注册了生物课。有些学生注册了两门课程，有10名学生注册了三门课程。

（a）有多少学生刚好注册了两门课程？

（b）有9名学生同时注册了化学和物理（没有注册生物），有4名学生同时注册了物理和生物（没有注册化学）。有多少人同时注册了化学和生物（没有注册物理）？

5.11 假设有序对不作为基础数据类型，将〈 x , y 〉定义为{ x ,{ x , y }}。证明：〈 x , y 〉=〈 u , v 〉当且仅当 x = u 和 y = v 。

---

[1] 在数学记法中，竖线|通常用于代替冒号“：”，例如 我们更喜欢用冒号，因为竖线还用于表示集合的大小。 zmWy5f+wRwx45DfB5oC0lRL4HD6QsnmkFfw5nExujssE0+3MoKaEP/ZbC6ZtaSOJ