狄尔沃斯定理

定理 对任何有限偏序$P$，设$k_1$是满足以下条件得最小值：存在$k_1$个全序集$C_1,...,C_{k_1}\subset P$，它们的并是$P$。设$k_2$是满足以下条件的最大值：存在$k_2$个元素$a_1,...,a_{k_2}\in P$，它们两两之间无法比较。那么$k_1=k_2$。

显然，$k_1$个全序集无论是否要求互不相交，不影响结果。

（注意，$k_1\geq k_2$是显然的。）

证明（来自维基百科）
考虑对$P$的大小使用归纳法。

$P$如果是空的，命题显然成立。

$P$如果不是空的，设$a$是$P$的一个极大元，根据归纳假设，$P':=P\setminus\{a\}$可以被拆成不交全序$C_1,...,C_k$的并，并且存在大小为$k$的不可比较集$A_0$。显然，$A_0\cap C_i\neq\varnothing,\forall i=1,2,...,k$。对于$i=1,...,k$，设$x_i$是$C_i$中满足以下条件的最大元：$x_i$能作为$P'$中某个大小为$k$的不可比较集的元素。设$A=\{x_1,x_2,...,x_k\}$。现在说明$A$是一个不可比较集。设$A_i$是一个大小为$k$且有$x_i$的不可比较集。任取不相等的下标$i$和$j$。于是$A_i\cap C_j\neq\varnothing$。设$y\in A_i\cap C_j$。那么根据$x_j$的定义可知$y\leq x_j$。由于$x_i\not\geq y$，这意味着$x_i\not\geq x_j$。交换$i$和$j$的角色就可知道$x_j\not\geq x_i$。这就得出了$A$是不可比较集。
现在回到$P$。假设对于某$i\in\{1,2,...,k\}$，$a\geq x_i$。设$K$是全序$\{a\}\cup\{z\in C_i:z\leq x_i\}$。于是根据$x_i$的选取，$P\setminus K$不具有大小为$k$的不可比较集。根据归纳假设可知$P\setminus K$可以被$k-1$个不交全序覆盖，由于$A\setminus\{x_i\}$是$P\setminus K$中大小为$k-1$的不可比较集。于是，$P$可以被$k$个不交全序覆盖。接着，如果对任何$i\in\{1,2,...,k\}$，$a\not\geq x_i$，那么$A\cup\{a\}$就是$P$的大小为$k+1$的不可比较集。而$P$能被$k+1$个全序$\{a\},C_1,C_2,...,C_k$所覆盖。