無限組合せ論

同義語:infinitary combinatorics組合せ論的集合論combinatorial set theory

概要

無限組合せ論(infinitary combinatorics)とは、無限集合、特に非可算な基数の上の色分け、集合族の交わり方、木、閉非有界集合などの組合せ的な構造を調べる、集合論の分野である。可算の場合に成り立つ現象が非可算でどう変わるか、どの問いが ZFC で決まりどの問いが独立かが中心の問いになる。たとえば $\omega_1$-Aronszajn 木は ZFC で存在し、$\omega_1$-Suslin 木の存在は ZFC から独立である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 集合論, 基数, 順序数, Ramseyの定理

無限組合せ論(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$ に当たる主張は成り立たない。

  • 満たすこと:定数関数の族 $\{c_n\mid n\in\omega\}$($c_n(k)=n$)は高々可算である。
  • 満たさないこと:すべての $n$ で $c_n< g$ となる $g$ はない。$g(0)>n$ がすべての $n$ で必要になるからである。
  • 成り立たない含意:「高々可算な族は上界をもつ」という含意が成り立たず、この順序での最小の濃度は $\aleph_0$ に落ちる(Hal12 p. 192)。対角線の議論が有限個の例外を必要とすることが、$\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)。

  • 満たすこと:高さは $\omega_1$ で、どのレベルも高々可算である。
  • 満たさないこと:濃度 $\aleph_1$ の鎖がない。
  • 成り立たない含意:König の補題の議論は、極限の段で止まる。極限のレベルでは、それまでに選んだ鎖の上に元があるとは限らない。
    構成は、$\alpha< \omega_1$ について単射 $s_\alpha\colon\alpha\to\omega$ を、$\alpha<\beta$ で $s_\beta|_\alpha$ と $s_\alpha$ の差が有限個になり、値域の補集合が無限に残るように選び、それらと有限個の値だけ違う単射を集めるものである。非可算の鎖があれば、$\omega_1$ から $\omega$ への単射ができてしまう。

読み進め方

段階読む記事得るもの
1基数、順序数、正則基数、Ramseyの定理記号と可算の場合の見本
2Δ-システム、定常集合、閉非有界フィルター非可算の基本の道具
3反鎖、可算鎖条件、Martinの公理組合せと強制法の接点
4超フィルター、弱コンパクト基数、可測基数大きな基数の組合せ的な定義
5Eastonの定理、pcf理論基数の冪の組合せ

全体を 1 冊で読むなら、Kun80 の Chapter II が木と組合せ原理の標準の入口で、Hal12 が基数不変量と強制法の組合せに進む。

未解決問題

基数不変量の大小関係には、ZFC から証明できるか、独立かが分かっていないものが残る。Hal12 の各章の Related Results は、2012 年の時点で未解決の問題を含む項目に星印を付けて挙げている。有限の側では、$\Delta$-システムの有限版である向日葵予想が Δ-システム の記事で述べられている。

関連項目

参考文献

[1]
Kenneth Kunen, Set Theory: An Introduction to Independence Proofs, North-Holland (Studies in Logic and the Foundations of Mathematics 102), 1980, Ch. II(p. 47), Def. 1.1, Thm 1.3, §5(Lemma 5.7, Thm 5.9, Thm 5.13, Lemma 5.14), §7(Def. 7.1, Lemma 7.2, Thm 7.8, Cor. 7.11), Ch. VI §5, Ch. VIII §3
[2]
Lorenz J. Halbeisen, Combinatorial Set Theory, Springer, 2012, Preface, Chapter 8(pp. 189–), p. 192

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する