「我流でゲーデル解釈」について VI

2009-03-21付記事のコメント欄に書きましたが、元記事の著者には、元記事を改変または削除する権利があります。それは著作者の権利として尊重されるべきです。改変または削除があっても、私は非難しません。読者のみなさまにおかれましても、同様に著作者の権利を尊重されることを期待します。

ちなみに、元記事の改変または削除があっても、他の人が改変前または削除前の記事を引用して論評する権利には影響がありません。公表された著作物を引用して利用することは著作権法で認められており、いったん公表された著作物を未公表の状態に戻すことはできないからです。

ということになる。 どんな論理体系であっても、それが可能であることを、ゲーデルは示した。
そこに矛盾が生じず、判定不能に陥ることもない。 だから、「完全」 だというわけである。

「どんな論理体系であっても」と「判定不能に陥ることもない」が致命的な誤りであることは、何回かにわたって解説しました。そこで、「そこに矛盾が生じず」ですが、結論からいうと、これも誤りではあるが、他に比べると傷の浅い誤りです。完全性定理そのものは無矛盾性についての定理ではありませんが、一階述語論理の健全性の系として一階述語論理の無矛盾性が導かれるからです。

先に進む前に用語の再確認をしておきましょう。

証明可能性

論理式が公理と推論規則から導かれること

恒真性

論理式がすべての解釈で真となること

完全性

論理体系のすべての恒真な論理式が証明可能であること

健全性

論理体系のすべての証明可能な論理式が恒真であること

ゲーデルの完全性定理が発見される直前の状況はこうでした。

• 命題論理が完全かつ健全であることは知られていた。
• 一階述語論理が健全であることも知られていた。
• 一階述語論理の完全性は未解決問題だった。

この状況でさっそうと現れて未解決問題を解決したのがゲーデルで、解決されて問題から定理になったのが完全性定理だったのです。

一階述語論理の健全性から、一階述語論理の無矛盾性はただちに導かれます。一階述語論理が矛盾すると仮定します。矛盾の定義より、ある文(自由変数をもたない論理式。閉じた論理式や閉式ともいう) が存在して、 も も証明可能です。一階述語論理の健全性より、 も も恒真です。しかし、解釈の定義により と が同時に真になる解釈は存在しません。したがって、一階述語論理は無矛盾です。

ということで、「そこに矛盾が生じず」は、完全性定理は無矛盾性に関する定理ではないので間違いですが、完全性定理とまったく無関係でもないので大間違いではありません。せいぜい、小間違いでしょう。

ところで、

ゲーデルと20世紀の論理学(ロジック)〈2〉完全性定理とモデル理論

に興味深い話が紹介されています。後になったわかったことですが、エルブランとスコーレムが、完全性定理を半分ずつ証明していたのです。つまり、エルブランの定理とスコーレムの定理から完全性定理がただちに導かれるのです。

勝手に想像を広げると、エルブランとスコーレムがタイミング良く接触していたら、エルブランとスコーレムの協力で一階述語論理の完全性が証明され、われわれが「ゲーデルの完全性定理」と呼んでいるものは「エルブラン・スコーレムの完全性定理」と呼ばれたかもしれません。これも、歴史の皮肉の一つなんでしょう。