2. 集合与关系¶
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}\) 的幂集是
一个元素无序（像集合一样）但允许元素值重复的汇集称为 包 [1]。 为了把包与集合区分开，我们用方括号 [] 把包的元素括起来。 例如，包 [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\) 。
2.1.1. 关系¶
集合 \(\mathbf{S}\) 上的一个 关系 \(R\) 是 取自 \(\mathbf{S}\) 的有序对的集合。 作为关系的一个例子，如果 \(\mathbf{S}\) 是 \(\{a, b, c\}\) ，则
是一个关系，而
是另一个不同的关系。 如果元组 \(\langle x, y\rangle\) 在关系 \(R\) 中，我们 可以使用中缀记号 \(xRy\) 。 我们经常使用诸如自然数上的小于运算符（ \(<\) ）这样的关系， 它包含诸如 \(\langle1, 3\rangle\) 和 \(\langle2, 23\rangle\) 这样的有序对，但不包含 \(\langle3, 2\rangle\) 或 \(\langle2, 2\rangle\) 。 我们通常不按有序对来写这种关系，而是对其使用中缀记号， 写作 \(1<3\) 。
定义关系的性质如下，其中 \(R\) 是 集合 \(\mathbf{S}\) 上的二元关系。
\(R\) 是 自反的 ，如果对所有的 \(a \in \mathbf{S}\) 都有 \(aRa\) 。
\(R\) 是 非自反的 ，如果对所有的 \(a \in \mathbf{S}\) ， \(aRa\) 都不成立。
\(R\) 是 对称的 ，如果对所有的 \(a, b \in \mathbf{S}\) ，只要 \(aRb\) 就有 \(bRa\) 。
\(R\) 是 反对称的 ，如果对所有的 \(a, b \in \mathbf{S}\) ，只要 \(aRb\) 且 \(bRa\) ，就有 \(a = b\) 。
\(R\) 是 传递的 ，如果对所有的 \(a, b, c \in \mathbf{S}\) ，只要 \(aRb\) 且 \(bRc\) ，就有 \(aRc\) 。
作为例子，对自然数而言， \(<\) 是 非自反的（因为 \(aRa\) 从不为真）、 反对称的（因为不存在 \(aRb\) 且 \(bRa\) 的情形）且传递的。 关系 \(\leq\) 是自反的、反对称的且传递的。 关系 \(=\) 是自反的、对称的（而且反对称！）、 且传递的。 对于人而言，"是……的兄弟"这一关系是对称的且 传递的。 如果我们把一个人定义为自身的兄弟，那么它是 自反的；如果我们把一个人定义为不是自身的兄弟，那么 它不是自反的。
2.2. 等价关系¶
如果 \(R\) 是自反的、对称的且传递的，那么它就是 集合 \(\mathbf{S}\) 上的一个 等价关系 。 等价关系可用于把集合划分成 等价类 。 如果两个元素 \(a\) 和 \(b\) 彼此等价， 我们写作 \(a \equiv b\) 。 集合 \(\mathbf{S}\) 的一个 划分 是一组 彼此 不相交 且并集为 \(\mathbf{S}\) 的子集。 集合 \(\mathbf{S}\) 上的一个 等价关系 把 该集合划分成元素彼此等价的互不相交子集。 UNION/FIND 算法能高效地 维护集合上的等价类。 这类 不相交集合 的一个应用是计算 最小代价生成树 。
2.3. 偏序¶
如果二元关系是反对称的且传递的，就称为 偏序 。 如果该关系是自反的，就称为 非严格偏序 。 如果该关系是 非自反的 ，就称为 严格偏序 。 定义偏序的集合称为 偏序集 或 偏序集 。 如果集合中的元素 \(x\) 和 \(y\) 满足 \(xRy\) 或 \(yRx\) ，则称它们在 给定关系 \(R\) 下是 可比的 。 如果偏序中每一对不同元素都是可比的， 则该序称为 全序 或 线性序 。
