Hindman's theorem does not code $\emptyset^{(\omega)}$ in one application

技術要約：「ヒンドマンの定理は、一度の適用で $\emptyset^{(\omega)}$ をコードしない」

問題設定
本論文は、ヒンドマンの定理（HT）の計算論的複雑さ、特に、与えられた彩色に対する解の強さが、入力の彩色に対してどのような関係にあるかに焦点を当てている。ヒンドマンの定理は、自然数 $\mathbb{N}$ の有限個の彩色に対して、無限集合 $H$ が存在し、その要素の異なる非空な有限和の集合（$FS(H)$ と表記）が単色であることを述べている。

先行研究では以下の境界が確立されている：

1. 上界： Blass, Hirst, Simpson (1987) は、任意の計算可能な彩色に対して、$\emptyset^{(\omega)}$ から計算可能な解が存在することを証明した。
2. 下界： 同著者らは、計算可能な彩色において、すべての解が停止集合 $\emptyset'$ を計算することを示すことも証明した。後に、Liao (2026) はこれを改良し、特定の計算可能な彩色に対して、$\Pi^0_3$ 解が存在しないことを示した。

本論文が扱う中心的な未解決問題は、単一の適用における $\emptyset^{(\omega)}$ の上界が最適であるかどうかである。具体的には、「すべての算術的なヒンドマンの定理のインスタンスは、$\emptyset^{(\omega)}$ を計算しない解を持つか？」という問いである。

手法
著者らは、Towsnerによるヒンドマンの定理の組合せ論的な証明から適応された強制法（forcing technique）を用いている。この手法は以下の構成要素を含む：

1. 再定式化： 問題を、HTと計算可能に等価である有限和定理（FUT）の言語へと翻訳する。これは、自然数の非空な有限部分集合の集合 $P_{fin}(\mathbb{N})$ に対する彩色を扱い、有限和 $FU(H)$が単色となる無限ブロック列$H$ を求めるものである。
2. Towsnerツリーとマッチング： 著者らは、Towsnerの「ハーフマッチ（half-match）」および「フルマッチ（full-match）」の概念を利用する。有限集合 $F$ が無限ブロック列 $X$ に「ハーフマッチ」するとは、任意の有限和 $b \in FU(X)$ に対して、$f(a \cup b) = f(b)$ を満たす $a \in F$ が存在することを指す。 「フルマッチ」は、$f(a) = f(a \cup b) = f(b)$ を要求する。
   • 彼らは、「Towsnerシーケンス」と呼ばれる、ハーフマッチを入れ子状に構成したツリー構造（Towsnerツリー）を構築する。
   • 算術的な彩色 $f$ に対して、$f''$ 計算可能なTowsnerシーケンスが存在することを確立する。
3. 強制概念： 彩色に関連する特定の拡張特性を満たす「P条件（P-conditions）」、すなわち、有限個のブロック列の集合 $I$ と無限のリザーバー $X$ のペアを用いた、新しい強制概念を定義する。ある条件が「$f$-マッチング」であるとは、その彩色に関する特定の拡張性質を満たすことを意味する。
4. 第一ジャンプの制御： コアとなる革新は、特定の定義可能性特性を持つ「強制質問（forcing question）」の設計である。これにより、結果として得られる解 $G$ が、特定の非算術的な集合 $C$ を計算しないような生成的フィルター（generic filter）を構築することが可能になる。強制関係は、解の第一ジャンプを制御するように設計されており、解が入力に対する特定の算術的次数内に留まりつつ、ターゲットとなる錐（cone）を回避することを保証する。
5. 対角線論法： $C \not\leq_T G$ を保証するために、要件 $R^C_e: W^G_e \neq C$ を満たす。$\Sigma^0_1$ 論理式に対する強制質問を分析することで、いかなる非算術的な集合 $C$ に対しても、条件を拡張して $G$ がある要素において $C$ と異なるように強制できることを示す。

主要な貢献と結果

1. 主定理（錐回避）： 主要な結果（主定理 1.5）は以下の通りである：$C$ を非算術的な次数を持つ集合とする。任意の $\ell \geq 1$ および算術的な次数を持つ彩色 $f: \mathbb{N} \to \ell$ （または $P_{fin}(\mathbb{N}) \to \ell$）に対して、$FS(H)$が$f$-単色であり、かつ$C \not\leq_T H$を満たす無限集合$H$ が存在する。

   • 系： $C = \emptyset^{(\omega)}$ と設定することで、著者らは、すべての算術的なヒンドマンの定理のインスタンスが、$\emptyset^{(\omega)}$ を計算しない解を持つことを証明した。これは、単一の適用における計算論的な上界である $\emptyset^{(\omega)}$ が最適ではないことを示している。

2. 反復の限界： 著者らは、この結果が逆数学における $\text{ACA}^+_0$ よりもヒンドマンの定理が弱いことを意味するものではないことを明確にしている。錐回避はチューリング還元（$C \not\leq_T H$）については成立するが、算術的還元については必ずしも成立しないためである。したがって、この定理を反復して、$\emptyset^{(\omega)}$ を除外するヒンドマンの定理の $\omega$-モデルを構築することはできない。

3. 単純な彩色： 論文では、ヒンドマンの定理の制限としての「単純な彩色」（和の彩色が成分の彩色とその相対的な位置のみに依存する彩色）について調査している。

   • 彼らは、単純な彩色に対する有限和定理の制限が、$\text{RCA}_0$ 上で $\text{ACA}_0$ と等価であることを証明している。
   • また、Blass, Hirst, Simpson による下界の証明で使用された特定の彩色（「非常に短いギャップ」に基づくもの）が、単純な彩色であることを示している。

4. Towsnerツリーの複雑さ： 著者らは（命題 2.24）、Blass, Hirst, Simpson によって構築された特定の彩色に対して、すべてのTowsnerシーケンスが $\emptyset'$ を計算することを証明している。これは、Towsnerツリーが強力な道具である一方で、特定の計算可能な彩色に対してその存在自体が重大な計算能力を内在的に符号化していることを示唆している。ただし、これは他の証明や、そのようなツリーに依存しないフルマッチの存在を否定するものではない。

意義
本論文は、ヒンドマンの定理の単一の適用において、$\emptyset^{(\omega)}$ という上界がタイト（tight）であるかという問いに答えた。非算術的な錐を回避できることを証明することで、著者らは、算術的な入力に対して解を生成するために、ヒンドマンの定理が本質的に $\omega$-ジャンプの全能力を必要とするわけではないことを示した。これにより、定理の計算的内容の理解が洗練された。すなわち、ある解を見つけるために必要な複雑さと、特定の高い次数を持つ集合を計算する解を見つけるために必要な複雑さを区別したのである。また、本研究は、組合せ論的な証明（Towsnerの手法）と強制法を橋渡しすることで、解のチューリング次数に対して精密な制御を実現している。