全序

全序
术语名称	全序
英语名称	total order
别名	线序, linear order, 简单序, simple order

全序集
术语名称	全序集
英语名称	totally ordered set
别名	线序集, linearly ordered set, loset, 简单序集, simply ordered set, 链, chain

全序(total order)，也称线序(linear order)，指集合上的一个二元关系，是完全的偏序，或者说同时是自反关系、反对称关系、传递关系、完全关系。 元素间存在全序关系的集合称为全序集(totally ordered set)或线序集(linearly ordered set)。

定义

对集合 [math]\displaystyle{ P }[/math] 上的二元关系 [math]\displaystyle{ \leq }[/math] ，如果是一个偏序、且有完全性，即满足：

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

称关系 [math]\displaystyle{ \leq }[/math] 为一个全序(total order)或线序(linear order)。 并称带有全序关系的集合 [math]\displaystyle{ (P, \leq) }[/math] 为全序集(totally ordered set)、线序集(linearly ordered set, loset)，有时也称链(chain)。

关系图特征

全部结点间构成一条链，链中任意结点存在到链方向全部结点的单向边，图中所有的边都指向自身或指向这一方向的结点。

全序集的结构可以被 Hasse 图直观地可视化。 Hasse 图中所有结点构成一条链。

性质

• 基本特征
  • 全序是自反、反对称、传递且完全的二元关系
• 序结构性质
  • 全序集的每个子集也是全序集（继承序关系）
  • 全序集的 Hasse 图是一条链（线性结构）
  • 有限全序集在同构意义下唯一由元素个数决定
• 运算性质
  • 全序的交不一定是全序
  • 全序的并不一定是全序
  • 全序的复合不一定是全序
  • 全序集的笛卡尔积在字典序下是全序集
• 全序集中的特殊元素
  • 全序集中的极大元、极小元与最大元、最小元等价。
  • 最大元、最小元如果存在则唯一。
  • 上确界、下确界如果存在则唯一。

关联

• 全序是完全的偏序。
• 全序是反对称的弱序。
• 全序和严格全序对应
  • 每个全序都可以诱导一个严格全序：定义 [math]\displaystyle{ x\lt y }[/math] 当且仅当 [math]\displaystyle{ x\leq y \land x\neq y }[/math] 。
  • 每个严格全序都可以诱导一个全序：定义 [math]\displaystyle{ x\leq y }[/math] 当且仅当 [math]\displaystyle{ x\lt y \lor 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]

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