跳转至

序理论

引入

注释

二元关系（Binary Relation）在数学中用于描述常见的关系概念：当且仅当对于 \((x, y)\) 属于定义二元关系的有序对集，元素 \(x\) 与元素 \(y\) 相关。也就是说，集合 \(X\) 和 \(Y\) 上的二元关系是笛卡尔积 \(X \times Y\)，由 \(x \in X\) 和 \(y \in Y\) 组成的有序对 \((x, y)\) 组成。

序理论是研究二元关系的一个数学分支。

为什么需要序理论？

在数学，计算机科学和相关知识领域中，次序无处不在。例如我们在入门数学课中学到的自然数之间的比较：「1 小于 2」，「100 大于 99」，「小明有 3 个苹果，小红有 12 个苹果。小红把自己的一半苹果分给小明，现在谁有更多的苹果？」。或者将这个概念扩展到其他数学集合的排序，比如整数和实数。实际上，大于或小于另一个数的概念是数学系统的基本直觉。很多时候我们并不知道两个数间的实际差，只有它们之间的次序。

上述类型的次序有特殊性质：每个元素都可以用于和另一个元素直接「比较」，也就是说，这个元素大于、小于、或等于另一个元素。但是，这不总是我们想要的结果。一个常见的例子是集合的子集排序。如果一个集合 \(A\) 包含集合 \(B\) 的所有元素，那么集合 \(B\) 被称为小于等于 \(A\)。然而有些集合不能用这种方式来比较，因为其中每个集合都包含着其他集合中不存在的某些元素。例如，考虑一个系列集合的子集次序：尽管鸟类集合和狗的集合都是动物集合的子集，但鸟类和狗都不构成另一个的子集。所以，子集包含是偏次序，对立了前面给出的全次序。

更宽泛地讲，次序的概念非常普遍，远远超出了对序列或相对数量这些具有直观结论的描述。在特定情况下，次序可以用来描述专业化的概念。因为抽象地来看，这种类型的次序相当于子集关系。例如，「儿科医生是医生」，「圆是一种特殊的椭圆」。

序理论捕捉了在一般环境中从这些例子中产生的次序直觉。这是通过指定必须是数学顺序关系的 \(\leq\) 属性来实现的。这种更抽象的方法很有意义，因为人们可以在一般环境中无需关注任何特定顺序的细节，就推导出许多定理。而这些方法可以很容易地转移到许多不太抽象的应用中。

在次序广泛应用的推动下，许多特殊类型的有序集有了定义，其中一些甚至已经发展成为了自己的数学领域。此外，序理论并不局限于各类序关系，而是考虑了它们之间的函数。函数的序理论的性质的一个简单例子来自在数学分析中常见的单调函数。

定义

本节以集合论、算术和二元关系的概念为基础介绍有序集合。

偏序集合

次序是特别的二元关系。设 \(P\) 为一个集合，而 \(\leq\) 是在 \(P\) 的关系，那么 \(\leq\) 是个偏序当他是自反的，反对称的，且递移的，则，对于所有 \(a,b\) 和 \(c\) 于 \(P\)，皆能满足：

  • \(a\leq a\)（自反的）
  • 如果 \(a\leq b\) 且 \(b\leq a\)，那么 \(a=b\)（反对称性）
  • 如果 \(a\leq b\) 且 \(b\leq c\)，那么 \(a\leq c\)（递移性）

一个偏序性质的集合称为 偏序集合、poset 或是 有序集合。通过这些性质，我们可以得出在自然数、整数、有理数、以及实数中皆有明确的序关系。当然，它们还有额外的性质成为 全序，即在 \(P\) 中对于每一个 \(a\) 和 \(b\) 皆能满足：

  • \(a\leq b\) 或 \(b\leq a\)（全序性）
注释

全序关系（Total order/Linear order）在数学中指集合 \(X\) 上反对称的、传递的和完全的二元关系（一般称其为 \(\leq\)）。

满足全序关系的集合叫做 全序集合、线性序集合、简单序集合 或 链。当许多典型序为线性，集合内的有序子集合会发生不满足此性质的例子。另一个例子为给定一个整除性关系 \(|\)。对于两个数 \(m\) 和 \(n\)，当 \(m\) 除以 \(n\) 未留余数时，我们书写为 \(n|m\)，这显然是一个偏序关系。偏序集的许多高级属性主要和偏序相关。

次序中的特殊元素

偏序集合中可能有一些特殊的元素。最基本的例子是由偏序集的 最小元素（Least element）。例如，\(1\) 是正整数中的最小元素，空集是子集顺序下的最小集合。形式上，如果满足以下条件，元素 \(m\) 是最小元素：

对于阶的所有元素 \(a\)，\(m \leq a\)。

符号 \(0\) 经常用于最小元素，即使不涉及数字也是如此。但是，在一组数字的顺序中，这种表示法可能有时不够准确，因为数字 \(0\) 并不总是最小的。上面的除法顺序给出了一个例子，其中 \(1\) 是最小元素，因为它可以整除所有其他数字。相反，\(0\) 是除以所有其他数字的数字。因此，它是次序中的 最大元素（Greatest element）。最小和最大元素的其他常用术语是 底部（bottom），顶部（top），零（zero）和 单位（unit）。

最小元素和最大元素可能不存在，如实数示例所示。但如果它们存在，它们总是独一无二的。相反，考虑整除关系 \(|\) 在集合 \(\{2,3,4,5,6\}\) 上。这个集合既没有顶部也没有底部，元素 \(2\)、\(3\) 和 \(5\) 以下没有元素，而 \(4\)、\(5\) 和 \(6\) 以上没有元素。这些元素分别称为 极小（minimal）和 极大（maximal）。形式上，如果满足以下条件，则元素 \(m\) 是极小的：

\(a \leq m\) 意味着对于阶的所有元素 \(a\)，\(a = m\)。

将 \(\leq\) 与 \(\geq\) 交换产生 极大值（maximality）的定义。如示例所示，可以有许多最大元素，并且某些元素可能既是极小又是极大（例如示例中的 \(5\)）。但是，如果存在极小元素，则它是该顺序中唯一的极小元素。同样，在无限偏序集中，极大元素并不总是存在：给定无限集的所有有限子集的集合，按子集包含排序，就是许多反例之一。确保在特定条件下极大元素存在的一个重要方法是 佐恩引理（Zorn's Lemma）。

注释

佐恩引理（Zorn's Lemma）也被称为库拉托夫斯基 - 佐恩（Kuratowski-Zorn）引理，是集合论中一个重要的定理。它的定义为：在任何一非空的偏序集中，若任何链都有上界，则此偏序集内必然存在（至少一个）极大元素。

偏序集的子集可以继承次序。我们已经通过考虑具有诱导整除排序的自然数的子集 \(\{2,3,4,5,6\}\) 来应用这一点。现在还有一个偏序集的元素对于顺序的某些子集是特殊的。这构成了 上限（upper bound）的定义。给定某个偏序集 \(P\) 的子集 \(S\)，\(S\) 的上界是 \(P\) 的元素 \(b\)，它高于 \(S\) 的所有元素。形式上，这意味着：

对于 \(S\) 中的所有 \(s\)，\(s \leq b\)。

下限同样由通过反转顺序定义。例如，\(-5\) 是一个整数子集的自然数的下限。给定一组集合，这些集合在子集排序下的上限由它们的并集给出。事实上，这个上限非常特殊：它是包含所有集合的最小集合。因此，我们找到了一组集合的 最小上限（least upper bound）。这个概念也被称为 supremum 或 join。集合 \(S\) 的最小上限写为 \(\sup(S)\) 或 \(\bigvee S\)。相反，最大下限（greatest lower bound）被称为 infimum 或 meet 并表示为 \(\inf(S)\) 或 \(\bigwedge S\)。这些概念在序理论的许多应用中发挥着重要作用。两个元素 \(x\) 和 \(y\) 分别对应 \(\sup(\{x,y\})\) 和 \(\inf(\{x, y\})\)。

例如，\(1\) 是作为整数子集的正整数下限。或者，我们再次考虑关于自然数的关系 \(|\)。两个数的最小上限是被两者相除的最小数，即这些数的最小公倍数（least common multiple of the number）。最大的下限依次由最大公约数（greatest common divisor）给出。

二元性

在前面的定义中，我们注意到一个概念可以通过颠倒以前定义中的次序来定义。「最小」和「最大」、「极小」和「极大」、「上限」和「下限」等等都是这种情况。这是序理论中的一般情况：给定的次序可以通过仅交换其方向来反转，以图形方式自上而下地翻转哈斯图（Hasse diagram）。这就产生了所谓的 对偶（dual）、逆（inverse）或 相反顺序（opposite order）。

每个序理论定义都是二元的：它是通过将定义应用于逆阶而获得的概念。由于所有概念都是对称的，因此该操作保留了偏序定理。对于给定的数学结果，只需颠倒顺序并用它们的对偶替换所有定义，即可获得另一个有效定理。

构建新次序

通过给定次序构造新次序有很多方法。二元/对偶次序就是一个例子。另一个重要的构造是两个部分有序集的笛卡尔积（cartesian product），连同元素对的积顺序（product order）。排序由 \((a, x) \leq (b, y)\) 当（且仅当）\(a \leq b\) 且 \(x \leq y\) 定义（注意这个定义中关系符号 \(\leq\) 有三个不同含义）。两个偏序集的不交并（disjoint union）是阶构造的另一个典型例子，其中阶只是原始阶的（不相交）并集。

通过定义当 \(a \leq b\) 而不是 \(b \leq a\) 时 \(a < b\)，每个偏序 \(\leq\) 都会产生所谓的严格次序 \(<\)。如果 \(a < b\) 或 \(a = b\)，则可以通过设置 \(a \leq b\) 来转换。这两个概念是等价的。

相关领域和应用

尽管大多数数学领域通过自定的方法使用次序，但也有一些理论的关系远远超出了应用范围。以下我们会着重介绍他们和序理论的关联。

通用代数

和之前提到的一样，通用代数的方法和形式是许多序理论的重要工具。除了根据满足某些定义的代数结构形式化次序外，还可以建立与代数的其他联系。布尔代数和布尔环之间的对应关系就是一个例子。其他问题与自由结构的存在有关，例如基于一个给定生成器集的自由格（free lattices）。此外，闭包算子（closure operator）的研究在通用代数中也很重要。

拓扑

在拓扑学中，次序起着非常重要的作用。事实上，开集的集合提供了一个完整格的例子，或者准确地说是一个完整的 Heyting 代数（或「框架」（frame）/「区域」（locale））。滤子和网是与序理论密切相关的概念，集合的闭包算子可用于定义拓扑。除了这些以外，拓扑也可以仅从开集格的角度来看待。此外，拓扑底层集合的元素的自然 git s 预序由所谓的特化顺序给出，如果拓扑是 \(T_{0}\)，这实际上是偏序。

范畴论

使用哈斯图的次序可视化有一个简单的概括：不是在较大的元素下方显示较小的元素，次序的方向也可以通过向图的边缘给出方向来描述。这样，每个序就可以被看作是一个有向无环图，其中节点是偏序集的元素，并且当且仅当 \(a \leq b\) 时存在从 \(a\) 到 \(b\) 的有向路径。去掉非循环的要求，还可以获得所有的预序（preorder）。

算法

C++ 基础库的排序函数 中有偏序关系的应用。很多情况时，我们需要在 C++ 中自定义比较器（custom comparator），而 STL 自定义比较器的要求就是它必须为 严格弱序 的（Strict Weak Ordering）。严格弱序定义为部分有序集合，其中不可比性是传递关系。设比较器为 \(f\)，\(f(x,y)\) 为真表示 \(x<y\)，则有：

  • \(f(x,x)\) 必须为假。（非自反性）

  • 如果 \(f(x,y)\) 为真，则 \(f(y,x)\) 必须为假。（非对称性）

  • 如果 \(f(x,y)\) 为真且 \(f(y,z)\) 为真，则 \(f(x,z)\) 必须为真。（传递性）

  • 如果 \(f(x,y)\) 为假，\(f(y,x)\) 为假，\(f(y,z)\) 为假且 \(f(z,y)\) 为假，则 \(f(x,z)\) 为假 且 \(f(z,x)\) 为假。（不可比性的传递性）

其中反对称性可以由非自反性和传递性推导得到。而所有 STL 中的自定义比较器都可以用简单的 \(<\) 关系表示。因为我们可以推断得知：

  • \(x>y\) 表示 \(y<x\);
  • \(x \leq y\) 表示 \(y \nless x\)；
  • \(x \geq y\) 表示 \(x \nless y\)；
  • \(x=y\) 表示 \(x \nless y\) 和 \(y \nless x\)。这就是为什么上面第四条规则被称为等价的传递性。如果 \(x \nless y\) 和 \(y \nless x\)，我们可以说「\(x\) 和 \(y\) 是不可比的」。

参考资料与拓展阅读

  1. Order theory - From Academic Kids
  2. Binary Relation - Wikipedia
  3. Order Theory - Wikipedia
  4. Order Theory, Lecture Notes by Mark Dean for Decision Theory
  5. 卢开澄，卢华明，《组合数学》（第 3 版）, 2006
  6. List of Order Theory Topics - Wikipedia
  7. 浅谈邻项交换排序的应用以及需要注意的问题 by ouuan
  8. One thing you should know about comparators—Strict Weak Ordering
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用