Königの定理
概要
Königの定理（König's theorem）とは、基数の族がすべての添字 $i$ で $\kappa_i<\lambda_i$ を満たすなら $\sum_{i\in I}\kappa_i<\prod_{i\in I}\lambda_i$ が成り立つという基数算術の定理である。積の第 $i$ 座標で和の第 $i$ 成分を避ける対角線論法で証明され、$\kappa_i=1$、$\lambda_i=2$ とすると Cantor の不等式 $\kappa<2^\kappa$ になる。無限基数 $\mu$ について $\mu<\mu^{\operatorname{cf}(\mu)}$ と $\operatorname{cf}(2^\kappa)>\kappa$ を導き、$2^{\aleph_0}\ne\aleph_\omega$ を ZFC で示す。集合の言葉で述べた形は選択公理と同値である。
König の定理とは
集合論の König の定理（König's theorem）は、基数の和と積のあいだに厳密な不等式を与える定理である。添字集合 $I$ の各 $i$ で $\kappa_i<\lambda_i$ なら、$\kappa_i$ をすべて足した基数より、$\lambda_i$ をすべて掛けた基数の方が真に大きい。
有限個の自然数なら、この不等式は数の計算でも確かめられる。しかし無限基数では、和も積も「最大の項」や「項の個数」に吸収されることが多い。たとえば $\sum_{n<\omega}n=\aleph_0=\sum_{n<\omega}(n+1)$ であり、$2^{\aleph_0}=3^{\aleph_0}$ である。各項の大小が和どうし・積どうしの大小に遺伝しないなかで、「和と積を比べる」ときだけは厳密な不等式が必ず残る。その理由は Cantor の対角線論法と同じ仕組みにある（定理の形と証明は Hal12 Theorem 5.11、pp. 126–127）。
この定理の主な使い道は、冪の基数に対する制約である。とくに $\operatorname{cf}(2^{\kappa})>\kappa$ が導かれ、連続体の濃度 $2^{\aleph_0}$ が $\aleph_\omega$ に等しくないことが ZFC で証明できる。
以下、断らない限り選択公理を含む ZFC で考える。基数は初期順序数（それより小さい順序数と対等にならない順序数）と同一視する。
基数の和と積
集合 $I$ で添字づけた基数の族 $(\kappa_i)_{i\in I}$ に対し、
$$ \sum_{i\in I}\kappa_i:=\Bigl|\,\bigcup_{i\in I}\{i\}\times\kappa_i\,\Bigr|,\qquad \prod_{i\in I}\kappa_i:=\Bigl|\,\{\,g\colon I\to\textstyle\bigcup_{i\in I}\kappa_i\mid \text{すべての } i\in I \text{ で } g(i)\in\kappa_i\,\}\,\Bigr| $$
と定める。右辺の集合をそれぞれ $\bigsqcup_{i\in I}\kappa_i$（直和）、$\prod_{i\in I}\kappa_i$（直積）と書く。
直和では、添字 $i$ を付けて各 $\kappa_i$ の写しを互いに交わらないように並べている。直積の元は、各座標 $i$ で $\kappa_i$ の元を 1 つずつ選んだ選び方である。$I=\emptyset$ のとき、和は $0$、積は空写像 1 個だけからなる集合の濃度 $1$ である。
基数を、それと対等な集合 $A_i$ に取り替えても、和と積の濃度は変わらない。各 $i$ で全単射 $A_i\to\kappa_i$ を 1 つずつ選べば、直和どうし・直積どうしの全単射が得られるからである。この「各 $i$ で 1 つずつ選ぶ」ところで選択公理を使う。
$I=\{0,1\}$、$(\kappa_0,\kappa_1)=(1,2)$、$(\lambda_0,\lambda_1)=(2,3)$ なら、和は $1+2=3$、積は $2\cdot3=6$ で、$3<6$ である。
$I=\omega$、すべての $n$ で $\kappa_n=1$、$\lambda_n=2$ なら、和は $\lvert\omega\rvert=\aleph_0$、積は $0,1$ の列全体の濃度 $2^{\aleph_0}$ である。
$I=\omega$、$\kappa_n=n$、$\lambda_n=\aleph_n$ なら、和は $\aleph_0$、積は $\prod_{n<\omega}\aleph_n$ である。後者は $\aleph_\omega$ 以上の基数で、下の定理から $\aleph_0<\prod_{n<\omega}\aleph_n$ が分かる。
主定理
集合 $I$ で添字づけた基数の族 $(\kappa_i)_{i\in I}$、$(\lambda_i)_{i\in I}$ が、すべての $i\in I$ で $\kappa_i<\lambda_i$ を満たすとする。このとき
$$ \sum_{i\in I}\kappa_i<\prod_{i\in I}\lambda_i $$
である。
$D:=\bigsqcup_{i\in I}\kappa_i$、$P:=\prod_{i\in I}\lambda_i$ とおく。
段 1（$P$ は空でない）． 各 $i$ で $\kappa_i<\lambda_i$ だから $\lambda_i\ge1$ であり、$0\in\lambda_i$ である。よって $g(i):=0$ で定まる $g$ は $P$ の元である。
段 2（$D$ から $P$ への全射はない）． 全射 $F\colon D\to P$ があったとする。各 $i\in I$ について、第 $i$ 成分 $\{i\}\times\kappa_i$ の像の第 $i$ 座標を集めた
$$ S_i:=\{\,F(i,\alpha)(i)\mid \alpha<\kappa_i\,\}\subset\lambda_i $$
を考える。$\alpha\mapsto F(i,\alpha)(i)$ は $\kappa_i$ から $S_i$ への全射なので $\lvert S_i\rvert\le\kappa_i<\lambda_i$ であり、$S_i\ne\lambda_i$ である。そこで $g(i)$ を $\lambda_i\setminus S_i$ の最小元と定めると $g\in P$ である。$F$ は全射だから、ある $(j,\alpha)\in D$ で $g=F(j,\alpha)$ となる。第 $j$ 座標を見ると $g(j)=F(j,\alpha)(j)\in S_j$ だが、$g(j)$ は $S_j$ に属さないように選んだ。これは矛盾である。
段 3（結論）． 基数は比較可能なので、$\lvert D\rvert<\lvert P\rvert$ でなければ $\lvert P\rvert\le\lvert D\rvert$ である。このとき単射 $h\colon P\to D$ があり、段 1 の $g_0\in P$ を用いて、$d\in h[P]$ なら $d\mapsto h^{-1}(d)$、それ以外なら $d\mapsto g_0$ と定めれば $D$ から $P$ への全射ができる（$D=\emptyset$ なら $h$ は存在しない）。これは段 2 に反する。よって $\sum_{i}\kappa_i=\lvert D\rvert<\lvert P\rvert=\prod_i\lambda_i$ である。$\square$
段 2 は対角線論法である。和の第 $i$ 成分から来る元は「第 $i$ 座標」だけで見張られ、そこで $\lambda_i$ の元を $\kappa_i$ 個しか使えない。$\kappa_i<\lambda_i$ だから見張りをすり抜ける値 $g(i)$ が残り、それらを並べた $g$ はどの成分からも来ていない。段 2 の $g$ の定義で「最小元」を取れたのは $\lambda_i$ が順序数だからで、ここでは選択公理を使っていない。選択公理を使ったのは、基数の比較可能性（段 3）と、和と積が代表の取り方によらないこと（前節）である。
仮定を外すと何が起きるか
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 各項で厳密に $\kappa_i<\lambda_i$（等号を許す） | $I=\omega$、$\kappa_n=\lambda_n=1$ | 和 $<$ 積（実際は和 $\aleph_0$ が積 $1$ より大きい） |
| すべての $i$ で $\kappa_i<\lambda_i$（1 か所だけ等号） | $I=\{0,1\}$、$(\kappa_0,\kappa_1)=(\aleph_1,0)$、$(\lambda_0,\lambda_1)=(\aleph_1,1)$ | 和 $<$ 積（実際は和と積がともに $\aleph_1$） |
| 和と積を比べる（和どうしにする） | $\kappa_n=n$、$\lambda_n=n+1$（$n<\omega$） | $\sum\kappa_n<\sum\lambda_n$ |
| 和と積を比べる（積どうしにする） | $\kappa_n=2$、$\lambda_n=3$（$n<\omega$） | $\prod\kappa_n<\prod\lambda_n$ |
1 行目：和は $\bigsqcup_{n<\omega}1=\omega\times\{0\}$ の濃度 $\aleph_0$、積は各座標の値が $0$ しかない写像 1 個で $1$ である。厳密不等式どころか $\le$ も成り立たない。等号の項が $1$ だと、和には $1$ ずつ効くが積には何も効かないからである。
2 行目：和は $\aleph_1+0=\aleph_1$、積は $\aleph_1\cdot1=\aleph_1$ で等しい。1 か所の等号だけで厳密さが失われる。
3 行目：どちらの和も、可算個の有限集合の和なので $\aleph_0$ である（各項は $0$ または正で、総和は無限）。各項の大小は和どうしの厳密な大小を与えない。
4 行目：$2^{\aleph_0}\le3^{\aleph_0}\le(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$ なので両者は等しい。積どうしでも厳密な大小は遺伝しない。
König の定理は、「小さい方を足し、大きい方を掛ける」という非対称な比較にしたときだけ厳密さが保たれることを述べている。
選択公理との関係
König の定理を、基数でなく集合の言葉で述べ直す。集合 $A,B$ について $\lvert A\rvert<\lvert B\rvert$ とは、単射 $A\to B$ があり、全単射 $A\to B$ がないことをいう。
ZF で次の主張 (K) を仮定する：集合の族 $(A_i)_{i\in I}$、$(B_i)_{i\in I}$ がすべての $i$ で $\lvert A_i\rvert<\lvert B_i\rvert$ を満たすなら、$\lvert\bigsqcup_{i}A_i\rvert<\lvert\prod_{i}B_i\rvert$ である。このとき、空でない集合の族 $(B_i)_{i\in I}$ の直積 $\prod_iB_i$ は空でない。すなわち選択公理が成り立つ。
各 $i$ で $A_i:=\emptyset$ とおく。空写像は単射 $\emptyset\to B_i$ であり、$B_i\ne\emptyset$ なので全単射 $\emptyset\to B_i$ はない。よって $\lvert A_i\rvert<\lvert B_i\rvert$ である。(K) から $\lvert\bigsqcup_iA_i\rvert<\lvert\prod_iB_i\rvert$ が従う。左辺の直和は空集合である。もし $\prod_iB_i=\emptyset$ なら、空写像が全単射 $\emptyset\to\prod_iB_i$ となり、厳密な不等式に反する。よって $\prod_iB_i\ne\emptyset$ である。$\square$
逆に選択公理のもとでは、各 $A_i$、$B_i$ をそれと対等な基数に置き換えられ（各 $i$ で全単射を 1 つずつ選ぶ）、(K) は主定理そのものになる。したがって、集合の言葉で述べた König の定理は選択公理と同値である（Hal12 p. 140 の注にも同じ指摘がある）。
Cantor の定理との関係
任意の基数 $\kappa$ について $\kappa<2^{\kappa}$ である。
$I=\kappa$、すべての $i$ で $\kappa_i=1$、$\lambda_i=2$ とおく。和は $\lvert\kappa\times\{0\}\rvert=\kappa$、積は $\kappa$ から $2=\{0,1\}$ への写像全体の濃度 $2^{\kappa}$ である。König の定理から $\kappa<2^{\kappa}$ を得る。$\square$
$2^\kappa$ は $\kappa$ の冪集合の濃度に等しい（部分集合とその特性写像が 1 対 1 に対応する）。冪集合を直接使う証明は 冪集合 の記事の「Cantorの定理」にある。König の定理の証明の段 2 を $\kappa_i=1$、$\lambda_i=2$ で書き下すと、$S_i$ は $F(i,0)(i)$ の 1 元だけからなり、$g(i)$ はその値を反転させたものになる。これは対角線論法そのものである。
| Cantor の対角線論法 | König の定理 | |
|---|---|---|
| 比べるもの | $\kappa$ と $2^\kappa$ | $\sum\kappa_i$ と $\prod\lambda_i$ |
| 第 $i$ 座標で避ける値の個数 | $1$ 個 | $\kappa_i$ 個 |
| 避けられる理由 | $1<2$ | $\kappa_i<\lambda_i$ |
| 作る元 | 対角線の値を反転した列 | $\lambda_i\setminus S_i$ の最小元を並べた写像 |
共終数への帰結
無限基数 $\mu$ の共終数 $\operatorname{cf}(\mu)$ は、$\mu$ より小さい順序数からなる列で上限が $\mu$ になるもののうち、最短の長さである。König の定理は、冪の形の基数の共終数を下から押さえる。
任意の無限基数 $\mu$ について $\mu<\mu^{\operatorname{cf}(\mu)}$ である。
$\lambda:=\operatorname{cf}(\mu)$ とし、上限が $\mu$ となる列 $(\mu_\xi)_{\xi<\lambda}$ で各 $\mu_\xi<\mu$ となるものをとる。$\mu$ は極限順序数だから $\mu=\bigcup_{\xi<\lambda}\mu_\xi$ である。各 $x\in\mu$ に、$x\in\mu_\xi$ となる最小の $\xi$ を $\xi(x)$ として対応させると、$x\mapsto(\xi(x),x)$ は $\mu$ から $\bigsqcup_{\xi<\lambda}\mu_\xi$ への単射である。よって
$$ \mu\le\sum_{\xi<\lambda}\lvert\mu_\xi\rvert<\prod_{\xi<\lambda}\mu=\mu^{\lambda} $$
である。2 つ目の不等号は、各 $\xi$ で $\lvert\mu_\xi\rvert\le\mu_\xi<\mu$ であることから König の定理を使った。$\square$
$\kappa$ を無限基数、$\lambda\ge2$ を基数とする。このとき $\operatorname{cf}(\lambda^{\kappa})>\kappa$ である。特に $\operatorname{cf}(2^{\kappa})>\kappa$ であり、$\operatorname{cf}(2^{\aleph_0})>\aleph_0$ である。
$\mu:=\lambda^{\kappa}$ とおく。$\mu\ge2^\kappa>\kappa$ なので $\mu$ は無限基数である。$\nu:=\operatorname{cf}(\mu)$ とし、$\nu\le\kappa$ と仮定して矛盾を導く。指数法則 $(\lambda^{\kappa})^{\kappa}=\lambda^{\kappa\cdot\kappa}$ と、無限基数の積 $\kappa\cdot\kappa=\kappa$ から
$$ \mu^{\nu}\le\mu^{\kappa}=(\lambda^{\kappa})^{\kappa}=\lambda^{\kappa\cdot\kappa}=\lambda^{\kappa}=\mu $$
となる（最初の不等号は $\nu\le\kappa$ と $\mu\ge1$ による）。一方、lem-konig-cf-power から $\mu<\mu^{\nu}$ である。これは矛盾である。よって $\operatorname{cf}(\lambda^\kappa)>\kappa$ である。$\square$
補題と、定理の $\lambda=2$ の場合は、Hal12 Corollary 5.12（p. 127）にも同じ形で証明がある。この結論は連続体仮説を仮定せずに ZFC だけで証明できる、連続体の濃度への数少ない制約である。
$\operatorname{cf}(\aleph_\omega)=\aleph_0$ なので（$\aleph_\omega$ は $\aleph_0,\aleph_1,\aleph_2,\dots$ の上限）、$2^{\aleph_0}\ne\aleph_\omega$ である。同じ理由で、$\aleph_{\omega+\omega}$ や $\aleph_{\omega_1+\omega}$ など、共終数が $\aleph_0$ の基数は $2^{\aleph_0}$ になれない。
一方、$\aleph_1$、$\aleph_{\omega+1}$ は正則（共終数が自分自身）であり、$\aleph_{\omega_1}$ の共終数は $\aleph_1$ なので、この定理はこれらを排除しない。$\kappa=\aleph_1$ に当てはめると $\operatorname{cf}(2^{\aleph_1})>\aleph_1$ となり、$2^{\aleph_1}\ne\aleph_{\omega_1}$ も分かる。
lem-konig-cf-power を $\mu=\aleph_\omega$ に当てはめると $\aleph_\omega<\aleph_\omega^{\aleph_0}$ である。$\aleph_\omega$ は可算個の小さい基数 $\aleph_n$ の上限なので、可算乗すると必ず真に大きくなる。一方 $\mu$ が正則なら $\mu^{\operatorname{cf}(\mu)}=\mu^\mu=2^\mu$ であり、補題は Cantor の不等式に戻る。
$2^{\aleph_0}$ の値が ZFC で決まらないこと（連続体仮説の独立性）は 連続体仮説 の記事の「連続体仮説の独立性」で扱う。König の定理が与えるのは $\operatorname{cf}(2^{\aleph_0})>\aleph_0$ という下からの制約であり、値を 1 つに決めるものではない。
注意
- ここでの König の定理は基数算術の定理である。二部グラフの最大マッチングと最小頂点被覆についての同名の定理、および無限木の無限枝についての König の補題とは別の主張である。
- König が証明したのは可算個の和と積の場合で、一般の形は Jourdain と Zermelo がそれぞれ独立に示した。そのため König–Jourdain–Zermelo の不等式とも呼ばれる（Hal12 p. 140）。
- 結論は厳密不等式である。前提の $\kappa_i<\lambda_i$ も厳密でなければならない（反例の表の 1・2 行目）。
- lem-konig-cf-power と thm-konig-cf-exponent は、「$\mu$ を $\operatorname{cf}(\mu)$ 個の小さい集合の和集合に書く」ことと、「$\lambda^\kappa$ は $\kappa$ 乗しても変わらない」ことを König の定理で突き合わせている。共終数の基本性質は 共終数 の記事にまとめてある。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
