「ゲーデルの不完全性定理」を学ぶ（その1）

「数学の中の無限」への扉へもどる

◆はじめに
小学６年生の頃だったでしょうか。算数の応用問題を自分の考えついた方法で解いて正解が出たとき、
論理さえ正しければ、解法の如何に拘わらず、
必ず同じ正解に辿りつく算数（数学）の面白さと不思議さを感じたことを今でも覚えています。

それは、いわば"数学の無矛盾性"に対する感動、ともいうべきものであり、
私にとってそれが数学を好きになったきっかけのひとつだったのですが、
ゲーデルに言わせれば、数学においてそんなことは保証の限りではないということになるのでしょうか?!
勿論、我々が扱う実用レベルの数学においてそんな心配は無用でしょうが…。

「ゲーデルの不完全性定理」―今は教養書でおぼろげながらそのアウトラインを知ったという段階で、
まだ狐につままれたような感が拭いきれないのですが、
今後、人間の思考・理性、各学問分野の論理構造などを探究する上で、何やら鍵になるような気がするので、
取り敢えず、その概要をここに書き留めておき、さらに科学ロマンの旅を続けようと思います。
旅の途中で、「あぁ、そういうことだったのか！」と深い理解に至ることを期待しつつ…。
1. ゲーデルの第一不完全性定理
「自然数論を含むような形式的体系Ｓが無矛盾であれば、
　それ自身もその否定も証明できないような命題がＳの中に必ず存在する。」

1)「形式的体系」とは、
　「公理系（対象についての規定＋推論の論理法則）で規定される形式的な演繹体系」のことであり、
　その内容は全て記号で表現できます。

2)いま、自然数の型であるような１つの自由変数（自然数ｋと対応付ける。）を持つ論理式を考えます。
　論理式は対象記号、関数記号、変数記号、論理記号、それに自然数に関する（公理化された）記号など、
　たかだか可算個の記号を有限個並べたものにすぎず、その数はたかだか可算個しかありません。
　よって、自由変数ｋについての論理式全体には順番が付けられます。
　そこで、ｎ番目のものをPn(k)と表すこととします。

3)kは自由変数だから、k＝nの場合、すなわち、Pn(n)もSの中に存在します。
　また、この否定￢Pn(n)も存在します。

4)さらに、形式的体系では「証明」も公理系に基づいた記号の有限列にすぎず、
　「証明可能な論理式」を定義することができます。
　よって、Sの中には
　ｎを自由変数として「￢Pn(n)は証明可能な論理式である」ことを意味する論理式も存在します。
　そこで、これをProv(￢Pn(n))と表すこととします。

5)このProv(￢Pn(n))も自由変数nについての論理式であり、ある自然数rが存在してPr(n)と表せます。
　すなわち、Prov(￢Pn(n)) ⇔Pr(n)
　ｎは自由変数だからn＝ｒとすれば、Prov(￢Pr(r))⇔Pr(r)
　∴￢Prov(Pr(r))⇔Pr(r)　…＊

6)これより、次のことが言えます。
　① Pr(r)が証明可能ならばPr(r)は真。このとき、＊式より￢Prov(Pr(r))が成り立ち矛盾。
　② ￢Pr(r)が証明可能ならば￢Pr(r)は真。このとき、＊式よりProv(Pr(r))が成り立ち矛盾。
　よって、肯定も否定も証明できない命題は必ず存在することとなります。

7)証明のエッセンスは以上ですが、ゲーデルは
　① 自然数の素因数分解を応用した「ゲーデル数」の概念を導入して論理式と自然数を対応させた上で、
　② 帰納的関数（その関数値を確実に計算する方法が存在する関数）の理論を創始し、
　　　論理式間の関係と自然数間の関係とが同一構造を持つことを確認することにより、
　これを数学的に厳密に証明しています。

8)なお、＊式のPr(r)は「自分自身が証明可能ではない」と主張している命題であり、
　この数学上の大発見が実はいわゆる「リシャールのパラドックス」や「うそつきのパラドックス」といった
　否定的自己言及によるパラドックスと論理的に共通するものであることがわかります。
　数学からパラドックスを追放し無矛盾性を手に入れようと努力した結果、
　それと同様の論理構造の定理によって無矛盾性の証明に引導が渡された（第二不完全性定理）なんて、
　何と皮肉なことでしょう。
　これを、人間が傲慢に理性を振りかざすことに対する神からの警鐘と捉えるのは考え過ぎでしょうか。
2. ゲーデルの第二不完全性定理
「自然数論を含むような形式的体系Sが無矛盾であれば、
　その無矛盾性をS内で形式化された論理でもって証明することはできない。」

1.で述べたPr(r)は「体系Sは無矛盾である」という具体的命題をSで形式化したものとすることができることから、
上記第二不完全性定理が成り立ちます。
3. ゲーデルの業績
① 1930年「第一階述語論理(∀,∃を含む数学の論理)に関する完全性定理」の証明を発表。
※ 同論理の無矛盾性はその前にアッカーマンにより証明。
② 1931年「自然数論を含む数学的体系に関する不完全性定理」の証明を発表。
③ 1938年「連続体仮説の無矛盾性」の証明を発表。
※同仮説の独立性はその後にコーエンにより証明。