偏序关系

File:Hasse diagram of powerset of 3.svg

{x,y,z}的子集的集合按包含排序的哈斯图。

偏序集合（英语：Partially ordered set，简写Poset）是数学中，特别是序理论中，指配备了偏序关系的集合。 这个理论将对集合的元素进行排序、顺序或排列等直觉概念抽象化。这种排序不必是全部的，就是说不需要保证此集合内的所有对象的相互可比较性。偏序空间是具有闭偏序的拓扑空间。

定义

非严格偏序，自反偏序

给定集合 <math>S</math>， 设“<math>\leq</math>”是 <math>S</math> 上的二元关系，若“<math>\leq</math>”满足：

1. 自反性：对所有<math>a \in S</math>，有 <math>a \leq a</math>；
2. 反对称性：对所有<math>a, b \in S</math>，若 <math>a \leq b</math> 且 <math>b \leq a</math>，则 <math>a = b</math>；
3. 传递性：对所有<math>a, b, c \in S</math>，若 <math>a \leq b</math> 且 <math>b \leq c</math>，则 <math>a \leq c</math>；

则称“<math>\leq</math>”是 <math>S</math> 上的非严格偏序或自反偏序。

严格偏序，反自反偏序

给定集合 <math>S</math>，设“<math><</math>”是 <math>S</math> 上的二元关系，若“<math><</math>”满足：

1. 反自反性：对所有<math>a \in S</math>，有 <math>a \not< a</math>；
2. 非对称性：对所有<math>a, b \in S</math>，若 <math>a < b</math>，则 <math>b \not< a</math>；
3. 传递性：对所有<math>a, b, c \in S</math>，若 <math>a < b</math> 且 <math>b < c</math>，则 <math>a < c</math>；

则称“<math><</math>”是 <math>S</math> 上的严格偏序或反自反偏序。

严格偏序与有向无环图（DAG）有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。其传递闭包是它自己。

偏序

容易证明以下结论：

• 给定集合 <math>S</math> 上的一个（非严格，自反）偏序“<math>\leq</math>”，则可自然地诱导出 <math>S</math> 上的一个（严格，反自反）偏序“<math><</math>”，只需如此定义：

<math>a < b</math> 当且仅当 <math>a \leq b</math> 且 <math>a \neq b</math>。

• 给定集合 <math>S</math> 上的一个（严格，反自反）偏序“<math><</math>”，则可自然地诱导出 <math>S</math> 上的一个（非严格，自反）偏序“<math>\leq</math>”，只需如此定义：

<math>a \leq b</math> 当且仅当 <math>a < b</math> 或 <math>a = b</math>。

• 给定集合 <math>S</math> 上的一个（非严格，自反）偏序“<math>\leq</math>”，其逆关系“<math>\geq</math>”也是 <math>S</math> 上的一个（非严格，自反）偏序；
• 给定集合 <math>S</math> 上的一个（严格，反自反）偏序“<math><</math>”，其逆关系“<math>></math>”也是 <math>S</math> 上的一个（严格，反自反）偏序；

由上述可知，只要定义了“<math>\leq</math>”、“<math><</math>”、“<math>\geq</math>”、“<math>></math>”中的任何一个，其余三个关系的定义可以自然诱导而出，这四种关系实际上可以看成一体。故此在不严格区分的情况下，只需定义其一即可（通常是“<math>\leq</math>”），称之为集合 <math>S</math> 上的偏序关系。（“偏序关系”通常被用来称呼非严格偏序关系。）

• （非严格，自反）偏序和（严格，反自反）偏序之间的对应关系不同于在（非严格）弱序和严格弱序直接的对应（逆关系的补集）。只有对于全序这些对应才是相同的。

偏序集与序对偶

若集合 <math>S</math> 上定义了一个偏序，则 <math>S</math> 称为偏序集（poset）；若将其上的偏序关系改为其逆关系，得到的新偏序集 <math>S'</math> 称为 <math>S</math> 的序对偶。

虽然通常术语“有序集”用来称呼全序集，但当上下文中不涉及其他序关系时，“有序集”也可用于称呼偏序集。

例子

下面是一些主要的例子：

• 自然数的集合配备了它的自然次序（小于等于关系）。这个偏序是全序。
• 整数的集合配备了它的自然次序。这个偏序是全序。
• 自然数的集合的有限子集{1, 2, ..., n}。这个偏序是全序。
• 自然数的集合配备了整除关系。
• 给定集合的子集的集合（它的幂集）按包含排序。
• 向量空间的子空间的集合按包含来排序。

一般的说偏序集合的两个元素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