偏序关系
维基百科，自由的百科全书
在数学中，特别是序理论中，偏序集合(简写为 poset)是配备了偏序关系的集合。这个关系形式化了排序、顺序或排列这个集合的元素的直觉概念。这种排序不必然需要是全部的，就是说不需要但也可以保证在这个集合内的所有对象的相互可比较性。(在数学用法中，全序是一种偏序)。偏序集合定义了偏序拓扑。
目录 |
[编辑] 形式定义
偏序是在集合 P 上的二元关系 ≤，它是自反的、反对称的、和传递的，就是说，对于所有 P 中的 a, b 和 c，有着:
- a ≤ a (自反性)；
- 如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)；
- 如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)。
带有偏序的集合叫做偏序集合(也叫做 poset)。术语有序集合有时也用于偏序集合，只要上下文中不涉及其他种类的次序。特别是，全序集合也可以被称为是"有序集合"，特别是在这些结构比偏序集合更常用的领域内。
[编辑] 例子
下面是一些主要的例子:
- 整数的集合配备了它的自然次序。这个偏序是全序。
- 自然数的集合的有限子集 {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 自身。
[编辑] 逆关系和序对偶
偏序关系 ≤ 的逆或反关系 ≥ 满足 x≥y 当且仅当 y≤x。偏序关系的逆关系是自反的、传递的和反对称的，因此自身也是偏序关系。偏序集合的“序对偶”是把偏序关系替代为它的逆关系的同一个集合。对于反自反关系有 > 对应 ≥ 而 < 对应 ≤。
在给定集合上的四个关系 ≤、<、≥、和 > 中的任何一个都唯一确定自其他三个。
一般的说偏序集合的两个元素 x 和 y 可以处于四个相互排斥的关联中任何一个: 要么 x < y，要么 x = y，要么 x > y，要么 x 和 y 是“不可比较”的(三个都不是)。全序集合是用规则排除第四种可能的集合: 所有元素对都是可比较的，并且声称三分法成立。自然数、整数、有理数和实数都关于它们代数(有符号)大小是全序的，而复数不是。这不是说复数不能全序排序；比如我们可以按词典次序排序它们，通过 x+iy < u+iv 当且仅当 x < u 或 (x = u 且 y < v)，但是这种排序没有合理的大小意义因为它使得 1 大于 100i。按绝对大小排序它们产生在其中所有对都是可比较的预序，但这不是偏序因为 1 和 i 有相同的绝对大小但却不相等，违反了反对称性。
[编辑] 线性扩展
全序 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
