常用序关系

偏序

若集合 S 上的二元关系 \le 满足：

• 自反性：x \le x
• 反对称性：x \le y \land y \le x \to x = y
• 传递性：x \le y, y \le z \to x \le z 则称 \le 为 S 上的一个偏序关系。

例如，整数的整除关系 (\mathbb{Z}, \mid)、集合之间的包含 (\mathcal{P}(A), \subset) 是偏序关系。

当 x \nleq y 且 y \nleq x 时，称 x 和 y 不可比，否则称为可比。例如，整除关系中，6 和 12 可比（6 \mid 12），但 7 和 8 不可比（7 \nmid 8 且 8 \nmid 7）。

全序

任意两个元素都可比的偏序关系，称为全序。

例如，实数上的小于等于关系 (\mathbb{R}, \le) 是全序关系。整数上的整除关系则不是全序关系。

严格弱序

严格弱序（strickly weak order）是一个常用于规定排序顺序的关系。

严格弱序的定义为一个满足不可比性的传递性的严格偏序关系 <：

• 反自反性：x \nless x；
• 反对称性：x < y \to y \nless x；
• 传递性：x < y, y < z \to x < z；
• 不可比的传递性：x \nless y, y \nless x, y \nless z, z\nless y \to x \nless z, z\nless x。

当 x \nless y 且 y \nless x 时，称 x 和 y 不可比，可以看做广义的“相等”。严格弱序要求偏序关系导出的不可比关系可以作为一个等价关系，也可以看做，严格弱序要求可以用 x \nless y 且 y \nless x 来判断 x = y。

排序 算法或要求内部元素有序的数据结构（如 二叉堆、（链接未公开））通常要求序关系满足严格弱序。

严格全序关系一定是严格弱序，因为此时没有不可比性。

二维偏序

当一个二元组的两个分量上都有全序关系时，可以定义 (a, b) \le (c, d) 当且仅当 a \le c 且 b \le d，这样定义将得到一个偏序关系，称为二维偏序。

逆序对（（链接未公开））定义为满足 i > j 且 a_i < a_j 的下标对 (i, j)，是典型的二维偏序，可以使用（链接未公开）在 O(n \log n) 时间内计算一个数组的逆序数。

偏序的性质

Hasse 图

一个有限集上的偏序关系可以导出一幅有向图。有向图的每个节点是集合的元素，然后当 a \le b 且不存在 c 使得 a \le c \le b 时，连接一条有向边 a \to b。这样构造的一幅有向图称为这个偏序关系的 Hasse 图。

Dilworth 定理

链和反链

在偏序关系（及其 Hasse 图） (S, \le) 中，若存在一个子集（子图），其上的元素两两可比，则称为一条链。链上的元素构成全序关系，可以按全序排列。若存在一个子集，其上的元素两两不可比，则称为一条反链。

若存在若干条两两不交的链 C_1, \dots, C_k 满足 \bigcup_i C_i = S，则称 C_1, \dots, C_k 是 S 的一个链覆盖。同理可以定义反链覆盖。

Dilworth 定理叙述

Dilworth 定理表明：Hasse 图上的最长链长度，等于最小反链覆盖的反链数；最长反链长度也等于最小链覆盖的链数。

简记为：最长链 = 最小反链覆盖，最长反链 = 最小链覆盖

证明

仅证明最长链 = 最小反链覆盖，反过来的证明类似。

由于最长链的长度为 k，显然链上每个节点都应该属于不同的反链，否则一条反链内将存在可比的元素。因此，反链的数目至少为 k。下面证明存在数目恰好为 k 的反链划分。

使用数学归纳法，对最长链的长度归纳。

最长链的长度为 1 时，Hasse 图中是一些孤立的点，所有的点构成一条反链，最小反链覆盖数为 1，命题成立。

假设最长链的长度小于 k 时都成立。对最长链的长度为 k 的 Hasse 图，取其所有最长链的最大元，则这些最大元两两不可比（假设最大元 a 与最大元 b 可比，且 a \le b，设最大元 a 所在最长链为 C，则 C \cup \{b\} 是一条长为 k + 1 的链，矛盾）。于是它构成一条反链。去除这些最大元后，得到一个最长链为 k - 1 的 Hasse 图，由归纳假设，有 k - 1 条反链可以覆盖图，于是由最大元的反链加上 k - 1 条反链，得到 k 条反链的覆盖。