逆数学

逆数学とは、数学の定理の証明に必要な公理を決定しようとする数理論理学のプログラムである。簡単に言えば、通常の数学が公理から定理を導くのとは逆に、「定理から公理を証明する」手法を用いることが特徴である。「選択公理とツォルンの補題はZF上で同値である」、というような集合論の古典的定理は、逆数学プログラムの予兆となるものだった。しかし、実際の逆数学では主に、集合論の公理ではなく、通常の数学の定理を研究するのを目的とする。

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

逆数学は、txtによってはじめて言及された。基本文献はSimpsonを参照。

1. 一般的な原理
---------

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

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

1.1. 2階算術の使用
------------

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

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

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

2. 2階算術の5つの基本的部分体系
----------------------------

2階算術の部分体系 、、、、は, Big Fiveと呼ばれ、 逆数学において頻繁に扱われるものである。

次は"big five"の特徴である。Simpson参照。

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

2.1. 再帰的内包公理 RCA0
-----------------

は、「ロビンソン算術の公理」＋「論理式に対する帰納法の公理」＋「論理式に対する内包公理」からなる部分体系である。

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

はBig Fiveで最弱だが、古典的数学の対象を形式化できる。また、以下の定理が証明可能である。

自然数全体、整数全体、有理数全体の成す集合の基本性質。
実数全体の成す集合の基本性質。
完備可分距離空間におけるベールの範疇定理。
実連続関数における中間値の定理。
可分バナッハ空間における連続線形演算子の列に関するバナッハ–シュタインハウスの定理。
弱いゲーデルの完全性定理。
可算な体での代数的閉体の存在。
可算な順序体の実閉体の存在と一意性。の1階部分は、と一致する。

2.2. 弱ケーニッヒの補題 WKL0
-------------------

は、に弱ケーニッヒの補題を付け加えた体系である。

弱ケーニッヒの補題は選択公理に近く、実際において、選択公理とが同値であることを示せる。また、分離原理とも同値になる。

は、よりも証明能力が高く、では非計算可能集合の存在を示せる。

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

上で、と以下の定理が同値であることが示せる。

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

2.3. 算術的内包公理 ACA0
-----------------

は、に算術的内包公理を付け加えた体系である。は、任意の算術的論理式を満たす自然数の集合の存在を示す。実際、算術的内包公理を得るために、にΣ1論理式の内包公理を追加したものである。

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

は、可述的数学のほとんどを展開することができ、古典的数学の基本的な定理の多くを証明することができる。

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

上で次とは同値。

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

2.4. 算術的超限再帰 ATR0
-----------------

は、に算術的超限再帰を追加した体系である。

は上で、Σ11分離原理と同値である。

は、の無矛盾性を証明可能なのでゲーデルの不完全性定理より、より強い。

で次がと同値。

任意の二つの可算整列順序は比較可能である。
可算被約アーベル群に対するウルムの定理。
完備可分距離空間の任意の非可算閉部分集合が完全閉集合を含むことを述べた完全集合定理。
ルージンの分離定理。
ベール空間における開集合の決定性。

2.5. Πp=1内包公理 Πp=1-CA0
----------------------

は、に論理式に関する内包公理を追加した体系である。は非可述的な体系である。

との関係は、との関係に似ている。

は、記述的集合論における強い非可述的論法によって証明される定理と同値になる。この同値性はこれらの非可述的論法が取り除けないことを示している。

で、と次の定理が同値であることが証明できる。

カントール＝ベンディクソンの定理。
任意の可算アーベル群は可除群と被約群の直和として書ける。

3. Big Five以外の体系
----------------

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

再帰的内包公理よりも弱い体系が定義できる。は、初等関数算術EFAに内包公理を付け加えた体系である。上で、は、可算な体の上で多項式が高々有限の根しかもたないことや、有限アーベル群の分類定理などと同値である。はと同じ証明論的順序数をもち、上文について保存的な拡大になっている。

は、に弱弱ケーニッヒの補題「無限路を持たない無限2進木のある部分木は、長さの葉がどれだけ存在するかを一様に推定できる」を追加した公理系である。は、上で「任意のコンパクト距離空間における任意のボレル測度は可算加法的である」等の測度論の定理と同値になる。のモデル理論は、アルゴリズム的ランダム列の理論と関連する。実際、の-モデルに対し, がのモデルであることと, に含まれる任意の集合について、に対し相対的に1-randomなあるが存在してがに含まれることは同値である。
DNRは、に「任意の集合に対し対角的非再帰な関数が存在する」を追加した公理系である。とはつまり「任意の集合に対して、ある全域的関数が存在して、fはから計算可能などんな部分関数とも等しくない」が成り立つということである。は、よりも真に弱い。.
「超算術的な集合全体からなる構造の上で成り立つ」「極小モデルは超算術的な集合全体である」という性質を満たす公理系はTheory of hyperarithmetic analysisと呼ばれる。Theory of hyperarithmetic analysisの例として、、、、はTheory of hyperarithmetic analysisがあり、それぞれに弱選択公理、内包公理、分離公理、選択公理を追加した公理系である。

4. ω-モデルとβ-モデル
--------------

「-モデル」のは非負整数全体の集合を意味する。

その1階部分が1階ペアノ算術の標準モデルになっているような、2階算術の部分体系のモデルを-モデルと呼ぶ。ただし、2階部分は非標準であっても良い。すなわち、-モデルはによって与えられる。数変数は の元として解釈され、定数記号や関数記号は標準的に解釈される。一方、集合変数は の元として解釈される。とする-モデルを2階算術の標準モデルと呼ぶ。しかし、標準モデル以外にも-モデルは存在する。たとえば、はとして計算可能なの部分集合全体をとった-モデルをもつ。

-モデルであって、文について、標準モデルと真偽が一致するものを-モデルと呼ぶ。において全ての-モデルがのモデルであることが示せる。また、において、「任意の集合についてを含むモデルが存在する」は と同値である。

一般に、-モデルであって、文について、標準モデルと真偽が一致するものは-モデルと呼ばれる。

また、Non--モデルも、ある公理系が保存的拡大であることの証明にしばしば登場する。

5. 参考文献
-------

6. 外部リンク
--------

[1]
[2]