Dilworth 定理证明

· · 个人记录

Dilworth 定理. 对于任意偏序 (S,\preceq)，最小链划分大小为 n，最长反链大小为 m，则有 n=m。

命题 1. 对于任意偏序 (S,\preceq)，最小链划分大小为 n，最长反链大小为 m，则有 n\geq m。

证明.

设此偏序任意最小链划分为 \{C_i\}，任意最长反链为 A。假设 n<m。则存在 x,y,i 满足 x,y\in A 且 x,y\in C_i，即 x,y 相互可比且不可比，矛盾，反证成立。

证毕.

定理 1. 对于任意偏序 (S,\preceq)，最小链划分大小为 n，最长反链大小为 m，则有 n=m。

证明.

采用归纳法。

当 |S|=1 时，易得 n=m=1。

下面讨论当 |S|>1 的情况：

设 |S|=l，则对于所有偏序 (S',\preceq) 满足 |S'|<l，n'=m' 成立。

在 S 中取任意极大元 x，显然 x 存在。对于偏序 (S-\{x\},\preceq)，最小链划分为 \{C_i\}，链 C_i 的第 j 大元素为 C_{ij}，最长反链集为 \{A_i\}。则有 |\{C_i\}|=|A_1|。则易得对于任意合法 i,j，满足集合 a_{ij}=C_i\cap A_j 大小为 1.

设集合 B=\{\forall i,\max a_{ij}\}。则 B\in \{A_i\}。证明：

假设 B\notin {A_i}。由于 |B|=|A_1|，存在 i,j,i',j' 满足 C_{ij},C_{i'j'}\in B，且 C_{i'j'}\preceq C_{ij}，且存在 k 满足 a_{ik}=C_{ij}。则 a_{i'k}\preceq C_{i'j'}\preceq C_{ij}=a_{ik}，即 a_{i'k},a_{ik} 相互可比。由于 a_{i'k},a_{ik}\in A_k，a_{i'k},a_{ik} 相互不可比，矛盾，反证成立。

情况 1: x 与 B 中任意元素不可比. 易证集合 B\cup \{x\} 是偏序 (S,\preceq) 上的一条反链，则 m\geq |A_1|+1。易证集合 \{C_i\}\cup \{\{x\}\} 是偏序 (S,\preceq) 上的一个链剖分集合，则 n\leq |\{C_i\}|+1=|A_1|+1。由 命题 1. 可知，n\geq m 成立，解得 n=m=|A_1|+1。

情况 2: 存在 i,j 满足 C_{ij}\in B 且 C_{ij},x 互相可比. 由于 x 是偏序 (S,\preceq) 上的极大元，C_{ij}\preceq x。设集合 U=\{\forall 1\leq k\leq j,C_{ik}\}\cup \{x\}，则 U 是偏序 (S,\preceq) 上的一条链。对于偏序 (S-U,\preceq)，最小链划分为 \{C'_i\}，最长反链大小为 m'。则有 m'\leq |A_1|-1，证明：

假设 m'\geq |A_1|。设 A' 为偏序 (S-U,\preceq) 上的一条反链，由于 x\in U，故 S-U\subseteq S-\{x\}，则存在 k 满足 A'=A_k，故 a_{ik}\in A'。由于 a_{ik}\preceq C_{ij}，a_{ik}\in U，a_{ik}\notin S-U，由于 A'\subseteq S-U，a_{ik}\notin A'，矛盾，反证成立。

由于 B-\{C_{ij}\}\subseteq S-U，B-{C_{ij}} 为偏序 (S-U,\preceq) 上的一条反链，故 m'\geq |A_1|-1，解得 m'=|A_1|-1。由于 U\ne \varnothing，|S-U|<|S|=l，|\{C'_i\}|=m'=|A_1|-1，易证集合 {C'_i}\cup \{U\} 为偏序 (S,\preceq) 上的一组链剖分，故 n\leq |\{C'_i\}|+1 =|A_1|。易证集合 B 是偏序 (S,\preceq) 上的一条反链，故 m\geq |B|=|A_1|。由 命题 1. 可知，n\geq m 成立，解得 n=m=|A_1|。

证毕.

参考：http://aleph.math.louisville.edu/teaching/2009FA-681/notes-091119.pdf