The reverse mathematics of the pigeonhole hierarchy

技術要約：鳩の巣原理の階層における逆数学

問題提起
$k$ 色に関する無限鳩の巣原理（$RT^1_k$）は、自然数の $k$ 分割に対して、分割クラスのいずれかに完全に含まれる無限部分集合が存在することを主張する。$RT^1_2$ はラムゼー理論の基礎であるが、その計算論的内容および逆数学的な強度は、インスタンスを算術的階層の特定のレベルに制限した場合、大きく変化する。

本論文は、インスタンスを $\Sigma^0_n$ および $\Delta^0_n$ 集合に制限することで定義される鳩の巣原理の階層（$\Sigma^0_n$-Subset および $\Delta^0_n$-Subset と表記）を調査する。中心となる問題は、これらの原理の正確な論理的強度と計算論的内容を決定することである。具体的には、この階層が厳密なものか（すなわち、$\Sigma^0_n$-Subset が $\Delta^0_{n+1}$-Subset および $\Delta^0_n$-Subset よりも厳密に強いか）を検討し、基底理論 $RCA_0$ におけるこれらの原理の一次の帰結を特徴付ける。先行研究である Benham ら [2] は、これらの原理と位相幾何学的定理（Ginsburg-Sands 定理）との関連性を確立したが、この階層の厳密性や、特定の基底定理（例：弱低度基底定理）の存在に関する問いを残した。

手法
著者らは、逆数学および計算理論の枠組みの中で、有効強制（effective forcing）の手法を用いる。核心となる手法は、Monin と Patey [32, 34] によって開発された**反復ジャンプ制御（iterated jump control）**であり、これにより、基底モデルの計算論的な弱さ（低度やハイパー免疫性など）を保持する解の構成が可能となる。

主な技術的構成要素は以下の通りである：

1. 木およびスコット・イデアルによる強制： 著者らは、リザーバー（貯蔵庫）がスコット・イデアル（チューリング還元および有効な結合に関して閉じている集合の集まり）に属する Mathias 強行法の変種を利用する。高次のジャンプ制御を実現するために、**ラージネス・タワー（largeness towers）およびスコット・タワー（Scott towers）**を導入する。これらはスコット・イデアルの階層であり、リザーバーが構成される集合について十分な正の情報を維持することを保証する「大きな」クラス（分割正則なクラス）に関連している。
2. 強制問題（Forcing Questions）： 特定の定義的複雑さを持つ強制問題の定義は、本研究の重要な革新である。クラス $\Gamma$ に対する強制問題を用いることで、解のジャンプの複雑さを増大させることなく、$\Gamma$ 性質を決定する構成が可能となる。著者らは以下を定義する：
   • メイン強制 ($MA^A_n$)： インスタンス集合 $A$ が特定の分割正則なクラスに属する場合に使用される。
   • ウィットネス強制 ($WA^A_n$)： $A$ がそのクラスに属さない場合、構成を導くための「ウィットネス」（$A$ を除外する大きなクラス）を必要とする。
   • 選言強制 ($DA^A_n$)： 異なるジャンプレベルにおけるハイパー免疫性を同時に保持するために導入された新しい概念である。これは、共通のリザーバーを持つ2つのステム（茎）を持つ条件を含み、構成が2つの結果のいずれか一方を選択できるようにする（一方の側または他方の側のハイパー免疫性を保持する）。
3. コンパクト性と併合（Compactness and Merging）： 著者らは、これらの強制問題がコンパクト（存在量化子の境界を定めることが可能）であり、かつ併合可能（強制条件の組み合わせが帰納スキームの保存を可能にする）であることを証明する。これらの性質は、保存定理や分離結果を証明するために不可欠である。

主要な貢献および結果

1. 階層の厳密性：
   本論文は、$RCA_0$ 上で鳩の巣原理の階層が厳密であることを証明する。具体的には、すべての $n \ge 1$ に対して次が成立する：
   $$\Sigma^0_n\text{-Subset} < \Delta^0_{n+1}\text{-Subset} < \Sigma^0_{n+1}\text{-Subset}$$
   これは、下位の原理を満たしつつ上位の原理には失敗する $\omega$-モデルを構成することによって達成される。この分離は、ハイパー免疫性保存に基づいている。すなわち、$\Delta^0_n$-Subset はレベル $\{n-2, n-1\}$ においてハイパー免疫性を保存するが、$\Sigma^0_n$-Subset はこれを保持しない。

2. 基底定理：
   著者らは、鳩の巣原理に関する新しい基底定理を確立する：

   • 弱低度基底（Weakly Low Basis）： すべての $n \ge 1$ について、$\Sigma^0_{n+1}$-Subset の任意の計算可能なインスタンスは、$\emptyset^{(n)}$ 上の PA 度は計算可能であるような解 $H$ を持つ。これは Benham ら [2] による予想を覆し、$\Delta^0_2$-Subset に関する既知の結果を一般化したものである。
   • 反復低度（Iterated Lowness）： すべての $\Sigma^0_{n+1}$ インスタンスは、$low^{n+1}$ 次数の解を持つ。
   • ハイパー免疫性保存： $\Delta^0_{n+1}$-Subset について、任意の $\emptyset^{(n-1)}$-ハイパー免疫関数 $f$ および $\emptyset^{(n)}$-ハイパー免疫関数 $g$ に対して、ある解 $H$ が存在し、$f$ は $H^{(n-1)}$-ハイパー免疫であり続け、$g$ は $H^{(n)}$-ハイパー免疫であり続けることを証明する。

3. 保存定理：
   本論文は、$RCA_0 + I\Sigma^0_n$ に $\Sigma^0_n$-Subset を加えることが、その理論の一次の強さを増大させないことを証明する。

   • 主要定理： $n \ge 2$ のとき、$RCA_0 + I\Sigma^0_n + \Sigma^0_n\text{-Subset}$ は $RCA_0 + I\Sigma^0_n$ 上で $\Pi^1_1$ 保存的である。
   • 応用： これは、$T_1$ 空間に対する Ginsburg-Sands 定理が $RCA_0 + I\Sigma^0_2$ 上で $\Pi^1_1$ 保存的であることを意味する。
   • 非保存性： 逆に、本論文は $RCA_0 + \Delta^0_{n+2}\text{-Subset}$ が $RCA_0 + B\Sigma^0_{n+1}$ 上で $\Pi^1_1$ 保存的ではないことを示し、$\Sigma^0$ レベルと $\Delta^0$ レベルの間における有界帰納との相互作用の違いを浮き彫りにしている。

意義
本論文は、ラムゼー型の定理の計算論的内容に関する複数の未解決問題を解決したと主張している。反復ジャンプ制御の枠組みをより高い算術的階層へと拡張することにより、著者らは以下の点において、鳩の巣原理の一元的な分析を提供している：

• ラムゼー理論の構造の明確化： ペアに関するラムゼーの定理（$RT^2_2$）の複雑さが $\Delta^0_2$-Subset 原理に深く根ざしていること、および鳩の巣原理の階層が強度的には厳密に増加することを示している。
• 強制手法の進展： 選言強制の導入と、反復ジャンプのための強制問題の洗練は、複数の計算論的性質の同時保存を必要とする組合せ論的原理を分析するための新しいツールを提供する。
• 位相幾何学との接続： Ginsburg-Sands 定理と鳩の巣原理の間の繋がりを強固にし、当該の位相幾何学的定理の強さが、凝集性（cohesiveness）と $\Sigma^0_2$-Subset の組み合わせによって正確に捉えられることを示している。

著者らは、階層の厳密性は確立されたものの、$\Sigma^0_n$-Subset の一次の帰結（具体的には $I\Sigma^0_2$ を含意するかどうか）や、$B\Sigma^0_2$ 上の $\Delta^0_2$-Subset の保存状況に関する問いが残されていると述べている。本論文は、これらの結果を、組合せ論的定理の計算論的内容を理解するという、より広範なメタ数学的プログラムの一部として位置づけている。