ゲーデル本食い歩き - hiroyukikojima’s blog

文末に付記があります(12月16日記載)
以前、銀座のフレンチレストランのランチを食べに行ったときのことである。1人で来ていた御曹司風の若い男性が、シェフを呼んで、講釈をたれていた。いわく、「〇〇さん、最高の中華フルコースはどこの店だかわかりますか？」。シェフが、「さあ、どこでしょうねぇ」と答えると、男はこういった。「まず、〇〇で前菜を食べるでしょ、そして、店を出てタクシーで〇〇に行って、フカヒレのスープを飲み、また、タクシーで〇〇まで移動して、ペキンダックを食べる・・・」。この調子で男は、デザートまでのすべての料理を店別で食べるフルコースをあげたのだった。(嫌な野郎だった)。
だけど、数学を勉強するときは、こういう方法が有効であることがままある。どの数学書も、すべての点でわかりやすいわけではない。著者の何かの意図があって、そのために、わかりにくい場所も出てきてしまう。例えば、定理Aを証明する場合、それだけをしたいなら、もっと簡単なセッティングで、もっとわかりやすい証明があるにもかかわらず、本の後半で別の定理Bを紹介したいがゆえに、その準備として定理Aのセッティングや証明をわざと一般化したり、凝ったものにしておくことがままある。そのため、定理Ａだけをストレートに理解したい読者には、かえってわかりにくい本になってしまう。
ぼくは、ここ数年ずっと、ゲーデルの不完全性定理を理解したくて勉強を続けてきた。それは、中学生のときからの望みだったからでもあるし、現在、専門としている経済学の研究に活かしたいからでもある。その勉強の中で数冊の本を読んだけれど、どの本にも長所と難所があり、結局、ほぼ完全な理解に達するために、「店を移動してのフルコース」をするはめになった。読んだ本は、以下である。(啓蒙書もたくさん読んだけど、ここでは専門書だけを読んだ順に挙げる)。
[1]数の体系と超準解析(田中一之)
[2]数学基礎論入門(前原昭二)
[3]数学基礎論(新井敏康)
[4]The Logic of Provability(George Boolos)の2章のみ
[5]数学基礎論講義(田中・鹿島・角田・菊池)
　不完全性定理とは、「PAと呼ばれる自然数の公理系が無矛盾であれば、文φで、PAではφも¬φ(φの否定文)も証明できないものが存在する」という定理である。PA(ペアノ公理系)というのは、明確な演繹規則を備えた自然数に関する公理系のことで、我々の頭の中の(数学者の頭の中の、というべきかもしれない)自然数の公理系とは別の存在である。我々の頭の中の自然数のシステムを、区別するために、「標準モデル」と呼ぶ。この定理の証明では、ざっくりとまとめると、PAの次の性質が本質的と(ぼくには)思われる。
(i)PAは、述語論理である。
述語論理は、命題論理よりも数学的に豊かな内容が記述できる。命題論理とはp→qとかp∨qなど文字を論理記号で結んだだけのもので、pやqなどが持つ内容には踏み込まないもの。それに対して、述語論理とは、「関数」や「関係」が導入され、数学的な内容が表現できる。例えば、R(x,y,z)をx+y=zという関係と定義したり、T(x,y)をxnとするとき、φがPAで証明できるならば、Pr(n)もPAで証明できる。
まず、Pr(n)とPr(n)の区別に用心する必要がある。実は、ぼくにはこれがなかなか理解が大変だった。nを自然数とする述語論理文Pr(n)は、標準モデル(我々の頭の中の自然数)として、「nをゲーデル数とする論理式は証明可能」という意味だが、Pr(n)は、自然数nを数字n(これは0の前に記号sがn個ついたもの)に置き換えるだけではなく、すべての関数や論理式をPAにおけるコード化された解釈に置き換えた論理文である。つまり、前者は我々の頭の中の論理文で、後者はPAにおいて形式化された論理文ということになる。そして、論理文φがPAで証明可能なら、φのコードを(sの並ぶ)数字で表したものを述語PR( )に代入したPAの論理文もPAで証明可能ということを意味している。例えば、φを「1+1=2」という論理文とし、そのコードが(そんなに小さくはないが)仮に7であるとしたら、φは正しい文なのでPAから証明でき、したがってPr(sssssss0)という文もPAで証明できる、と主張しているのである。これは、アタリマエにも見えるし、とても不思議にも見える。φの証明である論理式の記号列を、すべてコード化して形式化したものがPr(n)なのだから、PAの演繹システムでこの文に到達する証明を書くことは、単にφの証明をトレースしていけばいいだけと思えば当たりまえだし、他方では、そういう膨大にして殺伐とした論理文をPAの規則で導くことができる、というのは不思議といえば不思議にも思える。
(v) PAの1変数の論理式φ(x)が任意に与えられたとき、論理文Fをうまくとることによって、Fのコードの数字をnとして、「F←→φ(n)」という論理式がPAで証明できる。(不動点定理)
この不動点定理が、不完全性定理の証明の中で、最も面白い補題に思える。どんな1変数の論理式φに対しても、その変数にコードを代入した論理式が、そのコードの表す論理式と同値になってしまうような論理式Fが存在する、というのだから、これはさすがに不思議だ。これの証明のポイントになるのは、「xの式にxの式を代入することができる」という、中学生から習う文字式の代入の性質なのである。たとえば、3x+5のxにx+7を代入することができる。xとx+7は絶対に等しくはなれないが、にもかかわらず代入することは問題ないのである。なぜなら、3x+5をいったん3y+5と書いても「式が意味する計算」は変わらず、そのyにx+7を代入するなら全く問題がないからだ。プログラミングになじんでいる人には、x=x+7などという記述は全く平気であるが、それと同じことである。この不動点定理が証明できるところに、PAという述語論理の体系のもっとも面白い部分があるようにぼくは思う。
　さて、以上の(i)から(v)を理解できれば、不完全性定理の証明はもうそんなに遠くはない。
まず、(v)において、φとして¬Pr(x)を取る。そうすると、(v)から、「F←→¬Pr(n)」という論理式がPAで証明できるような論理式Fとそのコードの数字nが存在する。このFがPAから証明も否定もできない文(ゲーデル文)となる。なぜなら、ここで、このFがPAから証明できると仮定すると、、「F←→¬Pr(n)」という論理式がPAで証明できることから、¬Pr(n)がPAから証明できる。一方、(iv)から、Pr(n)もPAから証明できる。肯定文も否定文も証明できるということになると、「PAが無矛盾であるとすれば」、という仮定に反してしまう。したがって、文FはPAでは証明できない。次に、¬FがPAから証明できないことであるが、こちらは1−無矛盾性とかωー無矛盾性とかの仮定をすれば簡単に証明できるし、単なる無矛盾性からもロッサー文というのを構成すれば証明できる。
　以上、がんばって、ゲーデルの不完全性定理の証明のぼくの理解を書いてみた。(疲れた)。ここで言いたいのは、これらの全体を理解するには、先に挙げた5冊の本を「はしご」するほうがいい、ということなのだ。
まず、最も良い本は[3](新井)であることは疑いない。ぼくはこの本を読んで、一気に積年の思いを果たすことができた。これほど見事に構築された本にはなかなかめぐりあわないだろう。ただし、この本にもいくつか難所がある。まず、「演繹(シンタックス)」についての説明が、初学者にはきついかもしれない。完全性定理と不完全性定理の説明を両方ともうまく行うために選んだのであろう演繹システムなのはわかるが、初めての人は自分の理解している演繹のシステムとかけはなれていることにとまどうことになるだろう。そういう人は、[1](田中)か[5](田中他)の該当箇所を読んだほうがいいと思う。前者では、ゲンツエンの演繹システムを使っており、これは我々が普通に行う推論なのでとっつきやすい。(その代わり、コード化するときに、逆に複雑になる)。また後者は、[3](新井)と同じく、ヒルベルト流の少ない演繹システムを使っているが、その説明はとても優れており、読んでいて楽しい。また、[3](新井)には、Σ1完全性の例が一つも紹介されない。とにかくこの本は、例がなさすぎる。なので、Σ1完全性の例は、[2](前原)か[5](田中他)で補充したほうがいい。中でも後者は、簡潔にその意味をわからせてくれる例が入っていてよかった。それから、[3](新井)で最も理解が難しかったのは、(iv)の部分だった。形式化された論理式Pr(n)についての説明がたったの3行でなされ、例もたった一つだにないため、最初、何を言っているのかさっぱりわからなかった。ここについては、[1](田中)も[5](田中他)もあまりわかりやすくないと思う。そこで、[2](前原)の該当部分を読み、そのあと、[4](Boolos)を読んだ。この合わせ技でなんとか理解に達した。とりわけ、[4](Boolos)の第2章はすばらしいと思う。原子再帰的という概念を表に出さず、基本的にコツコツとPr(x)を構築していく説明は見事だった。(ゲーデルの証明を忠実に再現したのだろうと思うが)。また、わざと論理文を使わずに、ことばで(英語で)表現していく手法は、読みやすさを生み出していた。もちろん、これは、ぼくがある程度理解している上で読んでいるからわかることで、最初にこれを読むと(ことばで説明されることに)混乱するかもしれない。とりわけ、この本は、基本的には様相論理を解説する本であるから、最初にアプローチすべき本ではないということは確かだ。
以上から、総合的に評価すれば、[3](新井)が最もよく考え抜かれ、最も丹念に構築されていると思う。その上で、「はしご」はとても有益である。それぞれに焦点が異なり、その焦点のためにいろいろな工夫がなされている。そして、それぞれの工夫の帰結として、わかりやすい場所とわかりにくい場所が異なっているわけなのである。
(いつものこととは言え、なげ〜な〜。笑い)。

付記というか弁解(12月16日)：　ぼくのこの記事に対して、難癖をつけている人がいて(2011-12-14 - /dev/wd0a）、完全性定理の理解を間違ってるって。まあ、いいんだけど、それなりに理解してるつもりではあります。命題論理のほうも、述語論理のほうも。「付値が1」という文章を入れてあることで、p,q,r・・・等の記号には(任意の、ではなく、特定の)付値が導入してあることをちゃんと示唆したつもり。しかし、これはけっこうまずかったかな。正確には、記号pかまたはその否定¬pで付値が1のほうは、理論Tに公理として入ってることを暗黙の前提に書いた。(そうじゃなくて、単なる記号としてpとかqとかが出てくる公理系なんて無意味だから無視する、という思い込みがあった)。頭の中に理論T(素論理式かまたはその否定で付値が1のものの集合)がイメージとしてあったので、書き忘れてしまった。それならば正しいはずだよね？([1]新井の定理1.5.10、43ページ参照、ぼくにはこの補題のほうが「トートロジーは証明できる」という完全性定理より面白く思えたから、こっちを紹介したかった）。専門家ならぼくがいいたことを(自分なりに修正して)わかってくれるだろうと予想していたが、甘かった。でも、確かに暗黙の前提にするには、大胆すぎたとは反省する。そういう意味では指摘については本当にありがとう。指摘の仕方については、あまり専門家の良心を感じられないけどさ。最初は「トートロジーは証明できる」と書いたんだけど、これだと不完全性定理と対応しなくなっちゃうので、命題論理の完全性定理の証明の補題として使われる定理に入れ替えてみたんだけど、それが冒険すぎたのかもしれない。完全性定理について、こういう言い方をするのは、「専門家的には」正しくないのかもしれないね。けれど、それにしても、ここでもまた、吉永さんの名前とか出して、悪口をいってて、それについては気分が悪い。なので、数学ライターのはしくれとして、ここではそういう上から目線の罵詈雑言に抵抗しておこうと思う。そういう専門家の細かい批判に答えるには、結局は専門書のように記述するしかなくなり、そういうことになると、啓蒙書とかブログとかで、数学や科学について、一般の人に伝わるように書くことができなくなっちゃうし、それは数学文化や科学文化の衰退をもたらすと思うんだけど違うかな。ぼくはできるだけ、数学の魅力とか(経済学を含む)科学の魅力を多くの人と共有したいからこういうブログを書いており、しかし専門家の人向けには、「ここは、はしょってますよ」とか「ここは大胆な解釈をして冒険してますよ」とかをひっそりと伝えるために、「付値が1の論理式」みたいな示唆を入れて、「専門家なら専門家として、何を書きたいのかを好意的に類推してください」と言ってるつもりなんすよ。(もちろん、完全な間違いを書いてしまうこともある)。なので、こういう人が、こういう「物言い」をしたがるのをみると、とても悲しくなっちゃうのです。ぼくの記述が間違ってるというなら、みんなの利益になるように、自分の「完全性定理」の理解を(専門家同士の呪文じゃなく、一般の人に伝わるように)きちんと書けばいいのに、そうしたほうがみんなへの貢献になるのに、と思うのにな。もっと嬉しいのは、「ここをこう修正すれば、あるいは補足すれば正しい」と言ってくれることだけど、それは虫が良すぎるかね。笑い。まあ、そんな暇じゃない、のかもしれないし、そういうことに効用は感じないで、人のあげあしをとるほうに効用が高いなら仕方ないと思う。まあ、世の中、いろんな人がいていいのだけどさ。それが経済学者としての人間の理解(達観)。まあ、いろいろ見苦しい言い訳をしたけど、結論をいうと大変感謝しております。再度、ありがとうございました！