無限組合せ論(infinitary combinatorics)とは、無限集合、特に非可算な基数の上の色分け、集合族の交わり方、木、閉非有界集合などの組合せ的な構造を調べる、集合論の分野である。可算の場合に成り立つ現象が非可算でどう変わるか、どの問いが ZFC で決まりどの問いが独立かが中心の問いになる。たとえば $\omega_1$-Aronszajn 木は ZFC で存在し、$\omega_1$-Suslin 木の存在は ZFC から独立である。
無限組合せ論(infinitary combinatorics)とは、無限集合、特に非可算な基数の上の色分け、集合族の交わり方、木、閉非有界集合などの組合せ的な構造を調べる、集合論の分野である。中心の問いは、有限の組合せ論や可算の場合に成り立つ現象が非可算でどう変わるか、そしてどの問いが ZFC で決まり、どの問いが ZFC から独立であるか、の 2 つである。
$\omega$ の上の組合せ論と $\omega_1$ の上の組合せ論は同じ形にならない。たとえば、$\omega$ の 2 点集合を 2 色に塗ると無限の単色集合があるが、$\omega_1$ では非可算の単色集合が見つかるとは限らない。また、分枝が有限の無限の木には無限の枝があるが、$\omega_1$ の場合は成り立たない。この記事は、こうした現象の地図である。Kun80 の Chapter II の冒頭では、この分野を独立性の証明が現れる前に集合論と呼ばれていた領域として説明している。
個別の記事がある概念は、1 文で述べる。色分けの記号は Ramseyの定理、$\Delta$-システムは Δ-システム、閉非有界集合は 定常集合、鎖条件は 可算鎖条件 が持つ。ここでは、この記事で使う 3 つを定義する。
木とは、半順序集合 $(T,\le)$ で、各 $x\in T$ の真の前者の集合 $\{y\mid y< x\}$ が整列されているものをいう。その順序型を $x$ の高さといい、高さ $\alpha$ の元の集合を第 $\alpha$ レベルという。レベルが空になる最小の順序数を $T$ の高さという。
$\kappa$ を正則基数とする。高さが $\kappa$ で、どのレベルも濃度が $\kappa$ 未満の木を $\kappa$-木という。濃度 $\kappa$ の鎖をもたない $\kappa$-木を $\kappa$-Aronszajn木 という。濃度 $\kappa$ で、鎖も反鎖も濃度が $\kappa$ 未満の木を $\kappa$-Suslin木 という。$\omega_1$-木で $\aleph_2$ 本以上の枝(各レベルと交わる鎖)をもつものを Kurepa 木(Aronszajn木)という(Kun80 Ch. II §5)。
これは、グラフとしての木とは別の概念である。
無限基数 $\kappa$ について、$\kappa$ の濃度 $\kappa$ の部分集合からなる族 $\mathcal A$ が概素族であるとは、相異なる $x,y\in\mathcal A$ について $|x\cap y|<\kappa$ であることをいう(Kun80 Ch. II Def. 1.1)。
$f,g\in\omega^\omega$ について、有限個の $k$ を除いて $f(k)< g(k)$ であることを $f<^*g$ と書く。族 $\mathcal F\subset\omega^\omega$ が非有界であるとは、すべての $f\in\mathcal F$ について $f<^*g$ となる $g$ がないことをいう。族 $\mathcal D\subset\omega^\omega$ が支配的であるとは、すべての $f\in\omega^\omega$ についてある $g\in\mathcal D$ で $f<^*g$ となることをいう。非有界な族の濃度の最小値を $\mathfrak b$、支配的な族の濃度の最小値を $\mathfrak d$ と書く。
$\mathfrak b$ と $\mathfrak d$ は、連続体の濃度以下の基数を実数の組合せで定める 基数不変量 の例である(Hal12 Ch. 8)。
| 問い | 代表的な結果 | 入る先 |
|---|---|---|
| 色分けに大きな単色集合はあるか | $\omega$ では常にある。$\omega_1$ では非可算の単色集合がない 2 色の塗り方がある | Ramseyの定理、弱コンパクト基数 |
| 色分けの性質をもつ非可算基数はあるか | 非可算な弱コンパクト基数はその性質で定義され、到達不能かつ木性質をもつことと同値 | 弱コンパクト基数 |
| 集合族から規則的な部分族を取れるか | 非可算個の有限集合の族は、非可算な $\Delta$-部分族を含む | Δ-システム |
| 組合せの補題は強制法でどう使うか | 値の集合が高々可算な有限部分関数の強制 $\operatorname{Fn}(I,J)$ は ccc である | Δ-システムと強制法の鎖条件、可算鎖条件 |
| 概素族はどこまで大きいか | $2^{<\kappa}=\kappa$ なら濃度 $2^\kappa$ の概素族がある | Kun80 Ch. II Thm 1.3 |
| 非可算の上で「大きい集合」は何か | 正則な非可算基数の定常集合上の退行的関数は、ある定常部分集合の上で定数になる(Fodor の補題) | 定常集合、閉非有界フィルター |
| 木に長い鎖はあるか | $\omega$-木には無限鎖がある。$\omega_1$-Aronszajn 木は ZFC で存在する | ex-ic-tree-counter、Aronszajn木 |
| $\omega_1$-Suslin 木は存在するか | ZFC から独立である。$\omega_1$-Suslin 木の存在は Suslin 直線の存在と同値 | Suslin木、Kun80 Ch. II Thm 5.13, Lemma 5.14, Thm 7.8 |
| Kurepa 木は存在するか | 組合せ原理 $\diamondsuit^+$ から存在が従う。存在しないことの無矛盾性は、到達不能基数の存在の無矛盾性と同値である | Aronszajn木、Kun80 Ch. II Cor. 7.11, Ch. VIII §3 |
| 実数の組合せの基数はどう並ぶか | $\aleph_1\le\mathfrak b\le\mathfrak d\le2^{\aleph_0}$ | prop-ic-b-d、Hal12 Ch. 8 |
| 基数の冪の組合せはどこまで ZFC で決まるか | 特異基数の冪には ZFC の上界がある | pcf理論、Königの定理 |
| フィルターの組合せは基数の強さとどう結ぶか | 可測基数は非主で $\kappa$-完備な超フィルターで定義される | 超フィルター、可測基数 |
非可算の問いの多くは、追加の組合せ原理のもとで答えが決まる。代表的な 2 つの方向を比べる。
| 仮定 | CH | $\omega_1$-Suslin 木 | 根拠 |
|---|---|---|---|
| $V=L$ | 成り立つ | 存在する | $L$ で $\diamondsuit$ が成り立つ(Kun80 Ch. VI §5) |
| $\diamondsuit$ | 成り立つ | 存在する | Kun80 Ch. II Lemma 7.2, Thm 7.8 |
| Martin の公理と $\neg$CH | 成り立たない | 存在しない | Martinの公理、Kun80 Ch. II Lemma 5.14 |
ここで $\diamondsuit$(ダイヤモンド原理)は、$A_\alpha\subset\alpha$($\alpha<\omega_1$)の列で、各 $A\subset\omega_1$ について $\{\alpha\mid A\cap\alpha=A_\alpha\}$ が定常になるものが存在するという原理である(Kun80 Ch. II Def. 7.1)。
最初の例は、基数不変量の基本の不等式の完全な証明である。
$\aleph_1\le\mathfrak b\le\mathfrak d\le2^{\aleph_0}$ である。
まず、$\omega^\omega$ は支配的かつ非有界なので、$\mathfrak b,\mathfrak d$ は定義され、$\mathfrak d\le|\omega^\omega|=2^{\aleph_0}$ である。実際、$f$ は $f+1$ に支配され、どの $g$ についても $g+1<^*g$ ではない。
$\aleph_1\le\mathfrak b$ を示す。高々可算な族 $\{g_i\mid i\in\omega\}$ をとり、$f(k)=\max_{i< k}g_i(k)+1$($f(0)=0$)とおく。$k>i$ なら $g_i(k)< f(k)$ だから、$g_i<^*f$ である。よって高々可算な族は非有界でない。
$\mathfrak b\le\mathfrak d$ を示す。$\mathcal D$ を支配的な族とする。$\mathcal D$ が非有界でないとすると、すべての $d\in\mathcal D$ について $d<^*g$ となる $g$ がある。$\mathcal D$ は支配的だから $g<^*d$ となる $d\in\mathcal D$ がある。すると有限個を除くすべての $k$ で $g(k)< d(k)< g(k)$ となり矛盾する。よって支配的な族は非有界であり、$\mathfrak b\le|\mathcal D|$ となる。
証明の鍵は、$f$ が $g_i$ を $k>i$ でしか抑えていないことである。次の反例は、この有限個の例外が欠かせないことを示す。
すべての $k$ で $f(k)< g(k)$ であることを $f< g$ と書き、$<^*$ を $<$ に置き換えて非有界な族の最小の濃度を考える。すると $\aleph_1\le\mathfrak b$ に当たる主張は成り立たない。
次の例は、$\omega$ と $\omega_1$ の差を木で見る。
$\omega$-木には無限鎖がある(König の補題、Kun80 Ch. II Lemma 5.7)。第 $0$ レベルは有限なので、上に無限個の元をもつ元 $x_0$ が取れる。$x_0$ の直後の元も有限個なので、同じ性質の $x_1>x_0$ が取れる。これを繰り返せば無限鎖ができる。
「$\kappa$-木には濃度 $\kappa$ の鎖がある」という含意は $\kappa=\omega_1$ で成り立たない。$\omega_1$-Aronszajn 木がその反例である(Aronszajn木 の定理「非可算の高さの反例」、Kun80 Ch. II Thm 5.9)。
| 段階 | 読む記事 | 得るもの |
|---|---|---|
| 1 | 基数、順序数、正則基数、Ramseyの定理 | 記号と可算の場合の見本 |
| 2 | Δ-システム、定常集合、閉非有界フィルター | 非可算の基本の道具 |
| 3 | 反鎖、可算鎖条件、Martinの公理 | 組合せと強制法の接点 |
| 4 | 超フィルター、弱コンパクト基数、可測基数 | 大きな基数の組合せ的な定義 |
| 5 | Eastonの定理、pcf理論 | 基数の冪の組合せ |
全体を 1 冊で読むなら、Kun80 の Chapter II が木と組合せ原理の標準の入口で、Hal12 が基数不変量と強制法の組合せに進む。
基数不変量の大小関係には、ZFC から証明できるか、独立かが分かっていないものが残る。Hal12 の各章の Related Results は、2012 年の時点で未解決の問題を含む項目に星印を付けて挙げている。有限の側では、$\Delta$-システムの有限版である向日葵予想が Δ-システム の記事で述べられている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する