偏序

偏序
术语名称	偏序
英语名称	partial order
别名	偏序关系, weak partial order, reflexive partial order, 非严格偏序, non-strict partial order

偏序集
术语名称	偏序集
英语名称	partially ordered set
别名	poset, non-strict partially ordered set

偏序(partial order)指集合上的一个二元关系同时是自反关系、反对称关系和传递关系。 元素间存在偏序关系的集合称为偏序集(partially ordered set, poset)。

定义

对集合 [math]\displaystyle{ P }[/math] 上的二元关系 [math]\displaystyle{ \preceq }[/math] ，如果满足自反性、反对称性和传递性，即：

• 自反性： [math]\displaystyle{ \forall a \in P (a \preceq a) }[/math]
• 反对称性： [math]\displaystyle{ \forall a \forall b ((a \preceq b \land b \preceq a) \rightarrow a = b) }[/math]
• 传递性： [math]\displaystyle{ \forall a \forall b \forall c (a \preceq b \land b \preceq c \rightarrow a \preceq c) }[/math]

称关系 [math]\displaystyle{ \preceq }[/math] 为一个偏序(partial order)。 并称带有偏序关系的集合 [math]\displaystyle{ (P, \preceq) }[/math] 为偏序集(partially ordered set, poset) 。

关系图特征

偏序在关系图上的特征：

• 偏序中存在不可比较的元素，这些元素使得局部上存在不连通的区域；
• 传递性的存在使得预序中的关系链上的元素形成类似层次的结构，不连通的区域间层数可能有差异。
• 每个层次内可能分为多个连通分量，每个连通分量本身又是一个偏序，递归满足这一条件。

性质

• 基本特征
  • 偏序是自反、反对称且传递的二元关系。
  • 偏序关系的关系图是有向无环图（DAG），且每个顶点有自环。
• 运算性质
  • 偏序的交仍是偏序；
  • 偏序的并不一定是偏序；
  • 偏序的复合不一定是偏序；
  • 偏序集的笛卡尔积在字典序下是偏序集。
• 偏序集中的特殊元素
  • 最大元、最小元如果存在则唯一
  • 极大元、极小元可能不唯一

相关概念

偏序是非常常见且重要的概念，相关的研究产生了很多相关概念，见以下各个条目：

• Hasse 图：偏序集的可视化表示，省略可通过自反性和传递性得出的边，剩余的骨架结构。通常用于有限偏序集。
  • 覆盖关系：偏序在 Hasse 图中剩余的骨架关系。
• 链：偏序的全序子关系，即两两可比较的子集。
• 反链：偏序中两两不可比较的子集。
• 区间：偏序集中两个元素之间的所有元素。

关联

• 偏序是预序的特例，增加了反对称性要求。
  • 若一个偏序是完全关系，是全序。
  • 恒等关系也是偏序关系，且是唯一一个同时是偏序关系和等价关系的关系。
• 偏序也被称为非严格偏序，而去除自反部分后剩下的反自反核称为严格偏序，即拟序。
  • 拟序可以诱导出一个偏序：定义 [math]\displaystyle{ a\preceq b }[/math] 当且仅当 [math]\displaystyle{ a\prec b \lor a=b }[/math] 。
  • 偏序可以诱导出一个拟序：定义 [math]\displaystyle{ a\prec b }[/math] 当且仅当 [math]\displaystyle{ a\preceq b \land a\neq b }[/math] 。

关系
定义属性	前域、后域、定义域 [math]\displaystyle{ \operatorname{dom} }[/math]、值域 [math]\displaystyle{ \operatorname{ran} }[/math]、域 [math]\displaystyle{ \operatorname{fld} }[/math]
特殊关系	空关系 [math]\displaystyle{ \varnothing }[/math]、恒等关系 [math]\displaystyle{ I }[/math]、全关系 [math]\displaystyle{ A\times B }[/math]
二元齐次关系类型	自反、反自反、对称、反对称、传递
运算	集合运算	交 [math]\displaystyle{ \cap }[/math]、并 [math]\displaystyle{ \cup }[/math]、补 [math]\displaystyle{ \bar{\bullet} }[/math]、差 [math]\displaystyle{ \setminus }[/math]
	类映射运算	转置/逆 [math]\displaystyle{ \bullet^\mathrm{T}/\bullet^{-1} }[/math]、复合 [math]\displaystyle{ \circ }[/math]（幂 [math]\displaystyle{ \bullet^n }[/math]）、限制 [math]\displaystyle{ \bullet_{|\bullet} }[/math]
	闭包运算	自反 [math]\displaystyle{ \operatorname{r}() }[/math]/[math]\displaystyle{ \bullet^= }[/math]、对称 [math]\displaystyle{ \operatorname{s}() }[/math]/[math]\displaystyle{ \bullet^\sim }[/math]、传递 [math]\displaystyle{ \operatorname{t}() }[/math]/[math]\displaystyle{ \bullet^+ }[/math]、自反传递 [math]\displaystyle{ \bullet^* }[/math]、等价 [math]\displaystyle{ \bullet^\equiv }[/math]

二元关系复合类型
名称	自反、反自反	对称、反对称	传递	其他
相容关系	自反	对称	-	-
预序	自反	-	传递	-
等价关系	自反	对称	传递	-
方向	自反	-	传递	有上/下界
偏序	自反	反对称	传递	-
半格	自反	反对称	传递	有上/下确界
弱序/全序划分	自反	-	传递	完全
全序	自反	反对称	传递	完全
良序	自反	反对称	传递	完全、良基
不对称	反自反	反对称	-	-
拟序/严格偏序	反自反	反对称	传递	-
严格弱序/严格全序划分	反自反	反对称	传递	不可比关系传递
严格全序	反自反	反对称	传递	完全