副題に「数学的体系のあゆみ」とある。
ゲーデルの不完全性定理の初歩的な入門書である。不完全性定理を理解するにはまず、記号論理学に基づいた数学基礎論、すなわちヒルベルトの公理論を知っておかねばならない。ヒルベルトについては、既に『幾何学基礎論』を紹介した。公理主義はあらゆる数学体系の基礎をなすものだが、公理論が意識される前から発達していた (というよりも、公理論そのものの基盤となった) 系に、ユークリッド幾何学がある。そもそも、ヒルベルトが公理主義を適用するに相応しい題材として選んだのも幾何学であった。
したがって本書は、ユークリッド幾何学の歴史から始まる。ユークリッド幾何学はこの世界の近似でも何でもなく、ある公理群から演繹的に導かれた体系に過ぎない、というのが公理主義の立場である。適切な別の公理に基づけば、非ユークリッド幾何学が展開される。ユークリッド幾何学と非ユークリッド幾何学は互いに矛盾するわけではない。出発点である公理系が異なるだけである。というのがポイントだ。
続いて集合論の歴史が語られる。集合論は非常に強力なツールではあるが、「無限の」集合を扱い出すと途端に怪しくなる。加算無限と非加算無限といった、性質の異なる「無限」が現れたりする (これ自身は矛盾でも何でもないが)。問題なのは、カントール集合と呼ばれるパラドクスである。
どんな集合 X が与えられても、それより大きい集合 Y が存在する。
これはカントール自身が証明した定理だが、このとき、集合 X を「すべてのものの集合」と置いてみると、深刻な矛盾が発生する。これによって集合論は破滅の危機を迎えたが、別の側面からいえば、新たな数学の基礎付けを促すものでもあった。ここから、現代数学に通じる厳密な基礎が数学に与えられる。例えば、上のカントール集合におけるパラドクスは「自己言及」によるものである、という共通の理解が成立する。「自己言及」の最も簡単な命題の 1つは、
私は嘘つきだ。
というものがある。この命題が真か偽かは決定できない。こういう文を数学で使ってはならない。また、集合には階層がある、などといったルールが整備され始める。そういった中で、直感主義だとか排中律の問題が出てくるわけだが、こうして数学と論理学は急速に接近していく。
このような基礎の課題が出された後、今度は証明そのものを形式化しようという動きが出てくる。数学の証明は論理的な演繹によるが、その「論理的な」という部分を機械的に処理できるように記述しよう、というのが形式主義である。これは公理主義と密接な関係がある。幾何学において「点、線、面」を「テーブル、椅子、ビールコップ」と呼んだところで幾何学的には何ら変わらない、という考えを証明方法にまで敷衍したのが形式主義である。
論理的な演繹とはすなわち、命題の関係の機械的な操作ともいえる。例えば、「命題 P が真かつ命題 Q が真なら命題 R が偽」を、
P ∧ Q ⇒ ¬R
と書くやつである。正しい推論、すなわち命題関係において許される操作をこのように公理化することによって、コンピュータもロジックを把握できる。こうして、全ての数学の基礎は論理公理系と、その推論規則群に置かれるようになった。
ここでようやくゲーデルが登場する。300頁未満の本書において、233頁になってようやくゲーデルである。準備が大変である。
ゲーデルが考えたのは、自然数論を含む無矛盾の体系 Z について、である。俺が理解した範囲で、証明のあらましを書いておく。
- 体系 Z における全ての記号 (を含む記号列) を一意の自然数 (ゲーデル数) に置き換えることができる。
- 自然数 n と対応するゲーデル数を、関数 g (n) で表す。
- 「q は体系 Z の中で証明できる論理式のゲーデル数である」という論理式を Provable (q) とする。
- Provable (q) 自体も体系 Z の中で具体的に構成できる。
- ある論理式 P (x) のゲーデル数を p とする。
- 「変数 x」のゲーデル数を X とする。
- 「P (x) の変数 x に自然数 n を代入した論理式のゲーデル数」を表す関数 sub (p, X, g (n)) を考えよう。
- もちろん、sub (p, X, g (n)) も体系 Z 内で具体的に構成できる。
- ここで、sub (x, X, g (x)) を考えよう。
- ¬Provable (sub (x, X, g (x))) を G (x) (ゲーデル文) とする。
- 当然、G (x) も体系 Z 内の論理式である。
- G (x) のゲーデル数を h とする。
- G (h)
⇔ ¬Provable (sub (h, X, g (h))
⇔ sub (h, X, g (h)) は証明できない
⇔ G (x) の変数 x に h を代入した論理式は証明できない
⇔ G (h) は証明できない
したがって、ゲーデル文は形式的に正しいが証明できない。無矛盾の体系の中には、このような証明できない論理式 (つまり命題) が存在する。これが第一不完全性定理である。順を追って行けば、それほど難しいことはない。まァ、これも長い前説があってのことだが。という本書の構成の意図が、やっとここでわかってくる。
第二不完全性定理については簡単に書いておく。
体系 Z が無矛盾ならば、Z の無矛盾を Z の中で証明できない
これも強烈な定理である。証明に興味がある方は、本書を読んでほしい。