19.序理论

引入

序理论是利用二元关系来将「次序」这一概念严格化的数学分支，下面将介绍这一分支的基本定义。

定义

二元关系

定义

集合 $X$ 和集合 $Y$ 上的一个 二元关系（binary relation） $R$ 定义为元组 $(X, Y, G (R))$ ，其中 $X$ 称为定义域（domain）， $Y$ 称为陪域（codomain）， $G (R) \subseteq X \times Y = {(x, y) : x \in X, y \in Y}$ 称为二元关系 $R$ 的图（graph）。 $x R y$ 成立当且仅当 $(x, y) \in G (R)$ 。

若 $X = Y$ ，则称该二元关系为齐次二元关系（homogeneous relation）或内关系（endorelation）。

若没有特别说明，下文中的二元关系均为齐次二元关系。

例如 $N_{+}$ 上的整除 $∣$ 和小于等于 $\leq$ 均为二元关系。

我们研究二元关系时，往往会关注其是否具有一些特别的性质。对集合 $S$ 上的二元关系 $R$ ，我们定义如下特殊性质：

自反性（reflexive）： $(\forall a \in S) a R a$ ，
反自反性（irreflexive，anti-reflexive）： $(\forall a \in S) \neg (a R a)$ ，
对称性（symmetric）： $(\forall a, b \in S) a R b ⟺ b R a$ ，
反对称性（antisymmetric）： $(\forall a, b \in S) (a R b \land b R a) ⟹ a = b$ ，
非对称性（asymmetric）： $(\forall a, b \in S) a R b ⟹ \neg (b R a)$ ，
传递性（transitive）： $(\forall a, b, c \in S) (a R b \land b R c) ⟹ a R c$ ，
连接性（connected）： $(\forall a, b \in S) a \neq = b ⟹ (a R b \lor b R a)$ ，
良基性（well-founded）： $(\exists m \in S \neq = \emptyset) (\forall a \in S ∖ {m}) \neg (a R m)$ （即非空集合 $S$ 中有极小元 $m$ ），
不可比的传递性（transitive of incomparability）： $(\forall a, b, c \in S) (\neg (a R b \lor b R a) \land \neg (b R c \lor c R b)) ⟹ \neg (a R c \lor c R a)$ （若 $\neg (a R b \lor b R a)$ ，则称 $a$ 和 $b$ 是不可比的）。

同时我们定义一些特殊的二元关系：

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

关系间的运算

对集合 $X$ 和集合 $Y$ 上的二元关系 $R$ 和 $S$ ，我们可以定义如下运算：

$R$ 和 $S$ 的并 $R \cup S$ 满足 $G (R \cup S) := {(x, y) : x R y \lor x S y}$ （如 $\leq$ 是 $<$ 和 $=$ 的并），
$R$ 和 $S$ 的交 $R \cap S$ 满足 $G (R \cap S) := {(x, y) : x R y \land x S y}$ ，
$R$ 的补 $\overset{ˉ}{R}$ 满足 $G (\overset{ˉ}{R}) := {(x, y) : \neg (x R y)}$ ，
$R$ 的对偶 $R^{T}$ 满足 $G (R^{T}) := {(y, x) : x R y}$ .

对集合 $X$ 和集合 $Y$ 上的二元关系 $R$ 以及集合 $Y$ 和集合 $Z$ 上的二元关系 $S$ ，我们可以定义其复合 $S \circ R$ 满足 $G (S \circ R) := {(x, z) : (\exists y \in Y) x R y \land y S z}$ .

偏序集

定义

若集合 $S$ 上的一个二元关系 $⪯$ 具有 自反性、反对称性、传递性，则称 $S$ 是 偏序集（partially ordered set，poset）， $⪯$ 为其上一偏序（partial order）。

若偏序 $⪯$ 还具有 连接性，则称其为全序（total order），对应的集合称为 全序集（totally ordered set）、线性序集（linearly ordered set，loset）、简单序集（simply ordered set）。

不难发现 $N$ ， $Z$ ， $Q$ 、 $R$ 均关于 $\leq$ 构成全序集。

偏序集的可视化表示：Hasse 图

对于有限偏序集，我们可以用 Hasse 图直观地表示其上的偏序关系。

定义

对有限偏序集 $S$ 和其上的偏序 $⪯$ ，定义 $x ≺ y ⟺ (x ⪯ y \land x \neq = y)$ 其对应的 Hasse 图 为满足如下条件的图 $G = ⟨ V, E ⟩$ ：

$V = S$ ,

$E = {(x, y) \in S \times S : x ≺ y \land ((∄ z \in S) x ≺ z ≺ y)}$

如对于集合 ${0, 1, 2}$ 的幂集 $S$ 和集合的包含关系 $\subseteq$ ，其对应的 Hasse 图为：

由于偏序具有反对称性，所以 Hasse 图一定是有向无环图，进而我们可以根据拓扑排序对任意有限偏序集构造全序。

链与反链

定义

对偏序集 $S$ 和其上的偏序 $⪯$ ，称 $S$ 的全序子集为链（chain）。若 $S$ 的子集 $T$ 中任意两个不同元素均不可比（即 $(\forall a, b \in T) a \neq = b ⟹ (a ⋠ b \land b ⋠ a)$ ），则称 $T$ 为反链（antichain）。

对偏序集 $S$ 和其上的偏序 $⪯$ ，我们将偏序集 $S$ 的最长反链长度称为宽度（partial order width）。

如对于集合 ${0, 1, 2}$ 的幂集 $S$ 和集合的包含关系 $\subseteq$ ， ${\emptyset, {1}, {1, 2}}$ 为一条链， ${{1}, {0, 2}}$ 为一条反链， $S$ 的宽度为 $3$ .

预序集中的特殊元素

在预序集中，我们可以定义极大（小）元、上（下）界、上（下）确界等概念，这些概念可以推广到其他序关系中。

定义

对预序集 $S$ 和其上的预序 $⪯$ ，取 $S$ 中的元素 $m$ ：

若 $(\forall a \in S ∖ {m}) \neg (m ⪯ a)$ ，则称 $m$ 为 极大元（maximal element），

若对 $T \subseteq S$ 满足 $(\forall t \in T) t ⪯ m$ ，则称 $m$ 为 $T$ 的上界（upper bound），

若对 $T \subseteq S$ 满足 $m$ 是 $T$ 的上界且对 $T$ 的任意上界 $n$ 均有 $m ⪯ n$ ，则称 $m$ 为 $T$ 的 上确界（supremum）。

类似可定义 极小元（minimal element）、下界（lower bound）和 下确界（infimum）。

如 $1$ 是 $N_{+}$ 的极小元和下界。

可以证明：

预序集中，极大（小）元、上（下）界、上（下）确界都是不一定存在的，即使存在也不一定唯一。
若偏序集 $S$ 的子集 $T$ 存在上（下）确界，则一定唯一。

我们可将 $T$ 的上确界、下确界分别记为 $sup T$ ， $in f T$ . 若偏序集 $S$ 既有上界又有下界，则称 $S$ 是有界的。

在无限偏序集中，极大元不一定存在。可用 Zorn 引理（Zorn’s Lemma）来判断无限偏序集中是否存在极大元。

Zorn 引理

Zorn 引理 也被称为 Kuratowski–Zorn 引理，其内容为：若非空偏序集的每条链都有上界，则该偏序集存在极大元。

Zorn 引理与 选择公理、良序定理 等价。

有向集与格

我们知道若偏序集的子集存在上（下）确界，则一定唯一。但是这一点并不适用于极大（小）元。例如：考虑偏序集 $S = {{0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}}$ 和其上的偏序 $\subseteq$ ，不难发现其有 $3$ 个极大元和 $3$ 个极小元。

我们希望通过向偏序集添加一定的条件来使得若极大（小）元存在则一定唯一，这样我们就可以定义最大（小）元的概念了。

有向集

对预序集 $S$ 和其上的预序 $⪯$ ，若 $(\forall a, b \in S) (\exists c \in S) a ⪯ c \land b ⪯ c$ ，则称 $⪯$ 为 $S$ 的一个方向（direction）， $S$ 称为 有向集（directed set）或 过滤集（filtered set）。

有时也将满足上述定义的集合 $S$ 称为 上有向集（upward directed set），类似地可定义 下有向集（downward directed set）。

有向集也可用如下方式定义：

有向集的等价定义

对预序集 $S$ 和其上的预序 $⪯$ ，若 $S$ 的任意有限子集 $T$ 均有上界，则称 $⪯$ 为 $S$ 的一个方向， $S$ 称为有向集。

不难发现：

若上有向集存在极大元，则一定唯一。我们将上有向集的极大元称为 最大元（greatest element）。
若下有向集存在极小元，则一定唯一。我们将下有向集的极小元称为 最小元（least element）。

有方向的偏序集中，对任意元素 $a, b$ ， ${a, b}$ 都有上界，若将上界修改为上确界，则得到了并半格的定义。

对偏序集 $S$ 和其上的偏序 $⪯$ ：

并半格

若对 $S$ 中的任意元素 $a, b$ ， ${a, b}$ 均有上确界 $c$ ，则称 $S$ 为 并半格（join-semilattice，upper semilattice），并且我们称 $c$ 为 $a$ 和 $b$ 的并（join），记为 $a \lor b$ .

交半格

若对 $S$ 中的任意元素 $a, b$ ， ${a, b}$ 均有下确界 $c$ ，则称 $S$ 为 交半格（meet-semilattice，lower semilattice），并且我们称 $c$ 为 $a$ 和 $b$ 的交（meet），记为 $a \land b$ .

格

若 $S$ 既是并半格也是交半格，则称 $S$ 为格（lattice）。

例如 $60$ 的正因子构成的集合 $S = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}$ 关于整除构成偏序集，其上的任意正整数 $a, b$ ， $lcm (a, b)$ 为 $a$ 和 $b$ 的并， $g cd (a, b)$ 为 $a$ 和 $b$ 的交，从而 $S$ 是格。

对偶

在序理论中，对偶是非常常见的概念，如上文提到的极大元与极小元对偶、上界与下界对偶、上确界与下确界对偶。

对偏序集 $P$ 和其上的偏序 $⪯$ ，定义其对偶（dual，opposite）偏序集 $P^{d}$ 满足： $x ⪯ y$ 在 $P$ 中成立当且仅当 $y ⪯ x$ 在 $P^{d}$ 中成立。将 $P$ 的 Hasse 图的边反转即可得到 $P^{d}$ 的 Hasse 图。

Dilworth 定理与 Mirsky 定理

对有限偏序集 $S$ 和其上的偏序 $⪯$ ，我们有如下的一对对偶的定理：

Dilworth 定理

$S$ 的宽度（最长反链长度）等于最小的链覆盖数。

证明 $∣ S ∣ \leq 3$ 时，命题显然成立。

考虑数学归纳法。当

假设命题对所有元素个数小于 $∣ S ∣$ 的偏序集都成立，令 $S$ 的宽度为 $d$ . 若 $∣ S ∣$ 中所有元素均不可比，则命题显然成立，否则在 $S$ 中取一条长度大于 $1$ 的链，令其中的最小元为 $m$ ，最大元为 $M$ .

令 $T = S ∖ {m, M}$ ，若 $T$ 中的宽度不超过 $d - 1$ ，则由归纳假设知 $T$ 可被至多 $d - 1$ 条链覆盖，进而 $S$ 可被这些链再加上链 ${m, M}$ 覆盖，命题成立，否则说明 $T$ 中的宽度也为 $d$ ，令 $T$ 中最长的一条反链为 $A$ .

我们考虑如下两个集合：
$S^{+} := {x \in S : (\exists a \in A) a ⪯ x}$ $S^{-} := {x \in S : (\exists a \in A) x ⪯ a}$
我们不难发现如下性质：

$S^{+} \cup S^{-} = S$ ，

$S^{+} \cap S^{-} = A$ ，

$∣ S^{+} ∣ < ∣ S ∣$ , $∣ S^{-} ∣ < ∣ S ∣$ （因为 $m \in / S^{+}$ 且 $M \in / S^{-}$ ）。

对 $S^{+}$ 和 $S^{-}$ 都应用归纳假设，则这两个集合的最小链覆盖数为 $d$ ，且这些链中恰好包含一个 $A$ 中的元素 $a$ ，设这些链分别为 $C_{a}^{+}$ ， $C_{a}^{-}$ ，则 ${C_{a}^{-} \cup {a} \cup C_{a}^{+}}_{a \in A}$ 是 $S$ 的一个最小链覆盖，命题得证。

Mirsky 定理

$S$ 的最长链长度等于最小的反链覆盖数。

证明 $S$ 的最长链长度为 $d$ ，则由定义，最小反链覆盖数至少为 $d$ .

设

令 $f (s)$ 为以 $s$ 为最小元的最长链长度，注意到若 $f (s) = f (t)$ ，则 $s$ 与 $t$ 不可比，进而 $(\forall n \in N) f^{- 1} ({n})$ 均为反链，其中 $f^{- 1} ({n}) := {a \in S : f (a) = n}$ 称为水平集（level set）。

因此不难得出 ${f^{- 1} ({i}) : 1 \leq i \leq d}$ 是一个反链覆盖，从而最小反链覆盖数至多为 $d$ .

Dilworth 定理与 Hall 婚配定理等价。

我们可以用 Dilworth 定理证明如下定理：

Erdős–Szekeres 定理

含至少 $r s + 1$ 个元素的实数序列 ${a_{i}}$ 要么有一个长为 $r + 1$ 的不下降子序列，要么有一个长为 $s + 1$ 的不上升子序列。

证明 $n \geq r s + 1$ ，定义偏序集 ${(i, a_{i})}_{i = 1}^{n}$ ，其上的偏序 $⪯$ 定义为：

设序列长度为

$(i, a_{i}) ⪯ (j, a_{j}) ⟺ (i \leq j \land a_{i} \leq a_{j})$
假设该偏序集的宽度不超过 $s$ ，则由 Dilworth 定理可知该偏序集可以被至多 $s$ 条链覆盖，若这些链的长度都不超过 $r$ ，则序列所含元素数至多为 $r s$ ，与条件矛盾。

例题

Luogu P1020 [NOIP1999 提高组] 导弹拦截
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

对于全部数据，满足导弹的高度为正整数，且不超过 $5 \times 1 0^{4}$ .

题解 $n$ 个导弹，第 $i$ 个导弹的高度为 $h_{i}$ ，则集合 ${(i, h_{i})}_{i = 1}^{n}$ 为偏序集，其上的偏序 $⪯$ 定义为：

令一共有

$(i, h_{i}) ⪯ (j, h_{j}) ⟺ (i \leq j \land h_{i} \geq h_{j})$
进而根据 Dilworth 定理有：序列的不上升子序列的最少覆盖数等于最长上升子序列长度。从而可以通过最长不下降子序列的 $O(n\log n)$ 做法解决本题。
参考代码
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
  vector<int> a;
  int x;
  while (cin >> x) a.push_back(x);
  vector<int> f, g;
  for (int i : a) {
    if (f.empty() || -i >= f.back())
      f.push_back(-i);
    else
      *upper_bound(f.begin(), f.end(), -i) = -i;
    if (g.empty() || i > g.back())
      g.push_back(i);
    else
      *lower_bound(g.begin(), g.end(), i) = i;
  }
  cout << f.size() << '\n' << g.size() << '\n';
  return 0;
}

[TJOI2015] 组合数学
给一个 $n$ 行 $m$ 列的网格图，其中每个格子中均有若干块财宝。每次从左上角出发，只能往右或下走，每次经过一个格子至多只能捡走一块财宝。问至少要走几次才可能把财宝全捡完。

$1 \leq n \leq 1000$ ， $1 \leq m \leq 1000$ ，每个格子中的财宝不超过 $1 0^{6}$ 块。

题解 DAG 的最小链覆盖数等于最大的点独立集大小。

不考虑网格图的点权，不难发现按给定的规则下在网格图上行走等价于在 DAG 上行走，从而我们可以将其视作 Hasse 图来构造偏序集，进而根据 Dilworth 定理有：

因此本题所求即为给定网格图最大点权独立集的点权和。

令 $a_{ij}$ 为网格图在点 $(i, j)$ 处的权值， $f (i, j)$ 为从 $(i, j)$ 到 $(1, m)$ 这个子网格中的答案，注意到每个点都和其右上角的点不相邻，则状态转移方程为：
$f (i, j) = max {f (i - 1, j), f (i, j + 1), f (i - 1, j + 1) + a_{ij}}$
答案即为 $f (n, 1)$ .
参考代码
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
  int t = 0;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<vector<int64_t>> a(n, vector<int64_t>(m));
    for (auto &i : a)
      for (auto &j : i) cin >> j;
    vector<vector<int64_t>> f(n, vector<int64_t>(m));
    for (int i = 0; i < n; ++i)
      for (int j = m - 1; j >= 0; --j)
        f[i][j] =
            max({(i == 0 ? 0 : f[i - 1][j]), (j == m - 1 ? 0 : f[i][j + 1]),
                 (i == 0 || j == m - 1 ? 0 : f[i - 1][j + 1]) + a[i][j]});
    cout << f[n - 1][0] << '\n';
  }
  return 0;
}

习题

C++ 中的应用

另请参阅：排序相关 STL - 算法基础。

C++ STL 中需要使用比较的算法和数据结构中有序理论的应用。我们经常需要在 C++ 中自定义比较器，STL 要求其必须为 严格弱序。令 $<$ 为自定义比较器，则可以定义：

$x > y$ 为 $y < x$ ；
$x \leq y$ 为 $y ≮ x$ ；
$x \geq y$ 为 $x ≮ y$ ；
$x = y$ 为 $x ≮ y \land y ≮ x$ .

Sean's Blog

Explorer

19.序理论

引入

定义

二元关系

关系间的运算

偏序集

偏序集的可视化表示：Hasse 图

链与反链

预序集中的特殊元素

有向集与格

对偶

Dilworth 定理与 Mirsky 定理

例题

习题

C++ 中的应用

参考资料与拓展阅读

目录

Graph View

反向链接