序理论

简介¶

注释

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

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

为什么需要序理论？¶

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

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

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

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

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

定义¶

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

偏序集合¶

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

（自反的）
如果且，那么（反对称性）
如果且，那么（递移性）

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

或（全序性）

注释

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

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

次序中的特殊元素¶

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

对于阶的所有元素，。

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

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

意味着对于阶的所有元素，。

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

注释

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

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

对于中的所有，。

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

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

二元性¶

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

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

构建新次序¶

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

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

参考资料与拓展阅读¶

[1]Order theory - From Academic Kids
[2]Binary Relation - Wikipedia
[3]Order Theory - Wikipedia
[3]Order Theory, Lecture Notes by Mark Dean for Decision Theory
[4]卢开澄，卢华明，《组合数学》（第 3 版）, 2006
[5]List of Order Theory Topics - Wikipedia
[6]浅谈邻项交换排序的应用以及需要注意的问题 by ouuan
[7]One thing you should know about comparators — Strict Weak Ordering

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

序理论

简介¶

为什么需要序理论？¶

定义¶

偏序集合¶

次序中的特殊元素¶

二元性¶

构建新次序¶

相关领域和应用¶

通用代数¶

拓扑¶

范畴论¶

算法¶

参考资料与拓展阅读¶

评论