§E16.5Dilworth の定理

証明.$i=1,\dots,k$に対し$T_i=S_i\setminus(S_1\cup\dots\cup S_{i-1})$と定める（$i=1$のときは$T_1=S_1$とする）。$T_i\subseteq S_i$であるから仮定より$T_i\in\mathcal F$である。

$T_1,\dots,T_k$が互いに素であることを示す。$i<j$とすると、$T_j$の定義より$T_j\cap S_i=\varnothing$であり、$T_i\subseteq S_i$であるから$T_i\cap T_j=\varnothing$である。

$T_1\cup\dots\cup T_k=P$を示す。$T_i\subseteq S_i$より左辺は右辺に含まれる。逆に$x\in P$をとると$x\in S_1\cup\dots\cup S_k$であるから、$x\in S_i$を満たす添字のうち最小のものを$i$とすることができる。このとき$x\notin S_1\cup\dots\cup S_{i-1}$であるから$x\in T_i$である。

空である$T_i$を族から取り除けば、$\mathcal F$の元からなる$P$の分割であって、用いる集合の個数が$k$以下であるものを得る。

鎖$C$の部分集合の任意の二元は$C$の二元であるから比較可能であり、部分集合も鎖である。反鎖$A$の部分集合の相異なる二元は$A$の相異なる二元であるから比較不能であり、部分集合も反鎖である。したがって、鎖全体の族と反鎖全体の族はいずれも仮定を満たす。▨

証明. 最大反鎖の濃度を$w=\operatorname{w}(P)$とする。

（$\ge$）$\{C_1,\dots,C_m\}$を$P$の鎖被覆とし、$A$を濃度$w$の反鎖とする。鎖は反鎖の元を高々一つしか含まない。実際、同じ鎖の二元は比較可能であり、反鎖の相異なる二元は比較不能である。ゆえに$A$の$w$個の元は相異なる$w$本の鎖に分布し、$m\ge w$を得る。したがって$\operatorname{c}(P)\ge w$である。

（$\le$）$\lvert P\rvert$についての累積帰納法で、$P$が$w$本の鎖で覆われることを示す。$\lvert P\rvert=0$ならば$w=0$であり、空の族が鎖被覆を与える。以下$P\ne\varnothing$とする。

まず、空でない極大鎖、すなわち$C\ne\varnothing$であって$C$を真に含む鎖が存在しないような鎖$C$が存在することを示す。$P\ne\varnothing$であるから$x\in P$を取り、$C_0=\{x\}$と置く。一元集合は鎖であるから$C_0$は鎖である。$C_j$が鎖であるとき、$C_j\cup\{y\}$が鎖となる$y\in P\setminus C_j$が存在するかぎり、そのような$y$を一つ選んで$C_{j+1}=C_j\cup\{y\}$と定める。各段階で濃度が$1$ずつ増え、鎖の濃度は$\lvert P\rvert$以下であるから、この手続きは有限回で止まる。止まった時点の鎖を$C$とすると、$C\cup\{y\}$が鎖となる$y\in P\setminus C$は存在しない。ここで$C$を真に含む鎖$C'$が存在したとすると、$y\in C'\setminus C$を取れば$C\cup\{y\}\subseteq C'$は鎖となって矛盾する。ゆえに$C$は極大鎖であり、$C\supseteq C_0$より$C\ne\varnothing$である。

$C$は空でない有限集合であり、その任意の二元は比較可能である。空でない有限な鎖が最大元と最小元をもつことは、濃度についての帰納法から従う。実際、濃度が$1$ならばその唯一の元が最大元かつ最小元である。濃度が$2$以上のときは$z\in C$を一つ取り、帰納法の仮定より$C\setminus\{z\}$が最大元$m'$をもつから、$m'$と$z$の比較可能性により、$m'\le z$ならば$z$が、$z\le m'$ならば$m'$が$C$の最大元になる。最小元についても同様である。$C$の最大元を$m$、最小元を$\ell$と書く。

$m$は$P$の極大元である。実際、$m<y$を満たす$y\in P$が存在すれば、$C$の任意の元$u$について$u\le m<y$が成り立つので$C\cup\{y\}$は鎖となり、$y\notin C$（$y>m$かつ$m$は$C$の最大元）とあわせて$C$の極大性に反する。同様に$\ell$は$P$の極小元である。

$P':=P\setminus C$の幅で場合を分ける。$C\ne\varnothing$より$\lvert P'\rvert<\lvert P\rvert$である。

場合 1：$\operatorname{w}(P')\le w-1$のとき. 帰納法の仮定より$P'$は$w-1$本以下の鎖で覆われる。これに鎖$C$を加えれば、$P$は$w$本以下の鎖で覆われる。

場合 2：$P'$が濃度$w$の反鎖$A=\{a_1,\dots,a_w\}$を含むとき.$A$は$P$の反鎖でもあり濃度が$w$であるから、$P$の最大反鎖でもある。次の二集合を定める。$D^-=\{x\in P:\ x\le a_i\ \text{を満たす添字}\ i\ \text{が存在する}\},\qquad D^+=\{x\in P:\ x\ge a_i\ \text{を満たす添字}\ i\ \text{が存在する}\}.$

まず$D^-\cup D^+=P$を示す。$x\in P$がすべての$a_i$と比較不能であるとすると$A\cup\{x\}$は濃度$w+1$の反鎖となり、$w$が最大であることに反する。ゆえに$x$はある$a_i$と比較可能であり、$x\le a_i$または$x\ge a_i$が成り立つので$x\in D^-\cup D^+$である。

次に$D^-\cap D^+=A$を示す。$x\in D^-\cap D^+$とすると$x\le a_i$かつ$x\ge a_j$を満たす添字$i,j$が存在し、$a_j\le x\le a_i$から$a_j\le a_i$を得る。$A$は反鎖であるから$a_i=a_j$であり、$x\le a_i$かつ$x\ge a_i$から$x=a_i\in A$となる。逆の包含$A\subseteq D^-\cap D^+$は、各$a_i$が$a_i\le a_i$を満たすことによる。

$D^-$も$D^+$も$P$の真部分集合である。実際、$m\in D^-$と仮定すると$m\le a_i$を満たす添字$i$が存在し、$m$は$P$の極大元であるから$m=a_i$となる。しかし$m\in C$に対し$a_i\in P'=P\setminus C$であるから$m\ne a_i$であり、矛盾する。ゆえに$m\notin D^-$であり$D^-\subsetneq P$である。同様に、$\ell\ge a_j$を満たす添字$j$が存在すれば$\ell$が$P$の極小元であることから$\ell=a_j\in C$となって$a_j\in P'$に矛盾するので、$\ell\notin D^+$であり$D^+\subsetneq P$である。

$A\subseteq D^-$は濃度$w$の反鎖であり、$D^-$の反鎖は$P$の反鎖でもあるから、$D^-$の幅はちょうど$w$である。$D^-\subsetneq P$より帰納法の仮定を適用することができ、$D^-$は$w$本の鎖で覆われる。命題 1.2より、$w$本以下の鎖からなる$D^-$の分割が存在する。各鎖は反鎖$A$の元を高々一つしか含まないので、$A\subseteq D^-$の$w$個の元を覆うには$w$本以上の鎖が必要である。ゆえにこの分割はちょうど$w$本の鎖$E_1,\dots,E_w$からなり、各$E_i$はちょうど一つの$a_i$を含む（添字をそのように付け替える）。さらに$a_i$は$D^-$の極大元である。実際、$a_i<x$を満たす$x\in D^-$が存在すれば$x\le a_k$を満たす添字$k$があり$a_i<a_k$となって、$A$が反鎖であることに反する。

このことから、$a_i$は鎖$E_i$の最大元である。実際、$u\in E_i$を任意に取ると、$E_i$は鎖であり$a_i\in E_i$であるから$u$と$a_i$は比較可能であり、$u\le a_i$または$a_i\le u$が成り立つ。後者で$a_i\ne u$ならば$a_i<u$かつ$u\in E_i\subseteq D^-$となって、$a_i$が$D^-$の極大元であることに反する。ゆえに$u\le a_i$であり、$a_i$は$E_i$の最大元である。ここで極大性から最大性へ移ることができたのは、$E_i$が鎖であって$E_i$の任意の元が$a_i$と比較可能だからである。

$D^+$については、$P$の順序を逆にした半順序集合$(P,\ge)$を考える。$(P,\ge)$の鎖と反鎖は$(P,\le)$の鎖と反鎖に一致し、極大元と極小元の役割が入れ替わり、最大元と最小元の役割も入れ替わる。$(P,\ge)$において「$A$の元のいずれか以下である元の全体」は$\{x\in P:\ x\ge a_i\ \text{を満たす添字}\ i\ \text{が存在する}\}$、すなわち$D^+$に等しい。また$A$は$(P,\ge)$の濃度$w$の反鎖であり、$D^+\subsetneq P$である。帰納法の仮定は濃度が$\lvert P\rvert$より小さい有限半順序集合すべてについて適用することができ、鎖と反鎖の濃度は順序を逆にしても変わらない。

したがって、直前の二段落で$D^-$について示したことを$(P,\ge)$へ適用することができる。その結果、$D^+$はちょうど$w$本の鎖$F_1,\dots,F_w$に分割され、各$F_i$はちょうど一つの$a_i$を含み（添字は$E_i$と同じ番号を付ける）、$a_i$は$(P,\ge)$における$D^+$の極大元、すなわち$(P,\le)$における$D^+$の極小元であって、$(P,\le)$における$F_i$の最小元である。

各添字$i$について$E_i\cup F_i$を作る。$E_i$の任意の元$u$は$u\le a_i$を満たし、$F_i$の任意の元$v$は$a_i\le v$を満たすから、推移律より$u\le v$である。$E_i$と$F_i$はそれぞれ鎖であるから、$E_i\cup F_i$の任意の二元は比較可能であり、$E_i\cup F_i$は鎖である。

$E_i\cap F_i=\{a_i\}$を示す。$a_i$は$E_i$にも$F_i$にも属するから$\{a_i\}\subseteq E_i\cap F_i$である。逆に$x\in E_i\cap F_i$とすると$E_i\subseteq D^-$かつ$F_i\subseteq D^+$より$x\in D^-\cap D^+=A$であり、$x=a_j$を満たす添字$j$が存在する。$E_i$が含む$A$の元は$a_i$ただ一つであったから$a_j=a_i$、すなわち$x=a_i$である。ゆえに二本の鎖はちょうど$a_i$で継がれている。

これら$w$本の鎖の合併は$D^-\cup D^+=P$に等しく、$P$は$w$本の鎖で覆われる。

以上で両向きの不等式が示され、$\operatorname{c}(P)=w=\operatorname{w}(P)$を得る。▨

証明. 最長鎖の元数を$\ell=\operatorname{h}(P)$とする。

（$\ge$）$P$の反鎖被覆をとる。濃度$\ell$の鎖$C$の各元は相異なる反鎖に入らねばならない。実際、反鎖は鎖の元を高々一つしか含まない。ゆえに反鎖は少なくとも$\ell$本必要であり、$\operatorname{a}(P)\ge\ell$を得る。

（$\le$） 各$x\in P$に対し、$x$を最大元とする鎖の元数の最大値を$h(x)$とする。$\{x\}$自身が$x$を最大元とする濃度$1$の鎖であるから$h(x)$は定まり、$1\le h(x)\le\ell$が成り立つ。集合$A_k=\{x\in P:\ h(x)=k\}\qquad(k=1,\dots,\ell)$を考える。各$A_k$は反鎖である。実際、$x<y$かつ$h(x)=h(y)=k$と仮定すると、$x$を最大元とする濃度$k$の鎖$D$をとることができ、$D\cup\{y\}$は$y$を最大元とする濃度$k+1$の鎖となる。ここで$D\cup\{y\}$が鎖であることは、$D$の任意の元$z$が$z\le x<y$を満たすことによる。これは$h(y)\ge k+1>k$を与え、$h(y)=k$に矛盾する。

$h$の値はすべて$\{1,\dots,\ell\}$に属するから$A_1\cup\dots\cup A_\ell=P$であり、$A_1,\dots,A_\ell$は$P$の$\ell$本の反鎖被覆である。ゆえに$\operatorname{a}(P)\le\ell$である。

以上より$\operatorname{a}(P)=\ell=\operatorname{h}(P)$を得る。▨