無限組合せ論

数学において、無限組合せ論、あるいは組合せ集合論は、組合せ論の考え方を無限集合に拡張したものである。研究対象には、連続グラフや連続木、ラムゼーの定理の拡張、マーティンの公理などがある。最近の発展は、連続体の組合せ論^[1]と特異基数の継承者の組合せ論に関するものである。^[2]

順序数、基数（有限または無限）、自然数について 記述します。ErdősとRado（1956）は、次の記法を導入しまし た。${\displaystyle \kappa ,\lambda }$${\displaystyle m}$${\displaystyle n}$

${\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$

は、の- 要素部分集合の集合をに分割するたびに、順序型 の同次集合が成立することを簡潔に表す方法です。この場合の同次集合とは、 のすべての- 要素部分集合が分割の同じ要素に含まれるようなの部分集合です。 が 2 のときは、 は省略されることがよくあります。このようなステートメントは、分割関係として知られています。 ${\displaystyle [\kappa ]^{n}}$${\displaystyle n}$${\displaystyle \kappa}$${\displaystyle m}$${\displaystyle \lambda}$${\displaystyle \kappa}$${\displaystyle n}$${\displaystyle m}$

選択公理を仮定すると、となる順序数は存在しないので、は通常有限であるとみなされる。がほぼ無限であることが許される拡張は、次のように表記される。 ${\displaystyle \kappa}$${\displaystyle \kappa \rightarrow (\omega )^{\omega }}$${\displaystyle n}$${\displaystyle n}$

${\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{<\omega }}$

これは、 の有限部分集合の集合を部分に分割するたびに、 の順序型の部分集合が 個あり、任意の有限 に対して、サイズ の部分集合はすべて、分割の同じ要素に含まれるということを簡潔に表したものです。が 2 のときは、省略されることがよくあります。 ${\displaystyle \kappa}$${\displaystyle m}$${\displaystyle \lambda}$${\displaystyle n}$${\displaystyle n}$${\displaystyle m}$

もう一つのバリエーションは、

${\displaystyle \displaystyle \kappa \rightarrow (\lambda ,\mu )^{n}}$

これは、 の- 要素部分集合の2 色によるすべての色付けには、 のすべての要素が最初の色を持つような順序型の部分集合、または のすべての要素が 2 番目の色を持つような順序型の部分集合が含まれることを簡潔に表したものです。 ${\displaystyle [\kappa ]^{n}}$${\displaystyle n}$${\displaystyle \kappa}$${\displaystyle \lambda}$${\displaystyle [\lambda ]^{n}}$${\displaystyle \mu}$${\displaystyle [\mu ]^{n}}$

これには次のような特性があります: (以下は基数です) ${\displaystyle \kappa}$

${\displaystyle \displaystyle \aleph_{0}\rightarrow (\aleph_{0})_{k}^{n}}$すべての有限および（ラムゼーの定理）。${\displaystyle n}$${\displaystyle k}$

${\displaystyle \displaystyle \beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}}$（エルデシュ・ラドーの定理）

${\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}}$（シェルピンスキーの定理）

${\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (3)_{\kappa }^{2}}$

${\displaystyle \displaystyle \kappa \rightarrow (\kappa ,\aleph _{0})^{2}}$(エルデシュ・ドゥシュニク・ミラーの定理)

選択のない宇宙では、無限指数を持つ分割特性が成り立つ可能性があり、そのいくつかは決定性公理（AD）の結果として得られる。例えば、ドナルド・A・マーティンは、ADが

${\displaystyle \displaystyle \aleph _{1}\rightarrow (\aleph _{1})_{2}^{\aleph _{1}}}$

ヴァツワフ・シェルピンスキは、 であることを示して、ラムゼーの定理が の大きさの集合には拡張されないことを示した。つまり、シェルピンスキは、 の無数な実数部分集合のすべてに対して が両方の色を取るような、実数のペアを2 色に着色した。 の大きさの実数の任意の集合を取り、それにシェルピンスキの着色を適用すると、 が得られる。このような着色は強着色^[3]として知られ、集合論で研究されている。Erdős、Hajnal、Rado (1965) は、これに対して上記と同様の表記法を導入した。 ${\displaystyle \aleph _{1}}$${\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}}$${\displaystyle X}$${\displaystyle [X]^{2}}$${\displaystyle \aleph _{1}}$${\displaystyle \aleph _{1}\not \rightarrow (\aleph _{1})_{2}^{2}}$

序数、 基数（有限または無限）、自然数 について書きます。すると${\displaystyle \kappa ,\lambda }$${\displaystyle m}$${\displaystyle n}$

${\displaystyle \displaystyle \kappa \nrightarrow [\lambda ]_{m}^{n}}$

は、 の- 元部分集合の集合を、順序型のすべての集合がレインボー集合となるような部分に色付けすることが存在することを簡潔に述べたものです。この場合のレインボー集合は、すべての色を取るの部分集合です。が 2 のときは省略されることがよくあります。このようなステートメントは、負の角括弧の分割関係として知られています。 ${\displaystyle [\kappa ]^{n}}$${\displaystyle n}$${\displaystyle \kappa }$${\displaystyle m}$${\displaystyle \lambda }$${\displaystyle A}$${\displaystyle \kappa }$${\displaystyle [A]^{n}}$${\displaystyle m}$${\displaystyle m}$

もう一つのバリエーションは、

${\displaystyle \kappa \nrightarrow [\lambda ;\mu ]_{m}^{2}}$

これは、の 2 要素部分集合の集合の色付けが存在し、順序型 のすべての部分集合と順序型 のすべての部分集合に対して、集合がすべての色を取るということを簡潔に述べたものです。 ${\displaystyle [\kappa ]^{2}}$${\displaystyle \kappa }$${\displaystyle m}$${\displaystyle A}$${\displaystyle \lambda }$${\displaystyle B}$${\displaystyle \mu }$${\displaystyle A\times B}$${\displaystyle m}$

これには次のような特性があります: (以下は基数です) ${\displaystyle \kappa }$

${\displaystyle \displaystyle 2^{\kappa }\nrightarrow [\kappa ^{+}]^{2}}$（シェルピンスキ）

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]^{2}}$（シェルピンスキ）

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{3}^{2}}$（レーバー、ブラス）

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{4}^{2}}$（ガルビンとシェラ）

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}}$（トドルチェヴィッチ）

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1};\aleph _{1}]_{\aleph _{1}}^{2}}$（ムーア）

${\displaystyle \displaystyle 2^{\aleph _{0}}\nrightarrow [2^{\aleph _{0}}]_{\aleph _{0}}^{2}}$（ガルビンとシェラ）

この表記法を使用して、いくつかの大きな基数プロパティを定義できます。具体的には、次のようになります。

• 弱コンパクト基数 とは、${\displaystyle \kappa }$${\displaystyle \kappa \rightarrow (\kappa )^{2}}$
• α-エルデシュ基数 は、${\displaystyle \kappa }$${\displaystyle \kappa \rightarrow (\alpha )^{<\,\omega }}$
• ラムゼイ枢機卿は 満足させるものである${\displaystyle \kappa }$${\displaystyle \kappa \rightarrow (\kappa )^{<\,\omega }}$

• ダシュニク、ベン; ミラー、EW (1941)、「部分順序集合」、アメリカ数学誌、63 (3): 600–610、doi :10.2307/2371374、hdl : 10338.dmlcz/100377、ISSN  0002-9327、JSTOR  2371374、MR  0004862

• ポール・エルデシュ; Hajnal, アンドラーシュ州;ラドー、リチャード(1965)、「基数の分割関係」、Acta Math。アカド。科学。フン。、16 (1–2): 93–196、土井:10.1007/BF01886396、MR  0202613

• エルデシュ、ポール、ハイナル、アンドラス(1971)、「集合論における未解決問題」、公理的集合論 (カリフォルニア大学、カリフォルニア州ロサンゼルス、1967 年)、純粋数学シンポジウム講演集、第 XIII 巻第 1 部、プロビデンス、ロードアイランド州: アメリカ数学協会、pp. 17–48、MR  0280381
• ポール・エルデシュ; Hajnal, アンドラーシュ州;マテ、アッティラ; Rado、Richard (1984)、組合せ集合理論: 基数のための分配関係、論理学と数学の基礎の研究、vol. 2 106、アムステルダム: North-Holland Publishing Co.、ISBN 0-444-86157-2、MR  0795592
• Erdős, P. ; Rado, R. (1956)、「集合論における分割計算」(PDF)、Bull. Amer. Math. Soc.、62 (5): 427–489、doi : 10.1090/S0002-9904-1956-10036-0、MR  0081864
• 金森章宏(2000)、The Higher Infinite (第 2 版)、Springer、ISBN 3-540-00384-3
• クネン、ケネス（1980）、集合論：独立性証明入門、アムステルダム：北ホラント、ISBN 978-0-444-85401-8