逆数学

逆数学は大抵の場合、2階算術について実行され、定理が構成的解析と証明論に動機付けられた2階算術の部分体系のうち、どれに対応するのかを研究する。 2階算術を使うことで、再帰理論からの多くの技術も利用できる。実際、逆数学の結果の多くは、計算可能性解析学の結果を反映している。

逆数学は、Harvey Friedman (1975, 1976)によってはじめて言及された。基本文献は(Simpson 2009)を参照。

逆数学は、フレームとなる言語と基本的な公理からはじめる。例えば、“すべての実数の有界な列は上限をもつ”という定理の研究には、実数と実数の列を定義する公理が必要となる。

基本体系において証明できない定理からはじめて、定理を証明するのに必要な(基本体系よりも強い)公理を決定することを目標とする。定理${\displaystyle T\,}$ とそれを証明可能な場合の体系${\displaystyle S\,}$ との関係を示す2つの証明がある。1つ目は、${\displaystyle S\,}$ から${\displaystyle T\,}$ が証明可能であることの証明である。このとき普通の数学の定理は体系${\displaystyle S\,}$ で成り立つ。2つ目は*逆方向*、 すなわち${\displaystyle T\,}$ が${\displaystyle S\,}$ と同値であることであることの基本体系における証明である。 逆方向の証明ができれば、${\displaystyle S\,}$ より弱い体系${\displaystyle S^{\prime }\,}$ であって${\displaystyle T\,}$ を証明できるようなものは存在しないことが分かる。

2階算術の使用

逆数学は2階算術の部分体系において研究されることが多い。その場合、数学的対象を自然数と自然数の集合によって形式化しなければならない。例えば、自然数のペアを1つの自然数として表現することができ、自然数のペアによって有理数を表現する。有理数の集合（これは結局、自然数の集合として表現される）によって有理数の列を表現し、有理数の列のうちコーシー列であるようなものによって実数を表現することができる。逆数学の研究においては、弱い部分体系であって数学的対象を形式化できる程度には強い体系を基本体系として用いる。

逆数学が集合論ではなく2階算術を用いるのは、弱い部分体系であって数学的対象を形式化できる程度には強い体系を2階算術では自然に定義することができるからである。

2階算術を使う場合、数学の定理を制限しなければならない。例えば、2階算術では一般のベクトル空間は表現できない。そのため"すべてのベクトル空間は基底をもつ"という一般的な原理は表現できないが、"すべての可算なベクトル空間は基底をもつ"という原理は表現することができる。同様に、代数の定理の対象は可算な群や環や体についてのものになる。また、距離空間を対象とする解析や位相の定理は、実数を有理数のコーシー列によって表現したのと同様の手法により、可分な距離空間について考察することができる。 なお、定理を可算なものに制限した場合、本来の定理とその強さが全く異なる場合がある。例えば、"すべての体は代数的閉体をもつ"はZF集合論では証明できないが、"すべての可算な体は代数的閉体をもつ"と制限すれば、非常に弱い形式体系である${\displaystyle {\mbox{RCA}}_{0}\,}$ でも証明することができる。

2階算術の部分体系 ${\displaystyle {\mbox{RCA}}_{0}\,}$ 、${\displaystyle {\mbox{WKL}}_{0}\,}$ 、${\displaystyle {\mbox{ACA}}_{0}\,}$ 、${\displaystyle {\mbox{ATR}}_{0}\,}$ 、${\displaystyle \Pi _{1}^{1}{\mbox{-CA}}_{0}\,}$ は, Big Fiveと呼ばれ、 逆数学において頻繁に扱われるものである。

次は"big five"の特徴である。Simpson (2009, p.42)参照。

部分体系	名称の由来	証明論的順序数	対応する哲学的原理	備考
${\displaystyle {\mbox{RCA}}_{0}\,}$	Recursive comprehension axiom(再帰的内包公理)	${\displaystyle \omega ^{\omega }\,}$	構成的数学 (Bishop)	逆数学の基本体系
${\displaystyle {\mbox{WKL}}_{0}\,}$	Weak König's lemma(弱ケーニッヒの補題)	${\displaystyle \omega ^{\omega }\,}$	有限還元 (Hilbert)	PRA上で${\displaystyle \Pi _{2}^{0}\,}$ 文を、${\displaystyle {\mbox{RCA}}_{0}\,}$ 上で${\displaystyle \Pi _{1}^{1}\,}$ 文を保存する。
${\displaystyle {\mbox{ACA}}_{0}\,}$	Arithmetical comprehension axiom(算術的内包公理)	${\displaystyle \epsilon _{0}\,}$	可述主義 (Weyl, Feferman)	ペアノ算術上で算術的文を保存する。
${\displaystyle {\mbox{ATR}}_{0}\,}$	Arithmetical transfinite recursion(算術的超限再帰)	${\displaystyle \Gamma _{0}\,}$	可述的還元主義 (Friedman, Simpson)	フィッファーマン体系IR上で${\displaystyle \Pi _{1}^{1}\,}$ 文を保存する。
${\displaystyle \Pi _{1}^{1}{\mbox{-CA}}_{0}\,}$	${\displaystyle \Pi _{1}^{1}\,}$  comprehension axiom (${\displaystyle \Pi _{1}^{1}\,}$ 内包公理)	${\displaystyle \Psi _{0}\,}$ (${\displaystyle \Omega _{\omega }\,}$ )	非可述主義

なお, Big Fiveの名前についている ${\displaystyle {}_{0}\,}$ は帰納法の図式が制限されていることを意味する。例えば、${\displaystyle {\mbox{ACA}}_{0}\,}$ は算術的論理式についての帰納法しか持たない。帰納法を制限した体系は、一般の2階算術の論理式についての帰納法をもつ体系に比べ、大幅に小さい証明論的順序数を持つ。

再帰的内包公理 RCA₀

${\displaystyle {\mbox{RCA}}_{0}\,}$ は、「ロビンソン算術の公理」＋「${\displaystyle \Sigma _{1}^{0}\,}$ 論理式に対する帰納法の公理」＋「${\displaystyle \Delta _{1}^{0}\,}$ 論理式に対する内包公理」からなる部分体系である。

${\displaystyle {\mbox{RCA}}_{0}\,}$ は逆数学で最も多用される体系である。${\displaystyle {\mbox{RCA}}_{0}\,}$ は"再帰的内包公理"と呼ばれ、"再帰的"とは"計算可能"を意味している。この名称は${\displaystyle {\mbox{RCA}}_{0}\,}$ が"計算可能性数学"に類似しているからである。${\displaystyle {\mbox{RCA}}_{0}\,}$ で存在が証明可能な自然数の集合は計算可能である、よって計算不可能な集合の存在は${\displaystyle {\mbox{RCA}}_{0}\,}$ で証明できない。

${\displaystyle {\mbox{RCA}}_{0}\,}$ はBig Fiveで最弱だが、古典的数学の対象を形式化できる。また、以下の定理が証明可能である。

• 自然数全体、整数全体、有理数全体の成す集合の基本性質(例えば、有理数全体が順序体を成すこと)。
• 実数全体の成す集合の基本性質(実数全体がアルキメデス順序体であること、長さが0に近付く任意の包含閉区間列の交叉が1点のみからなること、実数は非可算であること)。
• 完備可分距離空間におけるベールの範疇定理。
• 実連続関数における中間値の定理。
• 可分バナッハ空間における連続線形演算子の列に関するバナッハ–シュタインハウスの定理。
• 弱いゲーデルの完全性定理。
• 可算な体での代数的閉体の存在(一意性は除く)。
• 可算な順序体の実閉体の存在と一意性。

${\displaystyle {\mbox{RCA}}_{0}\,}$ の1階部分は、${\displaystyle {\mbox{I}}\Sigma _{1}\,}$ （ペアノ算術の帰納法を${\displaystyle \Sigma _{1}\,}$ 論理式に制限した体系）と一致する。

弱ケーニッヒの補題 WKL₀

${\displaystyle {\mbox{WKL}}_{0}\,}$ は、${\displaystyle {\mbox{RCA}}_{0}\,}$ に弱ケーニッヒの補題（すべての無限二分木は無限路をもつ）を付け加えた体系である。

弱ケーニッヒの補題は選択公理に近く、実際${\displaystyle {\text{RCA}}_{0}\,}$ において、${\displaystyle \Pi _{1}^{1}\,}$ 選択公理と${\displaystyle {\text{WKL}}_{0}\,}$ が同値であることを示せる。また、${\displaystyle \Sigma _{1}^{0}\,}$ 分離原理とも同値になる。

${\displaystyle {\mbox{WKL}}_{0}\,}$ は、${\displaystyle {\mbox{RCA}}_{0}\,}$ よりも証明能力が高く、${\displaystyle {\mbox{WKL}}_{0}\,}$ では非計算可能集合の存在を示せる。

${\displaystyle {\mbox{RCA}}_{0}\,}$ と${\displaystyle {\mbox{WKL}}_{0}\,}$ の1階部分は同じ、つまり算術的な定理については証明能力は同じである。しかし、${\displaystyle {\mbox{WKL}}_{0}\,}$ で証明可能で、${\displaystyle {\mbox{RCA}}_{0}\,}$ では証明不可能な古典的数学の定理もある。これらの結果は2階部分の証明能力の違いを示している。

${\displaystyle {\mbox{RCA}}_{0}\,}$ 上で、${\displaystyle {\mbox{WKL}}_{0}\,}$ と以下の定理が同値であることが示せる。

• 実数からなる単位閉区間に対する（開区間による任意の被覆が有限部分被覆を持つという意味での）ハイネ＝ボレルの定理。
• 完備全有界可分距離空間に対する（開球体列による被覆についての）ハイネ＝ボレルの定理。
• 単位閉区間（もしくは任意のコンパクト可分距離空間）上の連続実函数が有界であること（もしくは有界かつその境界値を実現する点が存在すること）。
• 単位閉区間上の連続実函数が有理係数多項式で一様に近似できること。
• 単位閉区間上の連続実函数が一様連続であること。
• 単位閉区間上の連続実函数がリーマン積分可能であること。
• 単位閉区間の有限個のコピーの直積上の連続函数に対するブラウワーの不動点定理。
• 可分バナッハ空間の部分空間上の有界線型形式が全体空間上の有界線型形式に拡張できるという形での可分ハーン＝バナッハの定理。
• ジョルダンの閉曲線定理
• 可算言語に対するゲーデルの完全性定理。
• 任意の可算可換環が素イデアルを持つこと。
• 任意の可算形式的実体を順序体にできること。
• 可算体に対する代数閉包の一意性。

算術的内包公理 ACA₀

${\displaystyle {\mbox{ACA}}_{0}\,}$ は、${\displaystyle {\mbox{RCA}}_{0}\,}$ に算術的内包公理を付け加えた体系である。${\displaystyle {\mbox{ACA}}_{0}\,}$ は、任意の算術的論理式を満たす自然数の集合の存在を示す。実際、算術的内包公理を得るために、${\displaystyle {\mbox{RCA}}_{0}\,}$ にΣ₁論理式の内包公理を追加したものである。

${\displaystyle {\mbox{ACA}}_{0}\,}$ の1階部分はペアノ算術と同じである。つまり${\displaystyle {\mbox{ACA}}_{0}\,}$ は算術的な定理についてはにペアノ算術と証明能力は同じである。また、両者は無矛盾性については等価である。

${\displaystyle {\mbox{ACA}}_{0}\,}$ は、可述的数学のほとんどを展開することができ、古典的数学の基本的な定理の多くを証明することができる。

算術的集合を含まない${\displaystyle {\mbox{WKL}}_{0}\,}$ のモデルが存在するので、${\displaystyle {\mbox{ACA}}_{0}\,}$ は${\displaystyle {\mbox{WKL}}_{0}\,}$ よりも強いことが示される。実際、低基底定理を使った低集合を含むような${\displaystyle {\mbox{WKL}}_{0}\,}$ のモデルは構成不可能。

${\displaystyle {\mbox{RCA}}_{0}\,}$ 上で次と${\displaystyle {\mbox{ACA}}_{0}\,}$ は同値。

• 実数全体の集合の点列コンパクト性（有界で単調増加な任意の実数列は極限を持つ）。
• ボルツァーノ＝ワイエルシュトラスの定理。
• アスコリの定理: 単位閉区間上の任意の有界で同程度連続な実関数列は一様収束する部分列を持つ。
• 任意の可算可換環は極大イデアルを持つ。
• 有理数体（もしくは任意の可算体）上の任意の可算ベクトル空間は基底を持つ。
• 任意の可算体は超越基底を持つ。
• （任意の有限分岐木に対する、弱でない）ケーニヒの補題。
• ラムゼーの定理の一形態などを例とする組合せ論の諸定理。

算術的超限再帰 ATR₀

${\displaystyle {\mbox{ATR}}_{0}\,}$ は、${\displaystyle {\mbox{ACA}}_{0}\,}$ に算術的超限再帰を追加した体系である。

${\displaystyle {\mbox{ATR}}_{0}\,}$ は${\displaystyle {\mbox{ACA}}_{0}\,}$ 上で、Σ¹₁分離原理と同値である。

${\displaystyle {\mbox{ATR}}_{0}\,}$ は、${\displaystyle {\mbox{ACA}}_{0}\,}$ の無矛盾性を証明可能なのでゲーデルの不完全性定理より、${\displaystyle {\mbox{ACA}}_{0}\,}$ より強い。

${\displaystyle {\mbox{RCA}}_{0}\,}$ で次が${\displaystyle {\mbox{ATR}}_{0}\,}$ と同値。

• 任意の二つの可算整列順序は比較可能（一方が他方または他方の始片に同型）である。
• 可算被約アーベル群に対するウルムの定理。
• 完備可分距離空間の任意の非可算閉部分集合が完全閉集合を含むことを述べた完全集合定理。
• ルージンの分離定理（essentially ${\displaystyle \Sigma _{1}^{1}\,}$ 分離）。
• ベール空間における開集合の決定性。

Π1
1内包公理 Π1
1-CA₀

${\displaystyle \Pi _{1}^{1}{\text{-CA}}_{0}\,}$ は、${\displaystyle {\mbox{RCA}}_{0}\,}$ に${\displaystyle \Pi _{1}^{1}\,}$ 論理式に関する内包公理を追加した体系である。${\displaystyle \Pi _{1}^{1}{\text{-CA}}_{0}\,}$ は非可述的な体系である。

${\displaystyle \Pi _{1}^{1}{\text{-CA}}_{0}\,}$ と${\displaystyle {\text{ATR}}_{0}\,}$ の関係は、${\displaystyle {\text{ACA}}_{0}\,}$ と${\displaystyle {\text{WKL}}_{0}\,}$ の関係に似ている。

${\displaystyle \Pi _{1}^{1}{\text{-CA}}_{0}\,}$ は、記述的集合論における強い非可述的論法によって証明される定理と同値になる。この同値性はこれらの非可述的論法が取り除けないことを示している。

${\displaystyle {\mbox{RCA}}_{0}\,}$ で、${\displaystyle \Pi _{1}^{1}{\mbox{-CA}}_{0}\,}$ と次の定理が同値であることが証明できる。

• カントール＝ベンディクソンの定理（実数から成る任意の閉集合は完全集合と可算集合の和集合として書ける）。
• 任意の可算アーベル群は可除群と被約群の直和として書ける。

逆数学においては、Big Five以外の体系も研究されている。それらはAfter Fiveとも呼ばれる。

• 再帰的内包公理よりも弱い体系が定義できる。${\displaystyle {\mbox{RCA}}_{0}^{\ast }\,}$ は、初等関数算術EFA(指数関数を含む算術の基本公理 + ${\displaystyle \Delta _{0}^{0}\,}$ 帰納法)に${\displaystyle \Delta _{1}^{0}\,}$ 内包公理を付け加えた体系である。${\displaystyle {\mbox{RCA}}_{0}^{\ast }\,}$ 上で、${\displaystyle {\mbox{RCA}}_{0}\,}$ は、可算な体の上で多項式が高々有限の根しかもたないことや、有限アーベル群の分類定理などと同値である。

${\displaystyle {\mbox{RCA}}_{0}^{\ast }\,}$ は${\displaystyle {\mbox{EFA}}\,}$ と同じ証明論的順序数 ${\displaystyle \omega ^{3}\,}$ をもち、${\displaystyle {\mbox{EFA}}\,}$ 上${\displaystyle \Pi _{2}^{0}\,}$ 文について保存的な拡大になっている。

• ${\displaystyle {\mbox{WWKL}}_{0}\,}$ は、${\displaystyle {\mbox{RCA}}_{0}\,}$ に弱弱ケーニッヒの補題「無限路を持たない無限2進木のある部分木は、長さ${\displaystyle n\,}$ の葉がどれだけ存在するかを一様に推定できる」（無限路を持たない二分木の長さ n の枝の本数と ${\displaystyle 2^{n}}$  の比は ${\displaystyle n\to \infty }$  でゼロに収束する）を追加した公理系である。${\displaystyle {\mbox{WWKL}}_{0}\,}$ は、${\displaystyle {\mbox{RCA}}_{0}\,}$ 上で「任意のコンパクト距離空間における任意のボレル測度は可算加法的である」等の測度論の定理と同値になる。${\displaystyle {\mbox{WWKL}}_{0}\,}$ のモデル理論は、アルゴリズム的ランダム列の理論と関連する。実際、${\displaystyle {\mbox{RCA}}_{0}\,}$ の${\displaystyle \omega \,}$ -モデル${\displaystyle M\,}$ に対し, ${\displaystyle M\,}$ が${\displaystyle {\mbox{WWKL}}_{0}\,}$ のモデルであることと, ${\displaystyle M\,}$ に含まれる任意の集合${\displaystyle X\,}$ について、${\displaystyle X\,}$ に対し相対的に1-randomなある${\displaystyle Y\,}$ が存在して${\displaystyle Y\,}$ が${\displaystyle M\,}$ に含まれることは同値である。
• DNR("diagonally non-recursive"の略)は、${\displaystyle {\mbox{RCA}}_{0}\,}$ に「任意の集合に対し対角的非再帰な関数が存在する」を追加した公理系である。${\displaystyle {\mbox{DNR}}\,}$ とはつまり「任意の集合${\displaystyle A\,}$ に対して、ある全域的関数${\displaystyle f\,}$ が存在して、fは${\displaystyle A\,}$ から計算可能などんな部分関数とも等しくない」が成り立つということである。${\displaystyle {\mbox{DNR}}\,}$ は、${\displaystyle {\mbox{WWKL}}_{0}\,}$ よりも真に弱い。(Lempp et al., 2004).
• 「超算術的な集合全体からなる構造の上で成り立つ」「極小${\displaystyle \omega \,}$ モデルは超算術的な集合全体である」という性質を満たす公理系はTheory of hyperarithmetic analysisと呼ばれる。

Theory of hyperarithmetic analysisの例として、${\displaystyle {\mbox{weak-}}\Sigma _{1}^{1}{\mbox{-AC}}_{0}\,}$ 、${\displaystyle \Delta _{1}^{1}{\mbox{-CA}}_{0}\,}$ 、${\displaystyle \Pi _{1}^{1}{\mbox{-SEP}}_{0}\,}$ 、${\displaystyle \Sigma _{1}^{1}{\mbox{-AC}}_{0}\,}$ はTheory of hyperarithmetic analysisがあり、それぞれ${\displaystyle {\mbox{ACA}}_{0}\,}$ に弱${\displaystyle \Sigma _{1}^{1}\,}$ 選択公理、${\displaystyle \Delta _{1}^{1}\,}$ 内包公理、${\displaystyle \Pi _{1}^{1}\,}$ 分離公理、${\displaystyle \Sigma _{1}^{1}\,}$ 選択公理を追加した公理系である。

「${\displaystyle \omega \,}$ -モデル」の${\displaystyle \omega \,}$ は非負整数全体の集合を意味する。

その1階部分が1階ペアノ算術の標準モデルになっているような、2階算術の部分体系のモデルを${\displaystyle \omega \,}$ -モデルと呼ぶ。ただし、2階部分は非標準であっても良い。すなわち、${\displaystyle \omega \,}$ -モデルは${\displaystyle S\subseteq {\mathcal {P}}(\omega )\,}$ （${\displaystyle {\mathcal {P}}(\omega )\,}$ は${\displaystyle \omega \,}$ の部分集合全体のクラス）によって与えられる。数変数は ${\displaystyle \omega \,}$ の元として解釈され、定数記号${\displaystyle 0,1\,}$ や関数記号${\displaystyle +,\times \,}$ は標準的に解釈される。一方、集合変数は ${\displaystyle S\,}$ の元として解釈される。${\displaystyle S={\mathcal {P}}(\omega )\,}$ とする${\displaystyle \omega \,}$ -モデルを2階算術の標準モデルと呼ぶ。しかし、標準モデル以外にも${\displaystyle \omega \,}$ -モデルは存在する。たとえば、${\displaystyle {\mbox{RCA}}_{0}\,}$ は${\displaystyle S\,}$ として計算可能な${\displaystyle \omega \,}$ の部分集合全体をとった${\displaystyle \omega \,}$ -モデルをもつ。

${\displaystyle \omega \,}$ -モデルであって、${\displaystyle \Sigma _{1}^{1}\,}$ 文について、標準モデルと真偽が一致するものを${\displaystyle \beta \,}$ -モデルと呼ぶ。${\displaystyle {\mbox{ACA}}_{0}\,}$ において全ての${\displaystyle \beta \,}$ -モデルが${\displaystyle {\mbox{ATR}}_{0}\,}$ のモデルであることが示せる。また、${\displaystyle {\mbox{ACA}}_{0}\,}$ において、「任意の集合${\displaystyle X\,}$ について${\displaystyle X\,}$ を含む${\displaystyle \beta \,}$ モデルが存在する」は ${\displaystyle \Pi _{1}^{1}{\mbox{-CA}}_{0}\,}$ と同値である。

一般に、${\displaystyle \omega \,}$ -モデルであって、${\displaystyle \Sigma _{n}^{1}\,}$ 文について、標準モデルと真偽が一致するものは${\displaystyle \beta _{n}\,}$ -モデルと呼ばれる。

また、Non-${\displaystyle \omega \,}$ -モデル（1階部分が標準ではないモデル）も、ある公理系が保存的拡大であることの証明にしばしば登場する。

• 田中一之『逆数学と2階算術』倉田令二朗 監修、河合文化教育研究所〈数学基礎論シリーズ 4〉、1997年8月。ISBN 978-4-87999-970-2。 
• Ambos-Spies, K.; Kjos-Hanssen, B.; Lempp, S.; Slaman, T.A. (2004), “Comparing DNR and WWKL”, Journal of Symbolic Logic 69 (4): 1089, doi:10.2178/jsl/1102022212. 
• Friedman, Harvey (1975), “Some systems of second order arithmetic and their use”, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 1, Canad. Math. Congress, Montreal, Que., pp. 235–242, MR0429508 
• Friedman, Harvey (1976), Systems of second order arithmetic with restricted induction, I, II, “Meeting of the Association for Symbolic Logic”, The Journal of Symbolic Logic (Association for Symbolic Logic) 41 (2): 557–559, ISSN 0022-4812, http://www.jstor.org/stable/2272259?seq=7 
• Simpson, Stephen G. (2009), Subsystems of second order arithmetic, Perspectives in Logic (2nd ed.), Cambridge University Press, ISBN 978-0-521-88439-6, MR2517689, http://www.math.psu.edu/simpson/sosoa/ 
• Stillwell, John (2019-09-24), Reverse Mathematics: Proofs from the Inside Out (Paperback ed.), Princeton, NJ: Princeton University Press, ISBN 978-0-691-19641-1 
  • ジョン・スティルウェル 著、川辺治之 訳『逆数学　定理から公理を「証明」する』田中一之 監訳・解説、森北出版、2019年2月。ISBN 978-4-627-05451-6。 
• Solomon, Reed (1999), “Ordered groups: a case study in reverse mathematics”, The Bulletin of Symbolic Logic 5 (1): 45–58, doi:10.2307/421140, ISSN 1079-8986, MR1681895, http://www.jstor.org/stable/421140 

• Harvey Friedman's home page
• Stephen G. Simpson's home page