Time: 15:00-
Abstract: 無限組み合わせ論において重要な研究対象であるラムゼイの定理は,逆数学および計算可能性理論の分野においても様々な視点から研究がなされている. 特に逆数学の観点では, 自然数のペアに対する2色塗分けの無限ラムゼイ定理RT^2_2において,それが基本 体系RCA_0と体系ACA_0の間に属し,かつ弱ケーニヒの補題の定式化である体系WKL_0と互いに独立であるという特異さをもつこと(しかし,このバリエーションである多くの定理はこれらの体系と同様の関係にある)に着目し,帰納法公理をはじめとする様々な公理 および組み合わせ論の定理との導出関係や,公理系における保存拡大性,さらにはRT^2_2の 様々なバリエーション(ラムゼイ型定理)についても多くの研究がなされている.
本発表ではラムゼイ型定理のひとつとしてLarge Ramsey Theoremを紹介する. ある有 限集合Xがlargeであるとは, Xの濃度がXの最小値よりも大きいことをいう. また,ある有限集合Xがexactly largeであるとは, Xの濃度とXの最小値+1が一致することをいう. このlargenessという概念は組み合わせ論において有名なParis-Harringtonの原理に由来するものだが,これを基にexactly largeな集合に対する2色塗分けの無限ラムゼイ 定理を考えることができる(RT^!ω_2と表記する). 実はRT^!ω_2は“ω回のTuring jump”の下で閉じた体系であるACA^+_0とRCA_0上同値となることが知られている[2], [1]. 本発表で は, RT^!ω_2とそのバリエーションにおける逆数学研究について,これまでのラムゼイ型定理 研究の流れを踏まえながら紹介する.
[1] Lorenzo Carlucci, Oriala Gjetaj, Quentin Le Hou´erou, and Ludovic Levy Patey. Ramsey-like theorems for the schreier barrier. The Journal of Symbolic Logic, page 1–29, July 2025.
[2] Lorenzo Carlucci and Konrad Zdanowski. The strength of Ramsey’s theorem for coloring relatively large sets. J. Symb. Log., 79(1):89–102, 2014