预序

预序
术语名称	预序
英语名称	preorder
别名	quasi-order, 预序关系, non-strict preorder

预序集
术语名称	预序集
英语名称	proset
别名	preordered set, non-strictly preordered set

预序(preorder)指集合上的一个二元关系同时是自反关系和传递关系。 元素间存在预序关系的集合称为预序集(preordered set, proset)。

注意， quasi-order 一词在英语语境中是预序(preorder)的别名，是自反且传递的关系；但在中文语境中常翻译为拟序，且用来指反自反且传递的关系，见拟序条目。

为避免混淆，两个条目中均将 quasi-order 标注为别名，且从正文中删去。

定义

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

• 自反性： [math]\displaystyle{ \forall a \in P (a \preceq a) }[/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] 为一个预序(preorder)。 并称带有预序关系的集合 [math]\displaystyle{ (P,\preceq) }[/math] 为预序集(preordered set, proset)。

注：根据使用者的习惯，预序中的关系可能会使用符号 [math]\displaystyle{ \preceq,\precsim,\leq,\lesssim }[/math] 中的某个。

关系图特征

预序在关系图上的特征：

• 传递性的存在使得预序中的元素，要么形成一个团，要么形成层次。
• 关系图中的团对应同时在两方向满足关系的元素；
• 关系图中的层次，对应不在两个方向成立关系的元素必然在任意复合中都使得小的一侧比大的一侧更小；
  • 每个层次内可以存在多个连通分量，对应多组两两不可比较的元素；
  • 对于有多个连通分量的层次，每个连通分量本身又是一个预序，递归满足这一条件。

性质

• 基本特征
  • 预序是自反且传递的二元关系。
• 运算性质
  • 预序的交仍是预序；
  • 预序的并不一定是预序；
  • 预序的复合仍是预序。
• 预序集中的特殊元素
  • 有限预序集中总是存在极大元、极小元，有时存在最大元、最小元。
• 构造方法
  • 任意关系的自反传递闭包都是预序。
  • 等价关系与偏序的复合是预序。

关联

• 若一个预序是对称关系，则其是等价关系。此时集合只存在一个层次，且每个连通分量都是一个团。
  • 每个预序都可以诱导一个等价关系：定义 [math]\displaystyle{ x \sim y }[/math] 当且仅当 [math]\displaystyle{ x \preceq y \land y \preceq x }[/math] 。
  • 这个等价关系将预序集划分为等价类
• 若一个预序是反对称关系，则其是偏序，也就是不允许两个元素双方向成立关系。此时关系图中的团被消除，只剩下有层次的关系。
  • 每个预序中都有一个子关系是偏序：定义 [math]\displaystyle{ x \leq y }[/math] 当且仅当 [math]\displaystyle{ x \preceq y \land y \npreceq x }[/math] ，或 [math]\displaystyle{ x = y }[/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]

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