拟序

拟序
术语名称	拟序
英语名称	strict preorder
别名	quasi-order, 强序.strong order, 严格预序, 严格偏序, strict partial order

拟序集
术语名称	拟序集
英语名称	strictly partially ordered set
别名	严格预序集, 严格偏序集, strictly preordered set

拟序，或严格预序(strict preorder)、严格偏序(strict partial order)指集合上的一个二元关系同时是反自反关系和传递关系。同时，这样的关系一定是不对称关系。 元素间存在拟序关系的集合称为拟序集(strictly partially ordered set)。

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

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

定义

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

• 反自反性： [math]\displaystyle{ \forall a \in P \lnot (a \prec a) }[/math] ；
• 传递性： [math]\displaystyle{ \forall a \forall b \forall c (a \prec b \land b \prec c \rightarrow a \prec c) }[/math] 。

称关系 [math]\displaystyle{ \prec }[/math] 为一个拟序或严格预序(strict preorder)或严格偏序(strict partial order)。 并称带有拟序关系的集合 [math]\displaystyle{ (P,\preceq) }[/math] 为拟序集或严格预序集(strictly preordered set)、严格偏序集(strictly partially ordered set)。

注：根据使用者的习惯，拟序中的关系通常会使用符号 [math]\displaystyle{ \prec,\lt }[/math] 中的某个。

关系图特征

• 拟序的关系图是一个无自环的有向图，且传递闭包等于自身；
• 拟序关系图不允许有向环（由反自反性和传递性保证）。

性质

• 基本特征
  • 拟序是反自反且传递的二元关系。
  • 拟序必然是不对称关系。
• 运算性质
  • 拟序的交仍是拟序；
  • 拟序的并不一定是拟序；
  • 拟序的复合不一定是拟序。
• 拟序集中的特殊元素
  • 有限拟序集一定存在极大元、极小元。

关联

• 拟序的自反闭包是偏序，且预序中去除等价元素后也会成为拟序，可以通过以下方式转换。
  • 拟序可以诱导出一个偏序：定义 [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\npreceq b }[/math] 。
  • 偏序可以诱导出一个拟序：定义 [math]\displaystyle{ a\prec b }[/math] 当且仅当 [math]\displaystyle{ a\preceq b \land a\neq b }[/math] 。由于反对称性，也等价于 [math]\displaystyle{ a\preceq b \land a\npreceq 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]

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

琐事

名称

在中文语境中，拟序关系的英语为 quasi-order ，指反自反且传递的关系，偶尔可能指自反且传递的关系； 预序关系为 preorder，较多指自反且传递的关系，但也不少用作拟序关系的同义词，指反自反且传递的关系。 本 wiki 中按照中文语境的习惯确定预序关系和拟序关系这两个条目的名称。 但是使用英语的情况下， quasi-order 和 preorder 是同义词，指自反且传递的关系， 反自反的版本则通过在前面加上 strict 来表示。 这里术语的使用基本中英文是不对应的。