在数学中,特别是序理论中,偏序集合(简写为 poset)是配备了偏序关系的集合。这个关系形式化了排序、顺序或排列这个集合的元素的直觉概念。这种排序不必然需要是全部的,就是说不需要但也可以保证在这个集合内的所有对象的相互可比较性。(在数学用法中,全序是一种偏序)。偏序集合定义了偏序集合拓扑。
形式定义
下面是一些主要的例子:
自然数的集合配备了它的自然次序(小于等于关系)。这个偏序是全序。
整数的集合配备了它的自然次序。这个偏序是全序。
自然数的集合的有限子集 {1, 2, ..., n}。这个偏序是全序。
自然数的集合配备了整除关系。
给定集合的子集的集合(它的幂集)按包含排序。
向量空间的子空间的集合按包含来排序。
例子
在某些上下文中,上面定义的偏序叫做非严格(或自反)偏序。在这些上下文中,严格(或反自反)偏序是反自反的、非对称的和传递的二元关系。
就是,对于所有集合 P 中的 a, b 和 c,严格偏序 < 有着:
如果 R 是非严格偏序,则 S = R − {(a, a) | a ∈ P} 是对应的严格偏序。类似的,所有严格偏序 S 都有一个对应的非严格偏序 S ∪ {(a, a) | a ∈ P}。注意这个对应不同于在(非严格)弱序和严格弱序直接的对应(逆关系的补集)。只有对于全序这些对应才是相同的。
严格偏序是有用的,因为它们更直接对应有向无环图(dag): 所有严格偏序是 dag,而 dag 的传递闭包是严格偏序也是 dag 自身。
¬(a < a) (反自反性);
如果 a < b 则 ¬(b < a) (非对称性);
如果 a < b 且 b < c 则 a < c (传递性)。
严格和非严格偏序
全序 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
引用
二元关系
全序关系
预序关系