逆数学
逆数学とは、数学の定理の証明に必要な公理を決定しようとする数理論理学のプログラムである。簡単に言えば、通常の数学が公理から定理を導くのとは逆に、「定理から公理を証明する」手法を用いることが特徴である。「選択公理とツォルンの補題はZF上で同値である」、というような集合論の古典的定理は、逆数学プログラムの予兆となるものだった。しかし、実際の逆数学では主に、集合論の公理ではなく、通常の数学の定理を研究するのを目的とする。
逆数学は大抵の場合、2階算術について実行され、定理が構成的解析と証明論に動機付けられた2階算術の部分体系のうち、どれに対応するのかを研究する。
2階算術を使うことで、再帰理論からの多くの技術も利用できる。実際、逆数学の結果の多くは、計算可能性解析の結果を反映している。
逆数学は、によってはじめて言及された。基本文献はを参照。
逆数学は、フレームとなる言語と基本的な公理からはじめる。例えば、“すべての実数の有界な列は上限をもつ”という定理の研究には、実数と実数の列を定義する公理が必要となる。
基本体系において証明できない定理からはじめて、定理を証明するのに必要な(基本体系よりも強い)公理を決定することを目標とする。定理formula_1とそれを証明可能な場合の体系formula_2との関係を示す2つの証明がある。1つ目は、formula_2からformula_1が証明可能であることの証明である。このとき普通の数学の定理は体系formula_2で成り立つ。2つ目は*逆方向*、
すなわちformula_1がformula_2と同値であることであることの基本体系における証明である。
逆方向の証明ができれば、formula_2より弱い体系formula_9であってformula_1を証明できるようなものは存在しないことが分かる。
逆数学は2階算術の部分体系において研究されることが多い。その場合、数学的対象を自然数と自然数の集合によって形式化しなければならない。例えば、自然数のペアを1つの自然数として表現することができ、自然数のペアによって有理数を表現する。有理数の集合（これは結局、自然数の集合として表現される）によって有理数の列を表現し、有理数の列のうちコーシー列であるようなものによって実数を表現することができる。逆数学の研究においては、弱い部分体系であって数学的対象を形式化できる程度には強い体系を基本体系として用いる。
逆数学が集合論ではなく2階算術を用いるのは、弱い部分体系であって数学的対象を形式化できる程度には強い体系を2階算術では自然に定義することができるからである。
2階算術を使う場合、数学の定理を制限しなければならない。例えば、2階算術では一般のベクトル空間は表現できない。そのため"すべてのベクトル空間は基底をもつ"という一般的な原理は表現できないが、"すべての可算なベクトル空間は基底をもつ"という原理は表現することができる。同様に、代数の定理の対象は可算な群や環や体についてのものになる。また、距離空間を対象とする解析や位相の定理は、実数を有理数のコーシー列によって表現したのと同様の手法により、可分な距離空間について考察することができる。
なお、定理を可算なものに制限した場合、本来の定理とその強さが全く異なる場合がある。例えば、"すべての体は代数的閉体をもつ"はZF集合論では証明できないが、"すべての可算な体は代数的閉体をもつ"と制限すれば、非常に弱い弱い形式体系であるformula_11でも証明することができる。
2階算術の部分体系 formula_11、formula_13、formula_14、formula_15、formula_16は, Big Fiveと呼ばれ、
逆数学において頻繁に扱われるものである。
次は"big five"の特徴である。参照。
なお, Big Fiveの名前についている formula_17は帰納法の図式が制限されていることを意味する。例えば、formula_14は算術的論理式についての帰納法しか持たない。帰納法を制限した体系は、一般の2階算術の論理式についての帰納法をもつ体系に比べ、大幅に小さい証明論的順序数を持つ。
formula_11は、「ロビンソン算術の公理」＋「formula_21論理式に対する帰納法の公理」＋「formula_22論理式に対する内包公理」からなる部分体系である。
formula_11は逆数学で最も多用される体系である。formula_11は"再帰的内包公理"と呼ばれ、"再帰的"とは"計算可能"を意味している。この名称はformula_11が"計算可能性数学"に類似しているからである。formula_11で存在が証明可能な自然数の集合は計算可能である、よって計算不可能な集合の存在はformula_11で証明できない。
formula_11はBig Fiveで最弱だが、古典的数学の対象を形式化できる。また、以下の定理が証明可能である。
formula_11の1階部分は、formula_30（ペアノ算術の帰納法をformula_31論理式に制限した体系）と一致する。
formula_13は、formula_11に弱ケーニッヒの補題（すべての無限二分木は無限路をもつ）を付け加えた体系である。
弱ケーニッヒの補題は選択公理に近く、実際formula_35において、formula_36選択公理とformula_37が同値であることを示せる。また、formula_21分離原理とも同値になる。
formula_13は、formula_11よりも証明能力が高く、formula_13では非計算可能集合の存在を示せる。
formula_11とformula_13の1階部分は同じ、つまり算術的な定理については証明能力は同じである。しかし、formula_13で証明可能で、formula_11では証明不可能な古典的数学の定理もある。これらの結果は2階部分の証明能力の違いを示している。
formula_11上で、formula_13と以下の定理が同値であることが示せる。formula_14は、formula_11に算術的内包公理を付け加えた体系である。formula_14は、任意の算術的論理式を満たす自然数の集合の存在を示す。実際、算術的内包公理を得るために、formula_11にΣ論理式の内包公理を追加したものである。
formula_14の1階部分はペアノ算術と同じである。つまりformula_14は算術的な定理についてはにペアノ算術と証明能力は同じである。また、両者は無矛盾性については等価である。
formula_14は、可述的数学のほとんどを展開することができ、古典的数学の基本的な定理の多くを証明することができる。
算術的集合を含まないformula_13のモデルが存在するので、formula_14はformula_13よりも強いことが示される。実際、低基底定理を使った低集合を含むようなformula_13のモデルは構成不可能。
formula_11上で次とformula_14は同値。
formula_15は、formula_14に算術的超限再帰を追加した体系である。
formula_15はformula_14上で、Σ分離原理と同値である。
formula_15は、formula_14の無矛盾性を証明可能なのでゲーデルの不完全性定理より、formula_14より強い。
formula_11で次がformula_15と同値。
formula_75は、formula_11にformula_36論理式に関する内包公理を追加した体系である。formula_75は非可述的な体系である。
formula_75とformula_80の関係は、formula_81とformula_37の関係に似ている。
formula_75は、記述的集合論における強い非可述的論法によって証明される定理と同値になる。この同値性はこれらの非可述的論法が取り除けないことを示している。
formula_11で、formula_16と次の定理が同値であることが証明できる。
逆数学においては、Big Five以外の体系も研究されている。それらはAfter Fiveとも呼ばれる。
formula_91はformula_92と同じ証明論的順序数
formula_93をもち、formula_92上formula_95文について保存的な拡大になっている。
Theory of hyperarithmetic analysisの例として、formula_121、formula_122、formula_123、formula_124はTheory of hyperarithmetic analysisがあり、それぞれformula_14に弱formula_72選択公理、formula_127内包公理、formula_36分離公理、formula_72選択公理を追加した公理系である。
「formula_103-モデル」のformula_103は非負整数全体の集合を意味する。
その1階部分が1階ペアノ算術の標準モデルになっているような、2階算術の部分体系のモデルをformula_103-モデルと呼ぶ。ただし、2階部分は非標準であっても良い。すなわち、formula_103-モデルはformula_136（formula_137はformula_103の部分集合全体のクラス）によって与えられる。数変数は formula_103の元として解釈され、定数記号formula_140や関数記号formula_141は標準的に解釈される。一方、集合変数は formula_2の元として解釈される。formula_143とするformula_103-モデルを2階算術の標準モデルと呼ぶ。しかし、標準モデル以外にもformula_103-モデルは存在する。たとえば、formula_11はformula_2として計算可能なformula_103の部分集合全体をとったformula_103-モデルをもつ。
formula_103-モデルであって、formula_72文について、標準モデルと真偽が一致するものをformula_131-モデルと呼ぶ。formula_14において全てのformula_131-モデルがformula_15のモデルであることが示せる。また、formula_14において、「任意の集合formula_108についてformula_108を含むformula_131モデルが存在する」は formula_16と同値である。
一般に、formula_103-モデルであって、formula_162文について、標準モデルと真偽が一致するものはformula_163-モデルと呼ばれる。
また、Non-formula_103-モデル（1階部分が標準ではないモデル）も、ある公理系が保存的拡大であることの証明にしばしば登場する。