序理论

主要是为了解决邻项交换排序相关的问题的。不过研究到这里似乎有些深入了。

纯属本人兴趣。

OI 中应该重点关注严格弱序。因为排序时需要设计一种严格弱序关系。

数学约定

本文中用 $R(a,b)$ 表示 $a,b$ 满足二元关系 $R$。注意 $R(a,b)$ 是一种陈述语句。严格的陈述中需要说明 $a,b\in$ 某一特定的集合 $S$，不过为了叙述简洁本文大多数情况下省略这一点。需要的时候，用 $S$ 来表示这个集合。

正题

下表摘自 OI-Wiki，略有添改：

二元关系		自反性	反自反性	对称性	反对称性	非对称性	传递性	连接性	良基性	不可比的传递性
等价关系	equivalence relation	有		有			有
预序	preorder, quasiorder	有					有
偏序	partial order	有			有		有
弱序	weak order	有					有	有
全序	total order	有			有		有	有
良序	well-order	有			有		有	有	有
严格预序	strict preorder		有				有
严格偏序	strict partial order		有			有	有
严格弱序	strict weak order		有			有	有	有		有
严格全序	strict total order		有			有	有	有

不带 “严格” 字眼的关系都满足自反性；带 “严格” 字眼的都满足反自反性。下面把所有严格弱序需要满足的性质都加粗了。

性质		定义	实例（默认 $S=\mathbb{R}$）	备注
自反性	reflexive	$R(a,a)$	$a=a$、$a\le a$
反自反性	irreflexive, anti-reflexive	$\lnot R(a,a)$	$a\not\lt a$
对称性	symmetric	$R(a,b)\Leftrightarrow R(b,a)$	$a=b\Leftrightarrow b=a$
反对称性	antisymmetric	$R(a,b)\land R(b,a)\Rightarrow a=b$	$a\le b\land b\le a\Rightarrow a=b$
非对称性	asymmetric	$R(a,b)\Rightarrow \lnot R(b,a)$	$a\lt b\Rightarrow b\not\lt a$
传递性	transitive	$R(a,b)\land R(b,c)\Rightarrow R(a,c)$	$a\lt b\land b\lt c\Rightarrow a\lt c$
连接性	connected	$a\not=b\Rightarrow R(a,b)\lor R(b,a)$	$a\not=b\Rightarrow a<b\lor b<a$
良基性	well-founded	$\exists m\in S,\forall a\in S\setminus\{m\}\Rightarrow \lnot R(a,m)$	$S=\mathbb{R}_+$ 时，$a\gt 0$	就是 $S$ 中存在一个 $m$，使得 $S$ 中除了 $m$ 以外的所有元素 $a$ 都满足 $R(a,m)$
不可比的传递性	transitive of incomparability	$\bar{R}(a,b)\triangleq\lnot R(a,b)\land\lnot R(b,a),\\\bar{R}(a,b)\land\bar{R}(b,c)\Rightarrow\bar{R}(a,c)$	真的有例子吗？	$\bar{R}$ 即 $R$ 的不可比（也是一种二元关系）

最后三个性质比较抽象。

参考

• 浅谈邻项交换排序的应用以及需要注意的问题 - ouuan的博客
• 序理论 - OI Wiki（其参考了上面那篇博客）