2002年10月 1日 作成 | ゲーデル の完全性定理 | >> 目次 (テーマ ごと) |
2007年11月16日 補遺 |
1. 恒真、恒偽および充足的 完全性定理を扱う前に、まず、以下の 3つの概念を把握しておいてほしい。
(1) 恒真
恒真というのは、任意の (all という意味) 変域の任意の (all という意味) 値について真であることをいう。
完全性定理の正式な名称は「論理学における述語計算の公理の完全性」 である。
完全性定理とは、「述語論理の トートロジー (恒真命題式) は、述語論理の体系の中で証明可能である」 ということを示している。つまり、「恒真 = 証明可能」 ということである (意味論的な恒真性と形式的な証明可能性は同値である)。
完全性定理は、一般完全性定理として、「公理系 T (述語論理) が無矛盾なら、T の加算 モデル が存在し、モデル が存在すれば、その形式的体系は無矛盾である」 ということを主張できる。 単純に言えば、形式的体系 T において、T の モデル が存在するということは、T が無矛盾である、ということと同値である。(ちなみに、この 「モデル の存在性」 が、後々、不完全性定理に使われることになる。)
完全性を証明するには、無矛盾ならば モデル が存在することを示せばよい。 |
[ 補遺 ] (2007年11月16日)
ゲーデル 氏の有名な仕事として、「第 1階述語論理の完全性」 「算術の不完全性」 「連続体仮説の無矛盾性」 を証明したこと、さらに、アインシュタイン の一般相対性理論の 「特殊解」 をみつけたことを列挙できるでしょう。「第 1階述語論理の完全性」 が、ふつう、「完全性定理」 とよばれ、「算術の不完全性」 が、ふつう、「不完全性定理」 とよばれています。「完全性」 とか 「不完全性」 という ことば は、数学的意味と日用の語法では違いがあるので、まず、数学的な意味を理解しなければならないでしょうね。特に、「不完全性」 という ことば は、日用語法では、「欠陥がある」 点を想像しがちなので。 まず、以下の用語を理解して下さい。
(1) 無矛盾 「矛盾」 というのは、「A ∧ ¬A」 (「A であり、かつ、A でない」) が起こる事態です。すなわち、ひとつの命題 (A) と その命題の否定 (非 A) が、同時に成立することを云います。したがって、「無矛盾」 とは、その反対概念で、「A ∨ ¬A」 (「A であるか、あるいは、A でない」) ことを云います。「A は、A である」 という形式を、証明の途中で、「A は、非A である」 という意味に変えてしまうと、正しい判断ができない。したがって、ひとつの概念は、思考過程において、同一の意味をもち続けなければならない、という思考法則 (同一律、自同律) を形式的要件としたのが 「無矛盾性」 です。 「完全性」 とは、ひとつの命題のなかで、A あるいは ¬A のいずれかを証明できる (判断できる) ことを云います。逆に言えば、A とも ¬A とも判断できない事態を 「不完全性」 と云います。 さて、ゲーデル の 「完全性定理」 は、「第 1階の述語論理」 では、「トートロジー (恒真命題) が証明可能である」 ことを証明した定理です。ここで、「第 1階の述語論理」 とは、量化記号 (∀ と ∃) が個体を束縛する ロジック を云います--たとえば、∀x P (x) とか、∃x P (x)。「第 1階の述語論理」 は、ふつう、単に、「述語論理」 とよばれています。いっぽう、述語に対して量化を適用した論理を 「第 2階の述語論理」 と云います--たとえば、∃P ∀x P (x) など。 本 エッセー の最初に述べましたが、完全性定理を扱う前に、まず、以下の 3つの概念を把握してください。
(1) 恒真 「恒真」 というのは、任意の (all という意味) 変域の任意の (all という意味) 値について真であることを云います。「命題論理」 では、「恒真」 のことを 「トートロジー (同語反復)」 と云います。恒真命題の例としては、「A ∨ ¬A」 とか。「トートロジー」 という言いかたは、ウィトゲンシュタイン が導入した概念です。「充足的」 というのは、或る変域の或る値について (適当な代入値をとれば) 真と成り得ることを云います。「命題論理」 では、事態が 「充足」 しているかどうか--事態の成立・不成立--は 「真理値表」 を使って判断されます。すなわち、真・偽を判断する 「一般手続き」 が、「命題論理」 にはあるのですが、いっぽうで、対象が 「無限」 になったとき--すなわち、「∀」 という量化が適用されたとき--や、∃x としても、対象の数が非常に多いときには、「真理値表」 を使って真・偽を験証することができないでしょうね。そういう状態のときには、「恒真性の テスト」 は、「証明」 を使わなければならないでしょう。となれば、「第 1階の述語論理」 が--言い換えれば、「述語論理」 の公理系が--、恒真命題 (トートロジー) を証明できるかどうかという 「完全性」 が争点になります。その争点に対して、肯定的な答えを与えたのが、ゲーデル の 「完全性定理」 です。すなわち、「(『第 1階の述語論理』 において、) 恒真命題は、すべて、証明可能である」 と。 ただし、ゲーデル 氏が証明したのは、「対偶」 を使って--すなわち、「p → q」 なら、「¬q → ¬p」 が同値であることを使って--、「証明可能でない命題には、反例の モデル が存在する」 という点でした。ゲーデル 氏の証明では、「ケーニヒ の補題」 が流用されています。ただ、ゲーデル 氏の証明法は、反例の構成を見通すのが難しいので、のちに、ヘンキン 氏が一般形として具体的に モデル を構成しました (1949年)。拙著 「論理 データベース 論考」 131ページ で まとめた 「完全性定理」 は、「一般完全性定理」 (モデル の存在定理) を使った証明法です。 「意味論」 の領域では、ゲーデル、タルスキー、カルナップ、モンタギュー、デヴィドソン、カプラン、クリプキに至る系統が重視されていますので、われわれ システム・エンジニア が、もし、モデル を本格的に学習するならば、かれらの説を学習しなければならないのですが、いっぽうで、数学上、「モデル 論」 として、レーヴェンハイム と スコーレム は 「原点」 でしょうから、レーヴェンハイム と スコーレム も学習して下さい。 ちなみに、ゲーデル の 「完全性定理」 は、「意味論的な 『真』 が、構文論的な 『証明可能性』 と同値である」 ことを示しました。そして、ゲーデル 氏・タルスキー 氏と交友関係のあった カルナップ 氏が 「『(事実的な) F-真」 概念と 『(導出的な) L-真』 概念」 を提示しました。 |
<< もどる | ベーシックス | すすむ >> | |
数学基礎論 |