現代数学解説

文献あり

半順序集合の高さと幅と階数

階数関数,順序

高さ・幅・最小鎖分割数・最小反鎖分割数

半順序集合$P$の部分集合$A$が反鎖 (antichain)であるとは、以下を満たすことを言う。

$\forall x,y \in A, x \le y \implies x = y$
(自身以外と順序関係を持たない)

半順序集合$P$の高さ (height)は、$P$の鎖の濃度の上限で定義される。
(上限が無限の場合は$\infty$とする。)
(※濃度-1で定義する流儀もある)

半順序集合$P$の幅 (width)は、$P$の反鎖の濃度の上限で定義される。
(上限が無限の場合は$\infty$とする。)

自然数$m$が半順序集合$P$の最小鎖分割数であるとは、以下を満たすことを言う。

$P$は$m$個の鎖による分割を持ち、$m$個未満の鎖による分割を持たない。

自然数$m$が半順序集合$P$の最小反鎖分割数であるとは、以下を満たすことを言う。

$P$は$m$個の反鎖による分割を持ち、$m$個未満の反鎖による分割を持たない。

任意の半順序集合は鎖分割・反鎖分割を持つ。

$P = \bigsqcup_{x \in P}\set{x}$とすればよい。

半順序集合$P$の最小鎖分割数が$m$のとき、$P$の幅は$m$以下である。

$P$ の $m$ 個の鎖による分割を $P = \bigsqcup_{k=1}^m T_k$ とする。
$A$ を $P$ の任意の反鎖とする。
反鎖の定義より、$A$ の任意の異なる2元は互いに比較不能である。
したがって、同じ鎖 $T_k$ が $A$ の元を2つ以上含むことはできない。
（もし含めば、それらは鎖の定義から比較可能になってしまい矛盾する）

これより、各鎖 $T_k$ ($k=1, \dots, m$) は $A$ の元を高々1つしか含まない。
したがって、反鎖 $A$ の濃度は鎖の個数 $m$ を超えることはできない。
$$\card{A} \le m$$
これが任意の反鎖 $A$ について成り立つため、反鎖の濃度の上限として定義される $P$ の幅もまた $m$ 以下である。

半順序集合$P$の最小反鎖分割数が$n$のとき、$P$の高さは$n$以下である。

$P$の$n$個の反鎖による分割を$P = \bigsqcup_{k=1}^n A_k$とする。
$C$を$P$の任意の鎖とする。
鎖の定義より、$C$の任意の異なる2元は互いに比較可能である。
したがって、同じ反鎖$A_k$が$C$の元を2つ以上含むことはできない。
（もし含めば、それらは反鎖の定義から比較不能でなければならず、矛盾する）

これより、各反鎖$A_k$ ($k=1, \dots, n$) は$C$の元を高々1つしか含まない。
したがって、鎖$C$の濃度は、分割を構成する反鎖の個数$n$を超えることはできない。
$$\card{C} \le n$$

これが任意の鎖$C$について成り立つため、鎖の濃度の上限である$P$自身の高さも$n$以下である。

Dilworthの定理・Mirskyの定理

$P$を半順序集合、$A \subset P$とする。

$↓^PA := \{x \in P\ |\ \exists a \in A; x \le a\}$
$↑^PA := \{x \in P\ |\ \exists a \in A; a \le x\}$

半順序集合$P$の反鎖$A$が包含関係で極大であることは以下と同値。

$\forall x \in P\setminus A, \exists y \in A; x \le y$または$y \le x$

両方の対偶を示す。

[$A$が極大でない ⇒ $\exists x \in P\setminus A; \forall y \in A, x \not\le y$かつ$y \not\le x$]
$A$を真に含む反鎖$A'$を取る。
$x \in A' \setminus A$を取ると、$A'$は反鎖だから、$\forall y \in A, x \not\le y$かつ$y \not\le x$

[$\exists x \in P \setminus A; \forall y \in A, x \not\le y$かつ$y \not\le x$ ⇒ $A$は極大でない]
そのような$x \in P$を取る。
$A \cup \set{x}$が$A$を包含する反鎖であるから、$A$は極大でない。

半順序集合$P$の極大反鎖を$A$とする。

このとき、$P = ↓^PA \ \cup ↑^PA$ が成り立つ。

即ち、$P$の任意の元は$A$のある元と比較可能である。

[$\supset$]
$\i$明らか。

[$\subset$]
$\i$$x \in P$を取る。
$\i$$x \in A$の場合は、$x \le x$だから$x \in ↓^PA$でok。
$\i$$x \in P \setminus A$の場合は、$A$は極大だから、
$\i$$\exists y \in A; x \le y$または$y \le x$より、$x \in ↓^PA$または$x \in ↑^PA$

有限半順序集合$P$が最小鎖分割 ($m$個の鎖に分割され、$m$個未満の鎖に分割されない)を持つならば、$P$は極大鎖を含む最小鎖分割を持つ。

$P = \bigsqcup_{k=1}^m T_k$を最小鎖分割とする。

$T_m$が極大鎖でないならば、$T_m \cup \{x\}$ が鎖となるような $x \in P$ が存在する。
$x \in T_i$ とするとき、$T_i$ を $T_i \setminus \{x\}$ に、$T_m$ を $T_m \cup \{x\}$ に置き換える操作を繰り返せば、
全体の分割数 $m$ を変えずに $T_m$ を極大鎖にできる。

$P$ を半順序集合とし、$A = \set{a_1,\dots,a_M}$ を $P$ の極大反鎖とする。

このとき、$↓^PA$ と $↑^PA$ がそれぞれ $M$ 個の鎖に分割可能であるならば、$P$ 全体も $M$ 個の鎖に分割可能である。

命題の仮定から$↓^PA,↑^PA$は$M$個の鎖に分割できる。

反鎖の異なる $a_i, a_j$ が同じ鎖に含まれることはないため、$↓^PA$ の鎖 $S_i^-$ が存在して、
$↓^PA = S_1^- \sqcup \cdots \sqcup S_M^-, \quad a_i \in S_i^-$
と表すことができ、$a_i$ は各鎖 $S_i^-$ の最大元となる。

同様に、
$↑^PA = S_1^+ \sqcup \cdots \sqcup S_M^+, \quad a_i \in S_i^+$
と表すことができ、$a_i$ は各鎖 $S_i^+$ の最小元となる。

ここで、$a_i$ を共通の結び目として2つの鎖を結合し、
$S_i = S_i^- \cup S_i^+$ という新しい鎖を作る。

これを $1, \dots ,M$ まで集めると、
$↓^PA\ \cup ↑^PA = S_1 \cup \cdots \cup S_M$
となる。

この時、$A$は極大反鎖であるから、$P = ↓^PA\ \cup ↑^PA$である。

[$(S_i)_{i=1}^M$は互いに素]
$\i$ある異なる$i,j \in \set{1,...,M}$が存在して、$S_i \cap S_j \not= \varnothing$と仮定する。
$\i$$x \in S_i \cap S_j$を取ると、$x$の所属先に以下のパターンが考えられる。

$\i$[$x \in S_i^-$ かつ $x \in S_j^-$ の場合]
$\ii$$↓^PA = S_1^- \sqcup \dots \sqcup S_M^-$だから、異なる鎖に同時に属することはなく、矛盾する。

$\i$[$x \in S_i^+$ かつ $x \in S_j^+$ の場合]
$\ii$上記と全く同様に、矛盾する。

$\i$[$x \in S_i^-$ かつ $x \in S_j^+$ の場合]
$\ii$$S_i^-$ は $a_i$ を最大元とする鎖だから、$x \le a_i$
$\ii$$S_j^+$ は $a_j$ を最小元とする鎖だから、$a_j \le x$
$\ii$順序の推移律により、$a_j \le a_i$
$\ii$しかし、$a_i$ と $a_j$ は反鎖の要素だから矛盾。

$\i$[$x \in S_i^+$ かつ $x \in S_j^-$ の場合]
$\ii$同様に$a_i \le a_j$ となり矛盾。

$\i$どのパターンでも矛盾する。

よって、全ての異なる$i,j \in \set{1,...,M}$に対し、$S_i \cap S_j = \varnothing$となる。

すなわち、$P = \bigsqcup_{i=1}^MS_i$

(Dilworth, 1950)

有限順序集合において、幅と最小鎖分割数は等しい。

「$\card{P} = n$なる半順序集合$P$は最小鎖分割数と幅が等しい」を全ての$n \in \N$で示す。
$n \in \N$に関する帰納法で示す。

[$n = 0$ のとき成り立つ]
$\i$$P$を空集合とし、$m$を$P$の最小鎖分割数、$M$を$P$の幅とする。
$\i$このとき、$m = M = 0$ となり成り立つ。

[任意の$k < n$で成り立つならば$n$で成り立つ]
$\i$$P$を$\card{P} = n$なる半順序集合とし、$m$を$P$の最小鎖分割数、$M$を$P$の幅とする。

$\i$[$m \ge M$]
$\ii$最小鎖分割を持つ半順序集合において成り立つ。

$\i$[$m \le M$]
$\ii$$P = \bigsqcup_{k=1}^m T_k$ を $P$ の最小個数の鎖への分割とする。
$\ii$補題より、$P$ の最小鎖分割を構成する $m$ 個の鎖のうち、
$\ii$1つの鎖 $T_m$ は極大鎖であるとしてよい。

$\ii$ここで、全体 $P$ から極大鎖 $T_m$ を除いた部分集合 $P' = P \setminus T_m$ を考える。
$\ii$$\card{P'} < \card{P} = n$ であるため、$P'$ に対して帰納法の仮定を適用できる。
$\ii$$P'$ の最小鎖分割数を $m'$、$P'$ の幅を $M'$ とすると、
$\ii$帰納法の仮定より $m' = M'$ が成り立つ。

$\ii$また、$P'$ の反鎖は全体 $P$ の反鎖でもあるため、明らかに $M' \le M$ である。
$\ii$これより、$M'$ が取りうる値は $M' < M$ または $M' = M$ の2通りに絞られる。
$\ii$以下、2つの場合についてそれぞれ $m \le M$ を導く。

$\ii$[$M' < M$ の場合]
$\iii$いま、$M' \le M -1$が成り立つ。

$\iii$$P'$は$P'=T_1 \sqcup \cdots \sqcup T_{m-1}$ によって $m-1$ 個の鎖に分割されている。
$\iii$もしこれより少ない個数の鎖への分割が存在すれば、
$\iii$それに $T_m$ を足すことで $P$ 全体も $m$ 未満の鎖で分割できることになり、
$\iii$$m$ の最小性に矛盾する。
$\iii$ゆえに、$P'$の最小鎖分割数$m'$は$m - 1$と等しい。

$\iii$したがって、以下の等式を得る。
$\iii$$m - 1 = M'$

$\iii$よって、
$\iii$$m - 1 = M' \le M - 1$
$\iii$となる。両辺に 1 を足すことで $m \le M$ が直ちに導かれる。

$\ii$[$M' = M$ の場合]
$\iii$$P'$ 内に存在する要素数 $M$ の反鎖を $A = \{a_1, \dots, a_M\}$ とする。
$\iii$$A$は極大反鎖である。

$\iii$$T_m$ は極大鎖であるため、$T_m$ の最大元は $↓^PA$ には含まれない。
$\iii$（もし含まれれば、ある $a_i$ に対して $\le a_i$ となり極大性に矛盾する）
$\iii$よって $\card{↓^PA} < \card{P}$ である。

$\iii$同様に、$T_m$ の最小元は $↑^PA$ には含まれないため $\card{↑^PA} < \card{P}$ である。

$\iii$$↓^PA,↑^PA$ は $A$ を丸ごと含むため幅は $M$ であり、
$\iii$よって、帰納法の仮定より、$↓^PA,↑^PA$は$M$個の鎖への分割を持つ。
$\iii$補題より、全体 $P$ が $M$ 個の鎖に分割できるため、
$\iii$最小鎖分割数 $m$ の定義から $m \le M$ が成り立つ。

$\ii$場合分けのいずれのルートを通っても $m \le M$ が示された。

$\i$よって、$m = M$ が成り立つ。

よって、数学的帰納法により、「$\card{P} = n$なる半順序集合$P$は最小鎖分割数と幅が等しい」が成り立つ。

(Mirsky)

有限半順序集合において、高さと最小反鎖分割数は等しい。

$P$を有限半順序集合、$n$を$P$の最小反鎖分割数、$N$を$P$の高さとする。

[$n \ge N$]
$\i$最小反鎖分割を持つ半順序集合において成り立つ。

[$n \le N$]
$\i$各元 $x \in P$ に対し、$x$ を極大元とする鎖の濃度の最大値を $h(x)$ と定義する。

$\i$$P$ の鎖の濃度の最大値は $N$ であるため、任意の $x \in P$ について $1 \le h(x) \le N$ である。

$\i$各 $k \in \{1, 2, \dots, N\}$ に対して、$P$ の部分集合 $A_k$ を $A_k = \{x \in P \mid h(x) = k\}$ と定める。
$\i$$P$ のすべての元は $A_1, \dots, A_N$ のいずれかただ1つに属するため、$P = \bigsqcup_{k=1}^N A_k$ が成り立つ。

$\i$次に、各 $A_k$ が反鎖であることを示す。
$\i$[$A_k$ に属する異なる2元 $x, y$ が比較可能であると仮定する]
$\ii$一般性を失わず $x < y$ とする。
$\ii$このとき、$x$ を極大元とする濃度 $k$ の鎖に $y$ を付け加えることで、
$\ii$濃度 $k+1$ の鎖を作ることができる。
$\ii$したがって、$y$ を極大元とする鎖の濃度の最大値 $h(y)$ は、$k+1$ 以上でなければならない。
$\ii$（$h(y) \ge k+1$）
$\ii$しかし、これは $y \in A_k$ （すなわち $h(y) = k$）であることに矛盾する。
$\i$ゆえに $A_k$ の任意の異なる2元は比較不能であり、各 $A_k$ は反鎖である。

$\i$以上より、$P$ は $N$ 個の反鎖による分割が構成できたため、最小反鎖分割数 $n$ は $N$ 以下である。

したがって、$n = N$ が示された。

半順序集合$P$において以下は同値。

$P$が有限の幅を持つ
$P$が有限個の鎖による分割を持つ

この時、$P$の幅と最小鎖分割数は一致する。

半順序集合$P$において以下は同値。

$P$が有限の高さを持つ
$P$が有限個の反鎖による分割を持つ

この時、$P$の高さと最小反鎖分割数は一致する。

らしい。。。

階数・次数

半順序集合$P$から鎖$C$への関数$\rho:P \to C$が$C$-階数関数 ($C$-rank function)であるとは、以下を満たすことを言う。

$\forall x,y \in P, x < y \implies \rho(x) < \rho(y)$
$\forall x,y \in P, x \prec y \implies \rho(y) \prec \rho(x)$

特に$C = \Z$のとき、単に階数関数と呼ぶ。

階数関数を持つ例 (Boole束)

$$\xymatrix{ & \{a,b,c\} \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] & \\ \{a,b\} \ar@{-}[d] \ar@{-}[dr] & \{a,c\} \ar@{-}[dl] \ar@{-}[dr] & \{b,c\} \ar@{-}[dl] \ar@{-}[d] \\ \{a\} \ar@{-}[dr] & \{b\} \ar@{-}[d] & \{c\} \ar@{-}[dl] \\ & \emptyset & }$$
各要素の要素数（濃度）がそのまま階数関数 $\rho$ となる。

階数関数を持たない例 (五角形束 $N_5$)

$$ \xymatrix{ & 1 \ar@{-}[dl] \ar@{-}[dr] & \\ b \ar@{-}[d] & & c \ar@{-}[ddl] \\ a \ar@{-}[dr] & & \\ & 0 & } $$

$0 \prec c \prec 1$ より $\rho(1) = \rho(0) + 2$ であるべきだが、左側の鎖 $0 \prec a \prec b \prec 1$ より $\rho(1) = \rho(0) + 3$ となり、矛盾するため階数関数は存在しない。

いくつかの性質を置いておく。

$P$ が階数関数を持つ。
$P$ が$\N$-階数関数を持つ。
任意の$x,y \in P$に対し、区間$[x,y]$の全ての極大鎖の濃度が等しい。(Jordan-Dedekindの鎖条件)
$P$ の全ての極大鎖の濃度が等しい。

半順序集合$P$の全ての鎖が有限集合であるとき、$P$は鎖有限であると言うことにする。
(ちなみにこれは$P$がACCとDCCを満たすことと同値。)

高さ有限ならば鎖有限である。

鎖有限で最小元を持つ半順序集合$P$において、1, 2, 3は同値である。

[1 $\implies$ 3]
$x,y \in P$を取る。

$x \not\le y$のとき、$[x,y] = \varnothing$であり、全ての極大鎖の濃度は $0$ で等しい。
$x = y$のとき、$[x,y] = \{x\}$であり、全ての極大鎖の濃度は $1$ で等しい。

$x < y$とする。

$[x,y]$の任意の極大鎖$C,D$を取る。

$P$は鎖有限だから、極大鎖の濃度は有限であり、次のように被覆関係で表せる。
$C: x = c_0 \prec c_1 \prec c_2 \prec \dots \prec c_m = y$
$D: x = d_0 \prec d_1 \prec d_2 \prec \dots \prec d_n = y$

いま、$P$は階数関数$\rho$を持つ。

階数関数の定義から、$c_i \prec c_{i+1}$ ごとに階数が $1$ 増えるため、$\rho(y) - \rho(x) = m$
同様に、$D$についても $\rho(y) - \rho(x) = n$

したがって $m = n$ となり、$[x,y]$の任意の極大鎖の濃度は等しい。

[3 $\implies$ 2]
$P$ は最小元 $0$ を持つ。
各 $x \in P$ に対して、関数 $\rho: P \to \N$ を
$\rho(x) := (\text{区間 } [0,x] \text{ の極大鎖の濃度})$

と定義する。条件3より $[0,x]$ の極大鎖の濃度はすべて等しく、$P$は鎖有限であるため、$\rho$ は well-defined である。

この $\rho$ が階数関数であることを示す。

$x \prec y$ のとき：
$[0,x]$ の極大鎖（濃度 $k = \rho(x)$）に $y$ を付加した鎖は、間に要素を挟めないため $[0,y]$ の極大鎖となる。その濃度は $k+1$ であるから、$\rho(y) = \rho(x) + 1$ が成り立つ。
$x < y$ のとき：
$[x,y]$ には濃度 $l \ge 2$ の極大鎖が存在する。$[0,x]$ の極大鎖と連結することで $[0,y]$ の極大鎖が得られ、その濃度は $\rho(x) + l - 1$ となる。ゆえに $\rho(y) = \rho(x) + l - 1 > \rho(x)$ が成り立つ。
よって $\rho$ は階数関数である。

[2 $\implies$ 1]
$\N$-階数関数は階数関数である。

鎖有限で有界な半順序集合$P$において、1, 2, 3, 4はすべて同値である。

[3 $\implies$ 4]
条件3は任意の区間で成り立つため、特に区間 $[0,1] = P$ についても成り立つ。

[4 $\implies$ 3]
条件4より、$P$のすべての極大鎖は等しい濃度 $L$ を持つ。

任意の区間 $[x,y]$ における2つの極大鎖 $C, D$ を取る。

$P$ は有界であるから、$[0,x]$ の極大鎖 $B$ と、$[y,1]$ の極大鎖 $T$ が存在する。
これらを連結した $C' = B \cup C \cup T$ および $D' = B \cup D \cup T$ は、どちらも $P$ 全体の極大鎖である。

ここで、$P$ は鎖有限であるため、すべての極大鎖の濃度は自然数である。
したがって、鎖の濃度について以下の加法性が成り立つ：
$$\card{C'} = \card{B} + \card{C} + \card{T} - 2$$
$$\card{D'} = \card{B} + \card{D} + \card{T} - 2$$

条件4より、全体の濃度は等しく $\card{C'} = \card{D'} = L$ である。
これらを代入して整理すると：
$$\card{C} = L - (\card{B} + \card{T}) + 2$$
$$\card{D} = L - (\card{B} + \card{T}) + 2$$
即ち $\card{C} = \card{D}$

よって、区間 $[x,y]$ の任意の極大鎖の濃度は等しく、条件3が示された。