数学基礎論と消えたパラドックス

 ■ はじめに
 ヒルベルトの提起した23問題の筆頭である連続体仮説の独立性をコーエンが証明してからちょうど30年になる.
 
集合論の研究者たちはよく冗談に“コーエン以前”をB.C. (Before Cohen の意)といい、
ゲーデル (Goedel) を B.C. の神 (God) であるといったりするが、
1960 年代には数学基礎論の各分野でこのような大事件が起きており、
まさに基礎論全体の変革期であった.
 
 
 60年代革命の激しさは、その教科書の変化によく現われている.
 
古き良き時代の教科書(例、文献[1])にはパラドックスから数学基礎論の誕生に至る歴史が悠然と述べられていたが、
革命後のもの(例、文献[2])にはパラドックスのパの字の解説もなく、それはもはや禁句になった感すらある.
(残念ながら日本では今もB.C. 時代のイメージが蔓延しているようで、それについては文献[5]の筆者のコメントを参照.)
 
 
 このような状況を踏まえた上で、なぜまたここでカビ臭いパラドックスの話を持ち出すかというと、
新歴30年を迎え、そろそろ新・旧基礎論を総括的に見直そうという気運が高まっているように思うからである.
 
最近次々と基礎論の専門誌の編集方針が変わったのだが、そこにもそういう動きが読み取れる.
 
 ■ 部分と全体のパラドックス
 「全体は部分より大きい」というのが、ユークリッドの8番目の公理だった.
この主張は日常論理では当たり前でも、数学的に意味するところは曖昧で、
そこにパラドックスの生まれる土壌があった.
 
ガリレオ・ガリレイ(1638)は平方数全体が自然数全体と1対1に対応していることに気が付いた.
 
 
   1、 2、 3、 4、 ...
   |  |  |  |
   1、 4、 9、16、 ... (注:本質的なことではないが、ここでは0を自然数から除く.)
 
 
 平方数全体は自然数全体の一部に過ぎないので、
上の状況はユークリッドの公理に矛盾するというのがガリレオのパラドックスの主旨である.
 
無限集合の扱いに慣れてしまった我々の感覚では、
もはやこれがパラドックスであるという感覚を持ちえないが、
これから述べるいろいろなパラドックスの原型になっていることは注意しておきたい.
 
ちなみに、ガリレオのパラドックスはクリーネの教科書[1]の第1頁に載っているので、
一昔前に基礎論をかじった人は誰でも知っていた話だが、
いまはそれを知らない基礎論の専門家も多いと思う.
 
また、デデキント(1888)は、このパラドックスを無限の本質と考えて、
全体が部分より大きいもの、つまり自分の一部分と1対1に対応できないものを“有限”と定義した.
 
 ■ 数えられる無限と数えられない無限
 自然数の集合Nの真部分集合でN全体と1対1に対応できるものは、
平方数に限らず、偶数全体とか素数全体とかいろいろ考えられるが、
逆にNを真部分集合として含んで、それと全体が1対1に対応できるものはあるだろうか? 
 
単純な例としては、整数全体Zが考えられる.そして、この延長でカントルは有理数全体QがNと1対1対応になることを示した.
 
 
 さて、次の問題は実数全体RとNの関係である.
これに対し、カントルは“対角線論法”と呼ばれる強力な手法を開発し、RとNとは1対1に対応できないことを示した.(後略)
 
 ■ 集合の世界のパラドックス
 対角線論法は、RがNより真に大きな集合であることを示しただけでなく、
どの集合にもそれより大きな集合が存在することを示すことになった.
 
つまり、集合Aとそのベキ集合P(A)={B: B⊆A} は1対1に対応しないことが、対角線論法で言える.
 
 それでは、集合全体の集合を考えたらどうなるか? 
 
これより大きな集合は定義からありえないので上の話と矛盾するというのがカントルのパラドックス(1899)である.
(これ以前にも、カントル(1895)とブラリ・フォルチ(1897)は、
順序数全体を考えることでパラドックスを発見しているが、ここでは省略する.)
 
 さて、この状況をエレガントに表現したのがラッセルである.
 
彼は S = {X : ¬(X∈X)} という集合を考えた.
 
つまり、Sは、自分自身を要素として含まないような集合Xの集まりであり、
普通の集合はみんなSに属するように見える.
 
では、S自身はどうだろうか? 
 
SがSに属しているとすれば、
Sは ¬(X∈X) の関係を満たすから、
¬(S∈S)、つまりSはSに属さない.
 
逆に、¬(S∈S) でも、
Sは ¬(X∈X) の関係を満たすから
S∈S となって矛盾する.
 
これがいわゆるラッセルのパラドックス(1902)である.
 
集合Sの定義にすでに対角線論法の構造が入っていることに注目したい.
 
 ■ 数の世界のパラドックス
 カントルやラッセルが創った集合はとてつもなく大きなもので、
今日の集合論では集合として扱わず
、クラス(class)と呼んで区別している.
 
こうすることで、集合論からパラドックスを排除したわけである.
 
しかし、リシャール(1905)はもっと身近な世界からもパラドックスが生じることを示した.
 
日本語で定義出来るような実数は可算(Nと1対1対応する)である.
 
なぜなら、日本語で用いられる文字は有限種類しかなく、
実数を定義する日本語の文を長さの短いものから順に並べていくことができるからである.
 
そこで、すべての定義可能な実数を並べると、
例の対角線論法でこのリストにない、つまり定義不可能な実数が構成できる.
 
しかし、この構成自身がその実数の定義になっているので矛盾するというわけである.
 
このパラドックスは、定義可能という言葉の一見合理的で実は曖昧な意味合いによっている.
 
もしも特定の公理系における定義可能性を考えるなら、
各実数は定義できても実数を並べる操作は体系外のものなので、
対角線論法で創られる実数は定義可能とはいえず矛盾は生じない.
 
 
 そしていよいよ、パラドックスの波は自然数の世界にまで押し寄せてくる.
 
「日本語で20字で定義できない最小の自然数」は20字で定義できているというのが、
ベリーのパラドックス(1906)である.
 
リシャール同様、定義可能性の曖昧さを突いたものだが、
表向き無限が登場しない単純さの中にむしろこのパラドックスの深遠さがある.
 
これについてはもう一度あとで触れる.
 
ベリー以後も、
グレリングのパラドックス(1908)、床屋のパラドックス(1918)など
論理的、あるいはパズル的なパラドックスが次々発見されているが、
これらは数学の基礎とは直接関係がないので他書に譲りたい.
 
また、選択公理に関連するパラドックス(バナッハ・タルスキ1924など)についても、
スペースの関係で省略せざるをえない.
 
文献[4]などを参照されたい.
 
 ■ 数学基礎論の誕生
 次々発見されるパラドックスの嵐の中で、
数学の基礎付け、特に集合論の公理化は着々と進んでいった.
 
ツェルメロやフレンケルらが今日の公理的集合論(ZF集合論)の土台を確立したのは1920年代前半である.
 
そのころ、スコーレムは、この種の公理化に重大な問題が潜んでいることに気付いた.
 
ZF集合論のように、可算個の公理からなる無矛盾な体系には、
それを満たす可算個の要素からなる構造が存在するというものである.
 
集合論の公理を満たす以上、その構造はすべての実数を含むはずだから、
これは実数が可算でないことと矛盾するように見える.
 
この事実はしばしばスコーレムのパラドックス(1922ー3)と呼ばれているが、
実はパラドックスというより集合の濃度の概念に新しい見解を与えた画期的な定理である.
 
つまり、集合論の可算モデルというのは、モデルを外から見ての話であり、
モデルのなかで自らが可算であるとわかっている(つまり、すべての集合を並べる関数がその世界に存在している)わけではない.
 
 ところで、この定理が実質上ゲーデルの完全性定理を先取りした内容になっていることは見逃せない.ま
 
た、1926年には、フィンスラーがリシャールのパラドックスから決定不能命題の存在を導いており、
こちらはゲーデルの第1不完全性定理の先駆となる.こうして歴史はいよいよゲーデルの登場を迎える.
 
 ■ ゲーデルの完全性定理
 ゲーデルの学位論文の主要結果である完全性定理(1930)には
いくつかの(本質的には同値な)表現があるが、次の2つが一般によく知られている.
 
 
(1)論理的に矛盾を含まない一階述語論理の体系には、
それを満たす数学的構造(モデル)が存在する.
 
(2)ある体系から一階述語論理の法則で演繹される定理の集合は、
その体系のすべてのモデルで成り立つ命題の集合と一致する.
 
ある公理系である命題が成り立つということを示す際、数学でよくやる証明は、
その公理を成り立たせる任意の構造を持ってきてそこでその命題が成り立つことを示すというものである.
 
(2)の意味するところは、
この証明法と同等になるほど一階述語論理の法則は十分強いということで、
その意味で完全なのである.
 
 ■ ゲーデルの不完全性定理
 今度は上と少し違う意味で“完全”という言葉を使うので注意されたい.
 
体系Tの言葉で表現されている命題Aが存在して、
Aもその否定¬AもTで証明できないときに、
Tを“不完全”という.
 
この意味では述語論理の公理だけの体系は明らかに不完全である.
 
 
 さて、ゲーデルが1931年に発表した論文によれば、
自然数論を含む無矛盾な公理系はすべて不完全である(第1不完全性定理)。
 
ここで、公理系というのは、有限的メカニズムで捉えらるような公理図式の集まりのことである.
 
現実世界で真となる命題を全部集めてきてみんな公理にすれば完全な体系が得られるかも知れないが、
それは議論の対象外である.
 
それから、ゲーデルの原論文では無矛盾より少し強いω無矛盾が定理の前提となっていて、
それを無矛盾に改良したのはロッサーの仕事(1936)である。
 
 ゲーデルは、第1不完全性定理の証明をさらに深く分析することで、
自然数論を含む無矛盾な体系Tにおいては、
Tの無矛盾性を表す命題 con(T) がTから証明できないことを発見した(第2不完全性定理)。
 
2つの不完全性定理はしばしば並べて書かれ、
一見類似した主張のようにも思えるが、
実はかなり性質を異にするものである.
 
第一定理の主張は一見パラドックスの話とは無縁に思えるが、
この定理の証明は「自分自身は証明できない」という意味の命題を創って、
対角線論法でそれが証明できないことを示すので、
カントル、ラッセル、リシャールの延長にあるといえる.
 
それに対し、
第2定理はよく「自分の正当性は自分自身で証明できない」というような比喩で語られるので
パラドクシカルな感じも受けるが、
実はパラドックスを“無矛盾性”という数学的な概念に置き代えているところが重要で、
その証明もリシャールからの流れだけでは類推しえない巧妙なものである.
 
“無矛盾性”を数学的な概念といったのは
、完全性定理によりそれは数学的なモデルの存在を意味するものだからである.
 
 
 ところで、ゲーデルは第2不完全性定理をきちんと証明したわけではない.
証明を頭に描いていたことは確かだが、
それを書き下すための細かいテクニックまで気付いていたかどうかは定かでない.
 
これを実際にやってみせたのは、ヒルベルトとベルナイスであり、
その後も多くの研究者が様々な改良や考察を加えて今日に至っている.
 
ゲーデルはリシャールのパラドックスを手本に第一不完全性定理を証明し、
それを第二不完全性定理に発展させたが、
ブーロス(1989)はベリーのパラドックスから第一不完全性定理を導き、
最近(1993)私の学生がそれをもとに第二不完全性を証明した.
 
 ■ 不完全性定理を越えて
 ゲーデル以降の基礎論の流れは、
不完全性定理を研究するというより、
いかにそれを乗り越えるかという主題で発展している.
 
まず、第2不完全性定理に真っ向から挑戦したのがヒルベルトの助手のゲンツェンである.
 
彼は、ペアノ算術(自然数論)では証明できないが有限の立場で認めうる論法(超限帰納法)を用いてペアノ算術の無矛盾性を証明した(1936).
また、タルスキらは実閉体や代数的閉体など完全な理論がいろいろあることを発見している(1949).
 
 
 ペアノ算術において、
いわゆる自己言及文ではなく、数学的に意味を持つ独立命題が存在するか否かは、
ゲーデル以来長らく基礎論の研究者の関心の的であったが、
1977年にパリスとハーリントンがラムゼイの定理の一変種がそれになることを示した.
 
ラムゼイの定理というのは、いまや組合せ論の定理として有名だが、
そもそもラムゼイはラッセルの下でパラドックスの分類などをやっていた論理学者であり、
彼の定理がここに登場するのも因縁めいた話である.
 
パリス・ハーリントン以降、算術に限らず集合論までこの種の独立命題が次々に発見されている.
 
これらの発見は、ある命題を証明するのに必要最低限の公理は何かという一般的な問いを生み、
“逆数学”という研究プロジェクトにも発展している.
 
これらについては別の機会に譲る.
 
 ■ H. フリードマンの定理
 さて、ここでガリレオのパラドックスの話に戻ろう.
 
自然数の集合Nから平方数の集合の上へ1対1関数f(x) = x2 があった.
 
この関数fは大小関係を保存している(x<) は自分と同型な部分構造を持たないことが簡単に証明できる.
 
そうすると、代数構造まで含めてユークリッドの反例になるものはあまりなさそうな気がしてくるのだが、
その感覚をひっくり返したのが フリードマンである(1973).
 
 
 言葉の説明を後回しにして、定理を述べる.
 
 
ペアノの算術の可算な超準モデルは、自らと同型な接頭部を持つ.
 
 
和積演算を伴った非負整数の集合をペアノの算術の“標準モデル”といい、
それと同型でない数学的構造でペアノの公理を満たすものを“超準モデル”という.
 
標準モデルはたった1つしかないが、
超準モデルは可算のものに限っても非可算無限個存在する.
 
超準モデルもペアノの公理を満たしているから、
その上に大小関係や和積演算が定義されている.
 
モデルの要素を大きさの順に並べて、
あるところで大きい方と小さい方に分け、小さい方を“接頭部”と呼ぶ.
 
どんな超準モデルも、
標準モデルと同型な接頭部を持つことが簡単に示せる.
 
そして、どんな超準モデルも
自分の縮小コピーを接頭部として持ついうのがフリードマンの結果である.
 
これは、自分と同じものは自分の中で造れないという第二不完全性(+完全性定理)と矛盾するようだが、そうではない.
 
なぜなら、接頭部の切り口が自分では見つけられない(定義できない)からである.
 
 
 この定理の証明がまた実に巧妙で面白い.
厳密な議論を紹介するスペースはないが、
以下に述べるアイデアからその卓抜さに共感戴ければ幸いである.
 
任意の超準モデルをMとする.
 
Mのなかのある超準数を固定して、それ以下のゲーデル数をもつ論理式に関して、
Mの真偽を反映させたモデルをMの中に構成する.
 
ある超準数以下というのはモデルのなかでは有限を意味するのでこの構成が可能なのだが、
外から見ればすべての論理式は超準数以下のゲーデル数を持つので、
結局論理的に同等なモデルが造れたことになる.
 
そしてこのモデルをシェイプ・アップして同型にするという論法である.
 
フリードマンのもとの証明はこれと少し異なるが、
詳しくは文献[3]などを参照されたい.
 
 ■ おまけ
H. フリードマンは 1967年に18歳でスタンフォード大に入った.
 
しかし、並の秀才と少し違うのは、このとき助教授として入ったことである.
 
彼はすでにその前に2階算術について画期的な仕事をしてMITから博士号をとっている.
 
一方、ガリレオは19歳で初めてユークリッドの原論に触れたというし、
ガリレオのパラドックスも70歳過ぎの話である.
 
 
参考文献
[1] Kleene, Introduction to Metamathematics, North-Holland 1952.
[2] Shoenfield, Mathematical Logic, Addison-Wesley 1967.
[3] Kaye, Models of Peano Arithmetic, Oxford 1991.
[4] バンチ著 細井訳、パラドックスの数理、共立出版 1984.
[5] 市川編、ネットワークのソフィストたち、日本評論社 1993.
Comments