2.1. 集合入门¶

数学意义上的集合概念在计算机科学中有广泛的应用。 集合论的记号与技巧常用于描述和实现算法， 因为与集合相关的抽象往往有助于澄清和简化算法设计。

一个 集合 是可区分的 成员 或 元素 的汇集。 成员通常取自某个更大的总体，称为 基类型 。 集合的每个成员要么是基类型的 本原元素 ，要么本身就是一个集合。 集合中没有重复的概念。 基类型中的每个值要么在集合中，要么不在集合中。 例如，一个名为 \(\mathbf{P}\) 的集合可能由 7、11 和 42 这三个 整数组成。 此时， \(\mathbf{P}\) 的成员是 7、11 和 42，基类型是整数。

下表列出常用于表示集合及其关系的符号。

下面是这些记号的一些使用示例。 首先定义两个集合 \(\mathbf{P}\) 和 \(\mathbf{Q}\) 。

\(|\mathbf{P}| = 3\) （因为 \(\mathbf{P}\) 有三个 成员），而 \(|\mathbf{Q}| = 2\) （因为 \(\mathbf{Q}\) 有两个成员）。 这两个集合的长度都是有限的。 其他集合可以是无限的，例如整数集合。

\(\mathbf{P}\) 与 \(\mathbf{Q}\) 的并集，写作 \(\mathbf{P} \cup \mathbf{Q}\) ，是出现在 \(\mathbf{P}\) 或 \(\mathbf{Q}\) 中的元素构成的集合， 即 {2, 3, 5, 10}。 \(\mathbf{P}\) 与 \(\mathbf{Q}\) 的交集， 写作 \(\mathbf{P} \cap \mathbf{Q}\) ，是同时出现在 \(\mathbf{P}\) 和 \(\mathbf{Q}\) 中的元素构成的集合，即 {5}。 \(\mathbf{P}\) 与 \(\mathbf{Q}\) 的差集， 写作 \(\mathbf{P} - \mathbf{Q}\) ， 是出现在 \(\mathbf{P}\) 中但不在 \(\mathbf{Q}\) 中的元素构成的集合，即 {2, 3}。 注意 \(\mathbf{P} \cup \mathbf{Q} = \mathbf{Q} \cup \mathbf{P}\) ， 以及 \(\mathbf{P} \cap \mathbf{Q} = \mathbf{Q} \cap \mathbf{P}\) ， 但一般而言 \(\mathbf{P} - \mathbf{Q} \neq \mathbf{Q} - \mathbf{P}\) 。 在本例中， \(\mathbf{Q} - \mathbf{P} = \{10\}\) 。 最后，集合 {5, 3, 2} 与集合 \(\mathbf{P}\) 无法区分，因为集合没有顺序的概念。 同样，集合 {2, 3, 2, 5} 也与 \(\mathbf{P}\) 无法区分，因为集合没有重复元素的概念。

两个集合的 集合积 或 笛卡尔积 \(\mathbf{Q} \times \mathbf{P}\) 是有序对的集合。 对我们的示例集合而言，集合积为

集合 \(\mathbf{S}\) 的 幂集 （记作 \(2^S\) ） 是 \(\mathbf{S}\) 的所有可能子集构成的集合。 考虑集合 \(\mathbf{S} = \{ a, b, c \}\) 。 \(\mathbf{S}\) 的幂集是

一个元素无序（像集合一样）但允许元素值重复的汇集称为 包 。 为了把包与集合区分开，我们用方括号 [] 把包的元素括起来。 例如，包 [3, 4, 5, 4] 不同于包 [3, 4, 5]， 而集合 {3, 4, 5, 4} 与集合 {3, 4, 5} 无法区分。 然而，包 [3, 4, 5, 4] 与包 [3, 4, 4, 5] 无法区分。

序列 是一种元素有序的汇集， 且可以包含值重复的元素。 序列有时也称为 元组 或 向量 。 在序列中，有第 0 个元素、第 1 个元素、第 2 个元素，依此类推。 我们用尖括号 \(\langle\rangle\) 把 序列的元素括起来。 例如， \(\langle3, 4, 5, 4\rangle\) 是一个序列。 注意序列 \(\langle3, 5, 4, 4\rangle\) 不同于 序列 \(\langle3, 4, 5, 4\rangle\) ，而且两者都不同于 序列 \(\langle3, 4, 5\rangle\) 。