構造的ラムゼー理論

数学において、構造ラムゼー理論はラムゼー理論のカテゴリ的一般化であり、ラムゼー理論の多くの重要な結果が「類似した」論理構造を持つという考えに基づいています。重要な観察は、これらのラムゼー型定理は、特定のカテゴリ（または有限構造のクラス）がラムゼー特性（以下に定義）を持つという主張として表現できることに注目することです。

構造ラムゼー理論は1970年代にネシェジルとレードルの研究から始まり^[1]、フライセ理論と密接に関係しています。2000年代半ばには、構造ラムゼー理論と位相力学を結び付けるケクリス・ペストフ・トドルチェヴィッチ対応の発見により、新たな関心を集めました。

Leeb  [de]は1970 年代初頭に Ramsey 性質というアイデアを考案したことで知られています^[2] 。このアイデアの最初の発表は、このテーマに関するGraham、Leeb、Rothschildの 1972 年の論文のようです^[3] 。これらのアイデアの重要な展開は、NešetřilとRödlによる一連の 1977 年^[4]および 1983 年^{[5]の論文で行われ、有名な Nešetřil–Rödl 定理も含まれています。この結果は Abramson と}Harrington ^[6]によって独立に証明され、Prömel  [de]によってさらに一般化されました^[7]。より最近では、Mašulović ^{[8] [9] [10]}と Solecki ^{[11] [12] [13] が}この分野で先駆的な研究を行っています。

この記事では、各自然数はそれより小さいすべての自然数の集合として考えることができるという集合論の慣例を使用します。つまり、 です。任意の集合 に対して、の -色付けは、の各要素にラベルの 1 つを割り当てることです。これは、各要素を のラベルにマッピングする関数 (この記事で使用) として表すことができます。または、 を部分に分割することと同等です。 ${\displaystyle n\in \mathbb {N} }$${\displaystyle n=\{0,1,\ldots ,n-1\}}$${\displaystyle A}$${\displaystyle r}$${\displaystyle A}$${\displaystyle r}$${\displaystyle A}$${\displaystyle \Delta :A\to r}$${\displaystyle r=\{0,1,\ldots ,r-1\}}$${\displaystyle A=A_{0}\sqcup \cdots \sqcup A_{r-1}}$${\displaystyle r}$

ラムゼイ理論の典型的な結果のいくつかを以下に示します。

• (有限)ラムゼーの定理: 任意の に対して、 が存在し、のすべての-元部分集合の任意の-彩色に対して、を満たす部分集合 が存在し、 は-単色である。${\displaystyle k\leq m,r\in \mathbb {N} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle r}$${\displaystyle \Delta :[n]^{(k)}\to r}$${\displaystyle k}$${\displaystyle n=\{0,1,\ldots ,n-1\}}$${\displaystyle A\subseteq n}$${\displaystyle |A|=m}$${\displaystyle [A]^{(k)}}$${\displaystyle \Delta }$
• (有限)ファン デル ワールデンの定理: 任意の に対してが存在し、のすべての-色付けに対して、長さ の-単色等差数列が存在する。${\displaystyle m,r\in \mathbb {N} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle r}$${\displaystyle \Delta :n\to r}$${\displaystyle n}$${\displaystyle \Delta }$${\displaystyle \{a,a+d,a+2d,\ldots ,a+(m-1)d\}\subseteq n}$${\displaystyle m}$
• グラハム・ロスチャイルドの定理: 有限アルファベット を固定します。長さを超える-パラメータ語はの元であり、 がすべて出現し、初出は昇順になります。長さを超えるすべての- パラメータ語の集合は で表されます。および が与えられている場合、におけるのすべての出現を の番目の要素で置き換えることによって、それらの構成を形成します。すると、グラハム・ロスチャイルドの定理は、任意の に対して が存在し、長さ のすべての - パラメータ語のすべての- 彩色に対して が存在し、 (つまり のすべての- パラメータ部分語) は -単色になることを述べています。${\displaystyle L=\{a_{0},a_{1},\ldots ,a_{d-1}\}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle L}$${\displaystyle w\in (L\cup \{x_{0},x_{1},\ldots ,x_{k-1}\})^{n}}$${\displaystyle x_{i}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle L}$${\displaystyle \textstyle [L]{\binom {n}{k}}}$${\displaystyle \textstyle w\in [L]{\binom {n}{m}}}$${\displaystyle \textstyle v\in [L]{\binom {m}{k}}}$ ${\displaystyle \textstyle w\circ v\in [L]{\binom {n}{k}}}$${\displaystyle x_{i}}$${\displaystyle w}$${\displaystyle i}$${\displaystyle v}$
  ${\displaystyle k\leq m,r\in \mathbb {N} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle r}$${\displaystyle \textstyle \Delta :[L]{\binom {n}{k}}\to r}$${\displaystyle k}$${\displaystyle n}$${\displaystyle \textstyle w\in [L]{\binom {n}{m}}}$${\displaystyle \textstyle w\circ [L]{\binom {m}{k}}=\{w\circ v:v\in [L]{\binom {m}{k}}\}}$${\displaystyle k}$${\displaystyle w}$${\displaystyle \Delta }$
• (有限)フォークマンの定理: 任意の に対して、 が存在し、の任意の-彩色に対して、 を満たす部分集合 が存在し、 であり、 -単色である。${\displaystyle m,r\in \mathbb {N} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle r}$${\displaystyle \Delta :n\to r}$${\displaystyle n}$${\displaystyle A\subseteq n}$${\displaystyle |A|=m}$${\displaystyle \textstyle {\big (}\sum _{k\in A}k{\big )} <n}$${\displaystyle \textstyle \operatorname {FS} (A)=\{\sum _{k\in B}k:B\in {\mathcal {P}}(A)\setminus \varnothing \}}$${\displaystyle \Delta }$

これらの「ラムゼー型」の定理はすべて、同様の考え方に基づいています。つまり、2 つの整数と、および色のセット を固定します。次に、の内部でサイズ の「部分構造」のすべての -色付けに対して、 の内部でサイズ の適切な「構造」を見つけることができ、サイズのすべての「部分構造」が同じ色になるような、十分に大きい が存在することを示します。 ${\displaystyle k}$${\displaystyle m}$${\displaystyle r}$${\displaystyle n}$${\displaystyle r}$${\displaystyle k}$${\displaystyle n}$${\displaystyle A}$${\displaystyle n}$${\displaystyle m}$${\displaystyle B}$${\displaystyle A}$${\displaystyle k}$

どのようなタイプの構造が許可されるかは、問題の定理によって異なり、これが実質的にそれらの間の唯一の違いであることがわかります。この「ラムゼー型定理」という考え方から、ラムゼー特性 (以下) というより正確な概念が生まれます。

をカテゴリとする。がラムゼー特性を持つとは、任意の自然数および 内のすべてのオブジェクトに対して、 内の別のオブジェクトが存在し、任意の-彩色に対して、 -単色である射、すなわち集合 ${\displaystyle \mathbf {C} }$${\displaystyle \mathbf {C} }$${\displaystyle r}$${\displaystyle A,B}$${\displaystyle \mathbf {C} }$${\displaystyle D}$${\displaystyle \mathbf {C} }$${\displaystyle r}$${\displaystyle \Delta :\operatorname {Hom} (A,D)\to r}$ ${\displaystyle f:B\to D}$${\displaystyle \Delta }$

${\displaystyle f\circ \operatorname {Hom} (A,B)={\big \{}f\circ g:g\in \operatorname {Hom} (A,B){\big \}}}$

は単色である。^[10]${\displaystyle \Delta }$

多くの場合、は、埋め込みを射として持つ、あ​​る固定された言語上の有限 -構造のクラスであるとみなされます。この場合、射に色を付ける代わりに、内のの「コピー」に色を付けることを考えることができます。次に、内ののコピーをすべて単色にするような のコピーを見つけます。これは、以前の「ラムゼー型定理」の考え方に、より直感的につながります。 ${\displaystyle \mathbf {C} }$${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$${\displaystyle A}$${\displaystyle D}$${\displaystyle B}$${\displaystyle D}$${\displaystyle A}$${\displaystyle B}$

双対ラムゼー特性という概念もあります。 は、その双対カテゴリが上記のラムゼー特性を持つ場合、双対ラムゼー特性を持ちます。より具体的には、は、すべての自然数、および内のすべてのオブジェクトに対して、 内の別のオブジェクトが存在し、すべての-彩色に対して、が-単色である射が存在する場合、双対ラムゼー特性を持ちます。 ${\displaystyle \mathbf {C} }$ ${\displaystyle \mathbf {C} ^{\mathrm {op} }}$${\displaystyle \mathbf {C} }$${\displaystyle r}$${\displaystyle A,B}$${\displaystyle \mathbf {C} }$${\displaystyle D}$${\displaystyle \mathbf {C} }$${\displaystyle r}$${\displaystyle \Delta :\operatorname {Hom} (D,A)\to r}$ ${\displaystyle f:D\to B}$${\displaystyle \operatorname {Hom} (B,A)\circ f}$${\displaystyle \Delta }$

• ラムゼーの定理:順序保存写像を射として持つすべての有限鎖のクラスは、ラムゼー特性を持ちます。
• ファンデルワールデンの定理: オブジェクトが有限順序数であり、その射が 、に対するアフィン写像 であるカテゴリにおいて、に対してラムゼー特性が成り立ちます。${\displaystyle x\mapsto a+dx}$${\displaystyle a,d\in \mathbb {N} }$${\displaystyle d\neq 0}$${\displaystyle A=1}$
• ヘイルズ・ジュエットの定理：を有限アルファベットとし、各 に対して を変数の集合とします。 を、各 に対してオブジェクトがであり、に対する射 、が上で剛体かつ射影的な関数であるカテゴリとします。すると、は（定式化に応じて および ）に対して双対ラムゼー特性を持ちます。${\displaystyle L}$${\displaystyle k\in \mathbb {N} }$${\displaystyle X_{k}=\{x_{0},\ldots ,x_{k-1}\}}$${\displaystyle k}$${\displaystyle \mathbf {GR} }$${\displaystyle A_{k}=L\cup X_{k}}$${\displaystyle k\in \mathbb {N} }$${\displaystyle A_{n}\to A_{k}}$${\displaystyle n\geq k}$${\displaystyle f:X_{n}\to A_{k}}$${\displaystyle X_{k}\subseteq A_{k}=\operatorname {codom} f}$${\displaystyle \mathbf {GR} }$${\displaystyle A=A_{0}}$${\displaystyle B=A_{1}}$
• グラハム・ロスチャイルドの定理: 上記で定義されたカテゴリには、双対ラムゼー特性があります。${\displaystyle \mathbf {GR} }$

2005年にケクリス、ペストフ、トドルチェビッチ^[14]は、構造ラムゼー理論、フライセ理論、および位相力学のアイデアの間に 次の対応関係（以下、KPT対応と呼ぶ）を発見した。

を位相群とします。位相空間 に対して、-フロー( と表記) はから への連続的な作用です。コンパクト空間 上の任意の-フローが不動点を許容する場合、つまり の安定因子が自身である場合、 は極めて従順であると言えます。 ${\displaystyle G}$${\displaystyle X}$${\displaystyle G}$${\displaystyle G\curvearrowright X}$${\displaystyle G}$${\displaystyle X}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G\curvearrowright X}$${\displaystyle X}$ ${\displaystyle x\in X}$${\displaystyle x}$${\displaystyle G}$

フライセ構造 の場合、点収束の位相、またはそれと同等の、積位相 を持つ空間 によって に誘導される部分空間位相が与えられれば、その自己同型群は位相群と見なすことができます。次の定理は、KPT 対応を示しています。${\displaystyle \mathbf {F} }$${\displaystyle \operatorname {Aut} (\mathbf {F} )}$${\displaystyle \operatorname {Aut} (\mathbf {F} )}$${\displaystyle \mathbf {F} ^{\mathbf {F} }=\{f:\mathbf {F} \to \mathbf {F} \}}$

定理（KPT）。Fraïssé構造の場合、以下は同値です。 ${\displaystyle \mathbf {F} }$

1. の自己同型群は非常に従順です。${\displaystyle \operatorname {Aut} (\mathbf {F} )}$${\displaystyle \mathbf {F} }$
2. このクラスにはRamsey プロパティがあります。${\displaystyle \operatorname {Age} (\mathbf {F} )}$

• ラムゼー理論
• フレッセの定理
• 年齢（モデル理論）