逆数学の未解決問題のいくつか

はじめに

ここでは，逆数学の未解決問題について最近知った話題をまとめる。逆数学の未解決問題は様々あるが，広範囲についてのまとめではなく私が気になったものと今現在知っているものが中心的になる。この記事は今後更新する可能性が高い。

逆数学とは，数学で既に知られている個々の定理を証明するにはどういった公理系が必要十分であるか，ということを検証する数学基礎論のプログラムである。

通常の数学は $ZFC$ のような集合論の公理系をベースとして展開されるが，通常の数学で扱うような定理の逆数学を行うには集合論の公理系は強すぎることが多い。

そこでペアノ算術にその二階部分を扱う公理図式を追加した二階算術で，逆数学の舞台となる公理系を用意するという研究が発達している。(この形では本質的に可算な構造しか扱えないため，高階算術を用意するといった研究も調べられている。ここではそういう話はしない。)

古典的な結果として，五段階の強さに分かれる二階算術の部分体系(公理系)で逆数学は概ね行えることが判明している。(これを逆数学現象とかBig five 現象などと呼ぶ人もいる。)

その例外となるケースも多く知られており興味の対象となっている。

逆数学の既に知られている結果の簡単な一覧はWikipediaで見れる。

ja.wikipedia.org

ここで $\mathsf{RCA} _ 0$ 上で $\mathsf{ACA} _ 0$ と同値となる定理の項目で

"ラムゼーの定理の一形態などを例とする組合せ論の諸定理" という記述がある。まずはこれについて少し話す。

Ramsey理論周辺

Ramseyの定理の主張を見るための準備をする。

$\mathbb{N}$ の部分集合であって $n$ 元からなる集合の全体を $[\mathbb{N}] ^ n$ で表し， $k$ 元集合を単に $k$ と書く。 $f \colon [\mathbb{N}] ^ n \to k$ を着色という。

$H \subset \mathbb{N}$ が着色 $f$ で等質集合であるとは， $H$ の任意の $n$ 組が $f$ で同じ色になっていることをいう。

自然数 $n, k$ ごとに次の主張を定める。

$\mathsf{RT} ^ n _ k$ : 任意の着色 $f \colon [\mathbb{N} ]^ n \to k$ について等質な無限集合が存在する。

$\mathsf{RT} ^ n$ : 任意の $k$ について $\mathsf{RT} ^n _ k$ が成立する。

$n \ge 3$ のとき $\mathsf{RT} ^ n$ と $\mathsf{RT} ^ n _ k$ は $\mathsf{ACA} _ 0$ と同値となることが知られている。

また， $n \ge 3 , k \ge 2$ のときは $\mathsf{RT} ^ n _ k$ は $\mathsf{ACA} _ 0$ と同値であることが比較的簡単にわかる。(これは Simpson の Subsystems

of second order arithmetic にも書いてある)

では $\mathsf{RT} ^ 2 _ 2$ はどうか。これは逆数学現象に当てはまらない例として知られているようだ。つまり， $\mathsf{RT} ^2 _2$ は $\mathsf{RCA} _ 0$ 上で $\mathsf{ACA} _ 0$ より真に弱く，そして弱ケーニヒの補題とは比較不可能であることが示されている。

すると， $\mathsf{RT} ^2 _2$ で何が示せるか，という疑問が出てくる。

問題　 $\mathsf{RT} ^2 _2$ からアッカーマン関数の全域性や $^ \omega\omega$ の整列性は証明できるか？

これらは $\mathsf{I}\Sigma ^0 _2$ や $\mathsf{RT} ^2$ からは証明可能である。一方で $\mathsf{B}\Sigma ^0 _2$ はどちらも示せない。

$\mathsf{RT} ^2 _2$ の強さは興味を持たれていて色んな問題や予想が立っている。

魔境っぽい感じだったので詳細を書くことをやめたがいつかまとめたい。

Hindmanの定理

どのように自然数全体を $r$ 個の類に分割しても，無限集合 $S \subseteq \mathbb{N}$ であって $S$ の元の有限和全体 $\mathrm{Fin}(S)$ がある類に含まれるようなものが存在する

という主張を Hindman の定理という( $\mathsf{HT}$ と表す)。*1

$\mathsf{HT} \Rightarrow \mathsf{ACA}_0$ と $\mathsf{ACA}_0 ^ + \Rightarrow \mathsf{HT}$ は知られているが，それ以上はまだわかっていないらしい。

ここで $\mathsf{ACA}_0 ^ +$ は $\mathsf{RCA}_0 + \forall X ( X^{(\omega)} \textrm{exist} )$ である。( $X^{(\omega)}$ は $X$ のωチューリングジャンプである。)

問題　 $\mathsf{HT}$ の強さを特定せよ

代数

Wikipediaで $\mathsf{ATR}_0$ と同値となる定理を見ると，可算被約アーベル群に対するUlum の定理というのがある。

ざっくり見ると被約という条件があれば可換群の定理は $\mathsf{ATR}_0$ で扱え，被約性を外すと $\Pi ^1 _1 -\mathsf{CA} _0$ が出てくるらしい。

そこで次のような問題が出ている。

問題　次のふたつは $\Pi ^1 _1 - \mathsf{CA}_0$ と同値か？

・ $G , H$ を可算ねじれ可換群であって $G + G$ と $H + H$ が同型となるものとすると， $G$ と $H$ は同型である。

・ $G , H$ を可算ねじれ可換群であってそれぞれはもう片方の直和因子となっている。このとき $G$ と $H$ は同型である。

Friedmanはこれらの成立と，またこれらは被約性を付加すれば $\mathsf{ATR} _0$ と同値になるだろうと予想している。*2

他には，アルティン環はネーター環である，という定理が $\mathsf{WKL} _0$ を導き， $\mathsf{ACA} _ 0$ から導かれるということが判明している。この定理の強さはどうなるか？という問題が残っている。*3

ジェネトポ

二階算術では完備可分空間がうまくコード化できるので解析学などの定理はその上で調べられるが，ジェネトポをやるにはこれは微妙である。そこでMummer と Simpson により第二可算な位相空間について $\mathrm{MF}$ 空間というものを用いて調べることが考えられている。

$P$ を半順序集合とする。 $P$ に対して定まる $\mathrm{MF}$ 空間 $\mathrm{MF}(P)$ とは，点を $P$ の極大フィルターとし， $p \in P$ で $N_p = \{ F \in \mathrm{MF}(P) : p \in F \}$ を基として定まる位相が入った空間である。