ヒルベルトのプログラム

初めに記号があった. ~ヒルベルト~
 
 ■ ヒルベルトのプログラムHPとは
 1920年代,数学の巨匠ヒルベルトは,
記号の世界において数学そのものの模型,
今風にいうとバーチャルな数学を創造しょうと企てた.
 
どんな数学の難問も,記号世界の数学模型に投影させれば,
有限の組合せ問題になる.
 
そうすれば,絡んだ糸がいつかほぐれるように,
難問も必ず解けると考えたのである.
 
 
 20世紀の数学の健全な発展を期して,
1900年に彼が世に問うた23の問題(文献[3])も,
この頃には大半が解決されるか,少なくとも解決の見通しが立っていた.
 
しかし,誰にもどうにも手がつけられない問題に,
第1問題(連続体仮説),
第2問題(実数論の無矛盾性),
第10問題(不定方程式の可解性判定)などがあった.
 
すでに60歳に近かったヒルベルトは,
この新機軸をみずから証明論と名付け,
不屈の精神でこれらの問題に立ち向かった.
 
 ヒルベルトと優秀な門弟たちの精励により,徐々に部分的な成果が得られるようになったが,
最終的な念願のかなわぬまま68歳となったヒルベルトは,1930年にゲッチンゲン大学の定年を迎えた.
 
その年の9月始め,
ケーニヒスベルグ大学では3つの大きな会議
(4日~6日数学会,5日~7日認知論会議,7日~11日自然科学者医学者会議)
が並列して行われた.
 
ケーニヒスベルグで生まれ育ち,一度はそこで教壇に立っていたヒルベルトは,
市から名誉市民号を授与されることになり,
3番目の会議の中に設けられた記念講演(8日)において最後の雄叫びをあげた:

 我々は知らねばならない,そしていつか知るであろう.
 
 真に皮肉なことに,ヒルベルトの夢を砕く結果を携えて,
若きゲーデルが控えめに登場したのはその前日の認知論会議最終日であった.
(ヒルベルトは,みずからの講演準備に忙しく,ゲーデルの講演には出席していなかったらしい.)
 
ゲーデルの定理についてはあとでまた述べるが,
要するに記号世界の限界,つまりそこでできないことがあることを示したものであった. 
 
フォン・ノイマンらヒルベルトの側近たちは
ゲーデルの結果の重要性にすぐ気がついたが,その場でセンセーションが起きたわけではない.
 
基本的に彼らはみな数学者であった.
 
予想に反した結果が出てきても,それまでの研究成果の正当性が失われるわけではないし,
新しい結果を分析し過去の成果と融合させて,また別の予想を立てて進んで行くのが数学の道である.
 
実際,ゲーデルの仕事は,記号世界の限界を示しながらもその中身をより豊かにしたことにより,
その後の数学基礎論や計算機科学においてヒルベルトの証明論をさらに推進,発展させる役割を担ったのである.
 
 以下では,「ヒルベルトのプログラム」をHPと略称する.
 
HPとは,証明論の開発によって数学全体の明晰性をさらに高め,
それによって難問解決の端緒を見出そうというものである.
 
数学の明晰性は,完全性,無矛盾性,決定性(停止性),有限還元性(finitistic reduction)などの概念で具現される.
 
ヒルベルトは,数学の実世界と同型な記号世界を作れると信じていたので,
これらの目標は同時に達成されるはずのものであった.
 
しかし,現代的には無矛盾性プログラム,有限還元性プログラムなどと分けて考えるのが便利である.
 
基礎論研究者の間では,有限還元性(還元主義)プログラムを単にHPと呼ぶことが多い.
 
 ■ HPの起源
  ● 集合論と第1問題
 1862年生まれのヒルベルトが最初に証明した重要定理は,
「多項式イデアルは有限基底をもつ」という基底定理(1890)である.
 
当時この分野の第一人者ゴルダンが,
ヒルベルトの抽象的で非構成的な証明を指して「これは数学でない,神学だ!」と叫んだ話は有名である.
 
 その抽象的な論法のルーツはカントルの集合論にあったが,
カントルも「無限を扱うような研究は数学でない」という中傷をクロネッカーから受けて学会から冷遇されていたので,
ゴルダンの反応はヒルベルトにとって予期せぬものではなかったろう.
 
しかし,ヒルベルトは新しい道を猛進して次々と目覚ましい成果を上げ,
数年後にはゴルダンも彼の「神学」が優れていたことを認めた.
 
 1900年,すでにドイツを代表する数学者となったヒルベルトは,
パリの数学者国際会議で23の問題を提起した.
 
その第1問題は,カントルの連続体仮説「実数のどんな無限集合も,
可算集合(自然数全体と1対1対応が付く)か連続体(実数全体と1対1対応が付く)かである」を証明せよというものである.
 
これをトップにおいたのは,カントルへの畏敬の顕れであり,
また現代数学の基礎として集合論の重要性を確信していたからであろう.
 
 しかし,不思議なことにヒルベルト自身はなかなか集合論には手を出さなかった.
 
彼が連続体仮説の(無矛盾性)証明を試みるのは,
HPが成熟してきた1920年代半ばである.
 
その証明は彼には完成できなかったが,
のちにゲーデルが
連続体仮説CHと選択公理ACを成り立たせる記号的な模型Lを作った際の
プロトタイプになったと考えられる.
 
  ● 幾何学基礎論と第2問題
 ヒルベルトが1899年に発表した『幾何学基礎論』(文献[1])は,
いまで言うところのモデル論の本である.
 
ある公理系の中の一つの公理が他の公理から独立であることを示すモデル論的方法は,
その公理だけを成り立たせず他をすべて成り立たせるモデルを構築するものである.
 
すでに1870年代にクラインらは,
この方法で第5公準(平行線の公理)の独立性をエレガントに示しているが,
『幾何学基礎論』では,通常明らかと思われる諸公理に対しても公理同志の関係をモデルを使って系統的に調べている.
 
 とくに重要な結果は,ユークリッド幾何全体の無矛盾性を示すために,
その可算モデルを実数(代数的数)上に作ったことである.
 
この方法によって,ユークリッド幾何の無矛盾性は,
ある種の実数演算の体系(ヒルベルトが「算術」と呼ぶもの)の無矛盾性に還元された.
 
そこで,「実数論の無矛盾性を証明せよ」というのが,ヒルベルトの第2問題となる.
 
しかし,このとき実数論自体の公理化はまだ完成していなかったのである.
 
 実数論の公理化の難しさは,その中での自然数の扱いと,完備性の記述にある.
 
いま後者について簡単に説明しておこう.
 
実数とその上の演算に関するどんな公理系T(たとえば,実閉体の公理)に対しても,
Rの真部分集合(たとえば,多項式の解となるような実数全体)でその公理をすべて満たすものが存在してしまう.
 
そこでヒルベルトは,公理系Tのモデルの中で一番大きな(完備な)ものであるという主張を実数の公理に加えた.
 
モデルが最大かどうかは,モデルの外の世界に依存する性質なので,
完備性の公理が厳密な公理論の立場と相容れないのは明らかである.
 
ヒルベルトの基礎論研究の集大成である大著[2]以降,
実数論は自然数全体と自然数の集合たちを扱う2階算術(ヒルベルト・ベルナイスの体系とも呼ばれる)において展開するのが慣例となり,
2階算術の無矛盾性を示すことが第2問題であると考えられるようになった.
 
 ■ 決定可能性と完全性
  ● 公理系の完全性
 ヒルベルトは,実数の完備性にならって,
公理系Tが完全(英語ではどちちらもcomplete)であることを,
それより真に大きな無矛盾な公理系がないことと定義した.
 
つまり,完全な公理系Tから証明できない命題を1つでもTに加えると矛盾した体系になる.
 
したがって,Tが完全であることは,
どんな命題に対しても,それ自身かその否定かがTで証明できることと同じである.
 
 ヒルベルトは,どんな数学的な構造も完全な公理化が可能であると考えていた.
 
その構造で成り立つ命題が全て公理であるといってしまえば1つの完全公理系ができるが,
公理であるか否かが有限的に判定できないようなものは公理系と呼ぶに相応しくない.
 
そして,もしある構造に対して完全な(厳密な意味での)公理化が可能であれば,
その構造における任意の命題の真偽も有限的に判定できることがわかる.
 
これについてもう少し説明したいが,そのためにいくつかことばを用意しておこう.
 
  ● 再帰的集合と決定可能性
 自然数もしく有限の記号列の集合が r.e.(recursively enumerable, 再帰的に枚挙可能)であるというのは,
その要素をすべて並べあげる機械的な手続きがあることをいう.
 
たとえば,偶数全体とか素数全体は r.e.集合である.
 r.e.集合で,その補集合もr.e.になるものを,再帰的 (recursive)という.
 
偶数全体も素数全体も再帰的集合である.
 
再帰的集合Aに対しては,
その要素を並べあげる手続きと非要素を並べあげる手続きが両方あるので,
任意の自然数(また記号列)が与えられたとき,
それがAに属するか否かを,どちらの並べ上げに現れるかで有限時間内に判定できる.
 
それゆえ,再帰的集合は決定可能集合とも呼ばれる.
 
 
 我々が公理系と呼ぶものは,正確には再帰的公理系のことで,
公理の集合が再帰的であることを要請する.
 
そうすると,それから演繹される定理の集合が r.e. になるのは容易にわかる.
 
さらに,もし公理系Tが完全であれば,
Tの定理にならない命題Aの集合は,¬AがTの定理になるようなAの集まりと同じだから,
やはり r.e. になり,Tの定理の集合は再帰的である.
 
したがって,ある数学的構造に対して完全な公理系が見つかれば,
その構造における命題の真偽は決定可能である.
 
  ● 決定可能性と不可能性
 ゲーデルが1930年に発見した第一不完全定理は,
自然数論を含むどんな公理系も完全でなく,また決定可能でないというものである.
 
これから直ちに,ペアノ算術やZF集合論が不完全であることや,
自然数の構造(N,+,・,<)や有理数の構造(Q,+,・,<)における真偽が決定不能であることが導ける.
 
さらに群論,環論,述語論理(の定理全体)なども決定不能である.
 
 他方,決定可能な完全理論としては,
自然数上の足し算のみの体系,実閉体,代数的閉体,p-進体などが知られている.
 
したがって,実数の構造(R,+,・,<)や複素数の構造(C,+,・)における真偽は決定可能である.
 
 
 ある公理系(または構造)の決定可能性を示す有力な方法に,
タルスキが開発した量化記号消去法がある.
 
実(順序)閉体の場合,
∃x (ax^2 + bx + c = 0) が量化記号のない式 b^2 - 4ac >= 0 と同値になることはお馴染みであるが,
実数体上のどんな論理式(例えば,11次多項式が丁度7つの解をもつことを表すもの)も,
量化記号∀x,∃xのない等式,不等式だけの論理式に書き直せる.
 
これを使えば,実数の命題の真偽判定は,計算問題として解けるのである.
 
また,このことは,実数の構造(R,+,・,<)の上で,
整数であるという性質がうまく定義でないことを意味している.
 
 ■ 無矛盾性と有限還元性
  ● 無矛盾性プログラム
 『幾何学基礎論』でユークリッド幾何の無矛盾性を実数論のそれに帰着させたように,
ある理論のモデルを別の理論の中に構成することで,
相対的無矛盾性を示す方法はすでに確立された.
 
しかし,どこかに絶対無矛盾の拠り所を定めない限り,
この論法では永久に真の無矛盾性は保証されない.
 
その拠り所となるのが,
有限の記号を有限的にだけ扱う立場,いわゆる有限の立場である.
 
有限の立場は,
現代的には原始再帰的算術PRA(Primitive Recursive Arithmetic)として形式化されることが多いが,
その詳しい説明は省略する.
 
 有限の立場で扱える命題は,
量化記号∀x, ∃xを含まない算術的な論理式であると考えてよい.
 
しかし,x+y = y+x のように自由変数を含んでよいので,
これを ∀x∀x (x+y = y+x) のように書き換えれば,
外側だけに∀xのついた自由変数のない論理式(Pi^0_1 文と呼ぶ)を扱うと言い直しても差し支えない.
 
そして,有限の立場で正しいことが示されたPi^0_1 文は,
絶対に正しいということを以下の議論の大前提とする.
 
 
 さて,ある公理系Tの無矛盾性を示すにはどうしたらいいだろうか?
 
HPでは,矛盾命題(たとえば,0=1)が証明されないことを示すために,
公理系Tで証明されるPi^0_1文がすべて有限の立場でも(したがって絶対に)正しいことを示すことを目標とした.
 
 証明可能性を表す記号├を用いて,この目標を形式的に見てみると,2通りの解釈ができる.1つは,

   任意のPi^0_1文Aについて,(T├A)→A (1)

が正しいことを有限の立場で検証するもので,これを無矛盾性プログラムという.ここで,文(1)全体がPi^0_1文になっていることが重要である.もう1つは,

   任意のPi^0_1文Aについて,
   (T├A)→(有限の立場でAが正しい) (2)

を示すものである.こちらの方が幾分素直な解釈だと思うが,これを証明するためには有限の立場を形式化した上で,たとえば

   任意のPi^0_1文Aについて,
   (T├A)→(PRA├A)        (2')

 をPRAで証明することになる.((2')はPi^0_1文にならない.)これを有限還元性プログラムという.
 
 無矛盾性プログラムにおいて,Aを矛盾命題(0=1)とおけば,
(T├0=1)→0=1はT not├ 0=1と同値で,
これをゲーデルはTの無矛盾性を表す文 Con(T) と定義した.
 
従って,無矛盾性プログラムが成功すれば,Con(T) が導かれるわけだが,
逆に Con(T) から無矛盾性プログラムを導くことも容易にできる(演習問題).
 
ゲーデルは,ある程度の自然数論を展開できるどんな無矛盾な公理系T(例:ペアノ算術PA,ZF集合論)も
自らの無矛盾性Con(T)を証明できないことを示した.
 
これを第2不完全性定理という.
 
 ゲンツェンは,順序数ε_0までの超限帰納法を用いて,
ペアノ算術PAの無矛盾性 Con(PA) を証明した.
 
もちろん,ペアノ算術内部ではそのような超限帰納法は使えないのだが,
有限の立場にそれを加えることによって
ペアノ算術を包含するような強い理論ができるわけではないことも注意しておこう.
 
PAを自然に(PAで定義できる集合を扱えるように)2階算術に拡張してできる公理系を ACA_0 というが,
ゲンツェンの結果から直ちにこの体系の無矛盾性も得られる.
 
ACA_0 では,そこで定義される実数に対してボルツァーノ・ワイエルシュトラスの性質などが導けるので,
ACA_0 を実数論として見ても優れた体系であり,
ゲンツェンの結果は第2問題のかなりいい部分解になっていると考えられる.
 
さらに強い2階算術の体系については,現在もさまざまな研究が進行中である.
 
  ● 還元性プログラム
 T=PRAとしても,無矛盾性プログラム(T├A)→Aは,PRAで証明できない.
しかし,有限還元性プログラム(T├A)→(PRA├A)は,
Tをある程度大きくとってもPRAで証明できるのである.
 
 
 PRAに再帰的な集合が存在するという再帰的内包公理を付け加えた2階算術の体系を RCA_0 といい,
さらに無限2分木がかならず無限の道をもつという弱ケーニヒの補題を公理に加えた体系を WKL_0 という.
 
 WKL_0 では,実数の有界閉区間がハイネ・ボレルの意味でコンパクトであることがいえるし,解析学もある程度展開できる.
 
にもかかわらず,Pi^0_1文Aにたいして(WKL_0├A)→(PRA├A)となることがPRAで証明できる.
 
これをヒルベルトのプログラムの部分的実現と見なすこともできる.
 
 他方,Tを数学全体扱う大きな体系ZF+AC(選択公理)+CH(連続体仮説)とおいたとき,
任意の算術命題Aにたいして(T├A)→(ZF├A)が成り立つ事実も重要である.
 
これは,上に述べたゲーデルの模型Lの応用として導かれるが,
相対無矛盾性の結果Con(ZF)→Con(ZF+AC+CH)より実用的である.
 
たとえば,フェルマーの定理の証明に選択公理が使われているなら,
使わないような証明もあるということを意味している.
 
一般に,2つの形式体系 T_1⊂T_2 に対して,
ある論理式のクラスΓに属する T_2 の定理はすべてT_1 の定理でもあるとき,
T_2 はΓに関するT_1 の保存的拡大であるという.
 
いろいろな体系の間で,いろいろなクラスに関する保存的拡大の関係が調べられている.
 
 ■ 最近の話題から
 最後に,ヒルベルトのプログラム本来の趣旨からは離れるが,それと深く関わりをもつ最近の証明論の研究をいくつか紹介する.
 
  ● 数学的な独立命題の発見
 ある公理系で,証明も反証もできない命題を独立命題という.
 
ペアノ算術において、いわゆる自己言及文ではなく、
数学的に意味を持つ独立命題が存在するか否かは、
ゲーデル以来長らく基礎論の研究者の関心の的であったが、
1977年にパリスとハーリントンがラムゼイの定理の一変種がそれになることを示した.
 
 余白が少ないので,非常に大雑把な説明をしておく.
 
二つの自然数 a < b が大きく離れていることを,
その間にある種のラムゼイ性が成り立つこととして,算術的述語 PH(a,b) を定義する.
 
このとき,∀a∃b PH(a,b) は正しいのだけど,
a から b へは算術的に定義される関数では決して到達できないということが起こる.
 
つまり,∀a∃b PH(a,b) は,ペアノ算術PAで証明できない真なる命題になる.
 
具体的には,この命題からCon(PA)を導くことによって,その証明不可能性が示される.
 
 パリス・ハーリントン以降、2階算術の諸体系や集合論に対してまで種々の独立命題が発見されている.
 
  ● ゲーデルのプログラム
 パリス・ハーリントンの命題は,ペアノの算術PAでは証明できないけれど,
ある程度強い2階算術の体系,
たとえば算術的超限再帰(Arithmetical Transfinite Recursion)の体系ATR_0なら問題なく証明できる.
 
上にも述べたように,2階算術の体系にもいろいろな独立な命題があって,
それに対しては,さらに高階の算術体系や集合論を持ってくれば,たいがい証明あるいは反証されるようになる.
 
そして,ZF集合論の独立命題に対しては,
巨大基数の公理を仮定することで決定されるものが多い.
 
 こうして次々高度な集合を認める理論を作って行けば,
最終的にどんな命題の真偽もどこかで決定できるのではないかというのがゲーデルの予想であり,
とくにこの方法で連続体仮説の否定を証明しようというのがゲーデルのプログラムである.
 
ゲーデルは,自分に対するヒルベルト学派からの影響を軽視する傾向があったと言われるが,
ゲーデルのプログラムはあまりにヒルベルト的である.
 
「われわれは知らねばならない,そして知るであろう」という信念を,
いつのまにかゲーデルも共有しているかのようだ.
 
  ● 逆数学プログラム
 逆数学は,2階算術の枠組みにおいて,
ある定理を証明するのにどの程度の集合存在公理が必要かを調べるものである.
 
必要な存在公理によって数学の命題の世界に等高線を入れてみると,
数学史の流れや,異なる理論間の感覚的な類似性が,
うまく捉えられるというのがこの研究の売り物である.
 
たとえば,中間値の定理より実数の連続性公理(例:ワイエルシュトラスの上限に関する公理)の方が
強い存在公理を必要とすることが証明される.
 
それは数学史の流れがより高度な集合論を求める方向に進んだとも解釈できるであろう.
 
 
 すでに,2階算術の体系 RCA_0, WKL_0, ACA_0, ATRo を導入したが,
この他に (Pi^1_1)-CAoという体系もよく知られている.
 
1974年頃 H.フリードマンは,次のような現象に気付いた:

   数学の定理の多くはRCA_0で証明できるか,そうでなければ上にあげた他の
   4つの体系のどれかと論理的に同値であることがRCA_0において証明できる.

 これは「逆数学現象」と呼ばれ,
その後もこのパターンに当てはまる数多くの定理が S.シンプソンを中心とする研究グループによって発見されている.
 
例えば,ボルツァーノ・ワイエルシュトラスの定理はACA_0で証明できることを上に述べたが,
逆にボルツァーノ・ワイエルシュトラスの定理からACA_0も導けるのである.
 
  ● 実効還元性プログラム
 有限還元性プログラムは,
無限を扱う超越的な数学(の無矛盾性)を有限の立場(のそれ)に還元するものであった. 
 
有限の立場は,現代的には原始再帰的算術 PRA として形式化されると上に書いた. 
 
しかし,計算量理論の発達により,
もはや原始再帰的な計算は十分に構成的であるという感覚が薄らぎ,
それに変わって多項式時間計算可能性が,
より実際的な計算可能性を表すという見方が強くなってきた.
 
 
 多項式時間計算可能(実効的)関数の形式体系には,
コブハムの定理を基にしてクックが導入した PV がよく知られているが,
その他にも限定算術の体系 S^1_2 などがある. 
 
そこで,これらと無矛盾性において同等になる2階算術の体系を定義し,
そこでどれだけの数学が展開出来るかを調べようという研究が,最近始まった.
 
これを実効還元性プログラムと呼ぶ.
 
PV に対しPi^0_2保存拡大になっていて,
かつかなりの数学が展開できそうな体系として BTFA が有力視されているが,
いまのところまだ多くの成果は得られていない.
 
  ● プール=エルとクリプキの定理
 1960年代,プール=エルとクリプキは,
算術を含むどんな理論も,字面だけ見ればみんな同型になっているというすごい定理を発見した.
 
不完全性定理の最強バージョンともいえるこの結果には,さすがのゲーデルも驚いたらしい.
 
 
 昨年末のことであるが,
この定理が有限還元性プログラムについての筆者の予想を解く鍵になるというメールが,
この分野の大家であるS.シンプソン教授から届いた.
 
現時点では,まだ確かなことは言えないが,なかなか面白い事実が潜んでいそうな予感である.
 
 
(追記)この結果は,Simpson-田中-山崎の共著論文として発表されている.
 
 ■ 後書き
 昨年TIME誌が発表した20世紀の偉大な(影響力をもつ)科学者・思想家20人(正確には20組)にゲーデルとチューリングが入っていた.
 
他には,アインシュタイン,フロイト,ケインズ,ピアジェ,ライト兄弟から,
変わったところではWWWの開発者バーナーズリーもいた.
 
ヒルベルトの名はなかったが,ゲーデルやチューリングの仕事が,HPの延長上にあることは間違いないし,
このプログラムが人類にもたらした影響は21世紀にはさらに大きく見えることだろう.
 

参考文献
[1] ヒルベルト著(中村訳)『幾何学基礎論』弘文堂
[2] ヒルベルト・ベルナイス著(吉田・渕野抄訳)『数学の基礎』   シュプリンガー・フェアラーク東京
[3] 杉浦光夫編『ヒルベルト23の問題』 日本評論社
[4] 田中一之編著『数学基礎論講義』 日本評論社
[5] 田中一之編『数学の基礎をめぐる論争』  シュプリンガー・フェアラーク東京
Comments