偏序关系

在数学中，特别是序理论中，偏序集合(简写为 poset)是配备了偏序关系的集合。这个关系形式化了排序、顺序或排列这个集合的元素的直觉概念。这种排序不必然需要是全部的，就是说不需要但也可以保证在这个集合内的所有对象的相互可比较性。(在数学用法中，全序是一种偏序)。偏序集合定义了偏序集合拓扑。

[编辑] 形式定义

偏序是在集合 P 上的二元关系 ≤，它是自反的、反对称的、和传递的，就是说，对于所有 P 中的 a, b 和 c，有着:

• a ≤ a (自反性)；
• 如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)；
• 如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)。

带有偏序的集合叫做偏序集合(也叫做 poset)。术语有序集合有时也用于偏序集合，只要上下文中不涉及其他种类的次序。特别是，全序集合也可以被称为是"有序集合"，特别是在这些结构比偏序集合更常用的领域内。

[编辑] 例子

下面是一些主要的例子:

{x,y,z} 的子集的集合按包含排序

• 自然数的集合配备了它的自然次序(小于等于关系)。这个偏序是全序。

• 整数的集合配备了它的自然次序。这个偏序是全序。

• 自然数的集合的有限子集 {1, 2, ..., n}。这个偏序是全序。

• 自然数的集合配备了整除关系。

• 给定集合的子集的集合(它的幂集)按包含排序。

• 向量空间的子空间的集合按包含来排序。

[编辑] 严格和非严格偏序

在某些上下文中，上面定义的偏序叫做非严格(或自反)偏序。在这些上下文中，严格(或反自反)偏序是反自反的、非对称的和传递的二元关系。

就是，对于所有集合 P 中的 a, b 和 c，严格偏序 < 有着:

• ¬(a < a) (反自反性)；
• 如果 a < b 则 ¬(b < a) (非对称性)；
• 如果 a < b 且 b < c 则 a < c (传递性)。

如果 R 是非严格偏序，则 S = R − {(a, a) | a ∈ P} 是对应的严格偏序。类似的，所有严格偏序 S 都有一个对应的非严格偏序 S ∪ {(a, a) | a ∈ P}。注意这个对应不同于在(非严格)弱序和严格弱序直接的对应(逆关系的补集)。只有对于全序这些对应才是相同的。

严格偏序是有用的，因为它们更直接对应有向无环图(dag): 所有严格偏序是 dag，而 dag 的传递闭包是严格偏序也是 dag 自身。

[编辑] 线性扩展

全序 T 是偏序 P 的线性扩展，只要 x ≤ y 在 P 中成立则 x ≤ y 在 T 中也成立。在计算机科学中，找到偏序的线性扩展的算法叫做拓扑排序。

[编辑] 引用

• J. V. Deshpande, On Continuity of a Partial Order, Proceedings of the American Mathematical Society, Vol. 19, No. 2, 1968, pp. 383-386

[编辑] 参见

• 二元关系
• 全序关系
• 预序关系