Dilworthの定理

$C\cap A$ が相異なる 2 元 $x,y$ を含むとすると、$x,y\in C$ なので比較可能であり、$x,y\in A$ なので比較不能である。これは矛盾である。
$P=C_1\cup\cdots\cup C_m$ を鎖分割とし、$A$ を反鎖とする。前半により $|A|=\sum_i|A\cap C_i|\le m$ である。反鎖分割と鎖についても同様である。$\square$

$P=\emptyset$ なら明らかなので $P\ne\emptyset$ とする。各 $x\in P$ について、$x$ を最大元とする鎖の元の個数の最大値を $\ell(x)$ とする（$\{x\}$ がそのような鎖なので $\ell(x)\ge1$、また $\ell(x)\le h(P)$）。$j=1,\dots,h(P)$ について
$$ A_j:=\{x\in P\mid\ell(x)=j\} $$
とおくと、$P$ は $A_1,\dots,A_{h(P)}$ の互いに交わらない和集合である。各 $A_j$ は空でない。実際、元の個数 $h(P)$ の鎖 $c_1< c_2<\cdots< c_{h(P)}$ をとると、$c_1<\cdots< c_j$ は $c_j$ を最大元とする $j$ 元の鎖なので $\ell(c_j)\ge j$ であり、$\ell(c_j)>j$ なら $c_j$ を最大元とする $j+1$ 元以上の鎖に $c_{j+1},\dots,c_{h(P)}$ を付け加えて $h(P)$ 元より多い鎖ができるので、$\ell(c_j)=j$ である。
各 $A_j$ は反鎖である。$x,y\in A_j$ で $x< y$ とすると、$x$ を最大元とする $j$ 元の鎖に $y$ を付け加えたものは $y$ を最大元とする $j+1$ 元の鎖なので $\ell(y)\ge j+1$ となり、$y\in A_j$ に反する。
後半は lem-dilworth-theorem-meet から従う。$\square$

元の個数 $|P|$ に関する帰納法で示す。$P=\emptyset$ なら $0$ 個の鎖で分割できる。$P\ne\emptyset$ とし、元の個数が $|P|$ より少ない半順序集合では主張が成り立つとする。lem-dilworth-theorem-meet により、鎖分割の個数はいつも幅以上なので、$w(P)$ 個以下の鎖に分割できることを示せばよい。
$P$ の極大元 $a$ を 1 つとり（有限なので存在する）、$P':=P\setminus\{a\}$、$k:=w(P')$ とおく。帰納法の仮定により $P'=C_1\cup\cdots\cup C_k$ と $k$ 個の鎖に分割できる。$P'$ の元の個数 $k$ の反鎖は、lem-dilworth-theorem-meet により各 $C_i$ と高々 1 元を共有し、全部で $k$ 元をもつので、各 $C_i$ とちょうど 1 元を共有する。
$k\ge1$ のとき、各 $i$ について、$C_i$ の元のうち $P'$ の元の個数 $k$ のある反鎖に属するものの中で最大のものを $x_i$ とする（元の個数 $k$ の反鎖は存在し、$C_i$ と 1 元を共有するので、そのような元はある。$C_i$ は鎖なので最大のものが定まる）。$X:=\{x_1,\dots,x_k\}$ は反鎖である。実際、$x_i< x_j$ となる $i\ne j$ があるとし、$x_j$ を含む元の個数 $k$ の反鎖 $A$ をとる。$A$ と $C_i$ の共有元を $y$ とすると、$x_i$ の選び方から $y\le x_i$ であり、$y\le x_i< x_j$ となる。$y\in C_i$、$x_j\in C_j$ なので $y\ne x_j$ であり、$A$ の相異なる 2 元 $y,x_j$ が比較可能になって矛盾する。$k=0$ のときは $X:=\emptyset$ とする。
(a) $a$ が $X$ のどの元とも比較不能な場合。$X\cup\{a\}$ は元の個数 $k+1$ の反鎖なので $w(P)\ge k+1$ であり、$C_1,\dots,C_k,\{a\}$ は $P$ の $k+1$ 個の鎖への分割である。したがって $P$ は $w(P)$ 個以下の鎖に分割できる。
(b) $a$ がある $x_i$ と比較可能な場合。$a$ は極大元で $a\ne x_i$ なので $x_i< a$ である。
$$ K:=\{a\}\cup\{z\in C_i\mid z\le x_i\} $$
は鎖である（$C_i$ の元どうしは比較可能で、$z\le x_i< a$）。$P\setminus K$ に元の個数 $k$ の反鎖 $A$ があるとすると、$A\subset P'$ なので $A$ は $P'$ の元の個数 $k$ の反鎖であり、$C_i$ と 1 元 $y$ を共有する。$x_i$ の選び方から $y\le x_i$ なので $y\in K$ となり、$A\subset P\setminus K$ に反する。したがって $w(P\setminus K)\le k-1$ であり、帰納法の仮定により $P\setminus K$ は $k-1$ 個以下の鎖に分割できる。これに $K$ を加えると、$P$ は $k$ 個以下の鎖に分割できる。$w(P)\ge w(P')=k$ なので、$P$ は $w(P)$ 個以下の鎖に分割できる。$\square$

$P$ を有限半順序集合とする。$P$ の各元 $x$ に対して 2 つの頂点 $x^-$、$x^+$ を用意し、頂点集合 $P^-:=\{x^-\mid x\in P\}$ と $P^+:=\{x^+\mid x\in P\}$ をもち、$x< y$ のときに限り $x^-$ と $y^+$ を辺で結んだ二部グラフを $B$ とする。
マッチングから鎖分割を作る。 $M$ を $B$ のマッチングとする。$x^-y^+\in M$ のとき $y$ を $x$ の 後続、$x$ を $y$ の 先行 と呼ぶ。$M$ の辺は端点を共有しないので、各元の後続・先行はそれぞれ高々 1 つである。先行をもたない元 $x$ から後続をたどると $x< s(x)< s(s(x))<\cdots$ という列が得られ（$s$ は後続を表す）、$<$ は推移的で $z< z$ となる $z$ はないので同じ元は 2 度現れず、$P$ が有限なのでこの列は有限で止まる。どの元も、先行を逆にたどれば先行をもたない元に行き着くので、ちょうど 1 つの列に属する。各列は推移律により鎖である。したがって $P$ はこれらの列の個数個の鎖に分割される。列の個数は先行をもたない元の個数で、$M$ の各辺はちょうど 1 つの元に先行を与えるので、列の個数は $|P|-|M|$ である。$M$ を最大マッチングにとれば、$P$ は $|P|-\nu(B)$ 個の鎖に分割できる。
頂点被覆から反鎖を作る。 Königの定理により、大きさ $\nu(B)$ の頂点被覆 $T$ がある。
$$ A:=\{x\in P\mid x^-\notin T\text{ かつ }x^+\notin T\} $$
とおく。$T$ の各頂点は $A$ から高々 1 つの元を除くだけなので $|A|\ge|P|-|T|=|P|-\nu(B)$ である。$A$ は反鎖である。実際、$x,y\in A$ で $x< y$ なら、辺 $x^-y^+$ はどちらの端点も $T$ に属さず、$T$ が頂点被覆であることに反する。
以上と lem-dilworth-theorem-meet により
$$ w(P)\ge|A|\ge|P|-\nu(B)\ge(\text{鎖分割の最小の個数})\ge w(P) $$
であり、すべて等号である。特に $P$ は $w(P)$ 個の鎖に分割できる。$\square$

添字の集合 $\{1,\dots,N\}$ に、「$i\preceq j$ ⟺ $i\le j$ かつ $a_i\le a_j$」で半順序を入れる（反射律・反対称律・推移律は $\le$ の性質からすぐに確かめられる）。この半順序の鎖を添字の小さい順に並べると、対応する項は増加する。相異なる添字 $i< j$ が比較不能なら $a_i>a_j$ なので、反鎖を添字の小さい順に並べると、対応する項は減少する。
高さが $r+1$ 以上なら、元の個数 $r+1$ の鎖が長さ $r+1$ の増加部分列を与える。高さが $r$ 以下なら、thm-dilworth-theorem-mirsky により添字の集合は $r$ 個以下の反鎖に分割でき、鳩の巣原理によりある反鎖は $N/r$ 個以上の元をもつ。$N/r>s$ なので、それは $s+1$ 個以上である。それが長さ $s+1$ 以上の減少部分列を与える。$\square$