ゲーデルの定理-2.3- 自然数の公理系

前回からの続き

　自然数の性質を公理化したものはペアノの公理系の名で知られています。これには色々な書き方がありますが、岩波数学辞典[ref-2) p474(183B項)]では自然数の集合Ｎを定義するという形で書かれています。

公理系Ｐ１ａ
1. ０∈Ｎ
2. ｘ∈Ｎ→ｘ'∈Ｎ
3. ｘ∈Ｎ→ｘ'≠０
4. ｘ'＝ｙ'→ｘ＝ｙ
5. (０∈Ｍ)∧(ｘ∈Ｍ→ｘ'∈Ｍ)→Ｎ⊂Ｍ

　ここでアポストロフィ記号を使った「ｘ'」は「ｘの後者」すなわちｘ＋１を意味する関数を記述します。また５は数学的帰納法の公理で、Ｍは「ある性質ｍを満たす要素の集合」と解釈でき、Ｎ⊂Ｍは「自然数の集合が、ｍを満たす要素の集合に含まれる」すなわち「全ての自然数はｍを満たす」ということを記述しています。また、公理２、３、４から「ｘの後者」という関数によりいくらでも新しい自然数が生じること、つまり自然数は無限に存在することが、厳密な証明は別としてもわかると思います。どこまでいっても次がある、ということですね。

　公理系Ｐ１ａを本記事で使用する書き方で変更すると次のようになります。ここでは「ｘ'」の替わりに「ｓ(ｘ)」を使いましたが、この方が「ｘの後者」というのが１変数関数のひとつであることがわかりやすいでしょう^*1。また公理５を解説すれば、Ｐ(０)は「０(ゼロ)について命題Ｐが成り立つ」ことを、Ｐ(ｘ)→Ｐ(ｓ(ｘ))は「ｘについてＰならばｘ＋１についてＰ」を記述しています。

公理系Ｐ１ｂ
1. ∃ｘ(ｘ＝０)
2. ∀ｘ{∃ｙ(ｙ＝ｓ(ｘ)}
3. ∀ｘ{￢(ｓ(ｘ)＝０)}
4. ∀ｘ∀ｙ{(ｓ(ｘ)＝ｓ(ｙ))→ｘ＝ｙ}
5. Ｐ(０)∧∀ｘ{Ｐ(ｘ)→Ｐ(ｓ(ｘ))}→∀ｘ(Ｐ(ｘ))

　なお最初の数を０ではなく１にする方式もあります^*2。また和や積の記号を最初から導入すれば直観的には見やすくなるでしょう。むろん和や積はｓ(ｘ)を使って定義できます。そして和や積が定義できれば、その逆関数として差や商や剰余も定義できます。

　また、５≡ｓ(ｓ(ｓ(ｓ(ｓ(０)))))のように各自然数にそれぞれの定数記号を定義することもできますが、左辺の記号がなくても右辺の記号列(対象式である)をそのまま使えばよいので、必ずしも新たな記号の必要はありません。大きな自然数に対するｓ(ｓ・・(０)・・))のような長大な記号列^*1を読み取るのは人間技では不可能ですがチューリング・マシンなら間違えないから大丈夫です。

　公理系Ｐ１ｂは自然数全体の集合をモデルとしますが、負の数を定義する公理を加えた整数をモデルとする公理系や、有理数の公理系、実数の公理系を作ることもできます^*3。ここで加える公理というものは、もちろん公理系Ｐ１ｂからは証明できませんが、それをもって公理系Ｐ１ｂが統語論的に不完全だというのは、ゲーデルの不完全性定理が意図するものではないはずです。というのは、前回の最後に書いた通りです。

　公理系Ｐ１ｂで証明可能か否かが問題となる閉論理式とは、モデルである自然数の集合で何らかの意味を持つ論理式です。そのような閉論理式のひとつ∀ｘ(Ｒ1(ｘ))および￢∀ｘ(Ｒ1(ｘ))がどちらも公理系Ｐ１ｂからは証明できないものとしましょう。このときモデルである自然数の集合では、対応する命題∀ｘ(Ｒ1(ｘ))は成立しているのでしょうか、いないのでしょうか。前回で述べたようにモデルでの真偽は定まっているものとみなすとすれば、命題∀ｘ(Ｒ1(ｘ))もどちらかに定まっているとみなさなくてはなりません。にもかかわらず証明できないとすれば、「真であるにもかかわらず証明できない」と言うことができるわけです。しかしちょっと待ってください。

　∀ｘ(Ｒ1(ｘ))も￢∀ｘ(Ｒ1(ｘ))も証明できないということは、命題∀ｘ(Ｒ1(ｘ))が成立しているモデル(図２のモデル１)も成立していないモデル(図２のモデル反１)も公理系Ｐ１ｂのモデルだということです。つまり公理系Ｐ１ｂは少なくとも２つのモデルを持ちます。そして我々が素朴に自然数の集合だと考えているものがどちらに当てはまるのかは有限の手続きでは決定することができません。無限の対象についての命題を確認する手段は数学的証明しかないのに、その数学的証明ができないのですから。


　　【再掲】　図２

　さらにゲーデルの不完全性定理によれば、公理系Ｐ１ｂに∀ｘ(Ｒ1(ｘ))や￢∀ｘ(Ｒ1(ｘ))を付け加えた公理系も、まだ統語論的に不完全です。ゆえに∀ｘ(Ｒ2(ｘ))も￢∀ｘ(Ｒ2(ｘ))も証明できないような論理式∀ｘ(Ｒ2(ｘ))が存在します。というわけで、公理系Ｐ１ｂからは証明できない無限個の論理式が存在し、それらの論理式はすべて自然数の集合で何らかの命題に対応しています。そしてそれらの命題の真偽がどちらであるかにより無数のモデルが存在することになります。そしてこれら無数のモデルの全てで成立する関係だけが真であるようなモデルを作る集合を仮にペアノ自然数とでも名付ければ、完全性定理により公理系Ｐ１ｂはペアノ自然数においては意味論的に完全です。

　そもそもペアノの公理系とは人間が素朴に自然数の集合と考えていたものをきちんと定義しようとしたものです。しかし実はその自然数の実体は唯一のものではなかったのです。それはペアノの公理系で完全に表現できるペアノ自然数を共通部分としながらも、そこに各々異なる真理が付け加わった無数のモデルの集合体だったのです。そしてこれら無数のモデルのうちで、我々が素朴に言葉にする自然数がどれに当てはまるのかは有限の手続きでは決定できません。これら無数の異なる真理は、人間の観測が届かない無限の彼方にあるのです。「真であるにもかかわらず証明できない」のではなくて、「有限の手続きでは真偽を決定できない命題は証明できない」と言うべきなのです。といえば、何か当たり前の真理に聞こえるようになりますね。

　そう、今にして思えばゲーデルの不完全性定理とは何も不思議な定理ではなく、「無限集合についての命題で有限の手続きでは確認不可能な命題には、有限の証明列が存在しないものがある。」という、ごく自然に見えることをキチンと証明したところに意義があったのだと言うべきでしょう。

　次回はさらに具体的証明に踏み込みます。


－－－－－－－－－－－－－－－－－－－－
*1) 類書ではほぼすべてｘ'方式であり、表記が短くなる利点はある。ただ、どうせ例示でのなるべく短い表記にしか使わないので本記事ではｓ(ｘ)にした。等号も本来は関係記号でありEq(ａ,ｂ)などと表記してもよいが、こちらは非常によく使うので慣れてわかりやすい表記の方がよいだろう。
*2) 一般には０は自然数に含めないとする考え方が多そうだ。しかし０はイメージ的に空集合に対応させやすいので、何かと考えやすいという利点がありそうだ。
　[注]「０は自然数に含めないとする考え方が多い」という記述には根拠がなかった。０(ゼロ)は自然数か否か -1-参照。
*3) 負の数を導入すると公理３を破棄することになるだろうから、以下の議論には使えない。しかし正の有理数を導入するだけなら例としてたぶん大丈夫だろう。