2002年10月 1日 作成 ゲーデル の完全性定理 >> 目次 (テーマ ごと)
2007年11月16日 補遺  


 
 今回は、ゲーデル の完全性定理を扱う。

1. 恒真、恒偽および充足的

 完全性定理を扱う前に、まず、以下の 3つの概念を把握しておいてほしい。

  (1) 恒真
  (2) 充足的
  (3) 恒偽

 恒真というのは、任意の (all という意味) 変域の任意の (all という意味) 値について真であることをいう。
 充足的というのは、或る変域の或る値について (適当な代入値をとれば) 真と成り得ることをいう。
 恒偽というのは、「非充足的」 のことをいい、どんな変域のどんな値についても偽であることをいう。

 
2. 完全性定理

 完全性定理の正式な名称は「論理学における述語計算の公理の完全性」 である。
 ここでいう述語論理とは、現代の用語で言えば、「狭義の述語論理 (第一階述語論理)」 のことである。

 完全性定理とは、「述語論理の トートロジー (恒真命題式) は、述語論理の体系の中で証明可能である」 ということを示している。つまり、「恒真 = 証明可能」 ということである (意味論的な恒真性と形式的な証明可能性は同値である)。
 逆に言えば、論理 (公理系と推論) を使って証明できる論理式は恒真である。

 
3. 一般完全性定理

 完全性定理は、一般完全性定理として、「公理系 T (述語論理) が無矛盾なら、T の加算 モデル が存在し、モデル が存在すれば、その形式的体系は無矛盾である」 ということを主張できる。
 したがって、一般完全性定理は、「強完全性定理」 とか 「モデル の存在定理」 とも呼ばれている。

 単純に言えば、形式的体系 T において、T の モデル が存在するということは、T が無矛盾である、ということと同値である。(ちなみに、この 「モデル の存在性」 が、後々、不完全性定理に使われることになる。)

 
4. モデル の存在性

 完全性を証明するには、無矛盾ならば モデル が存在することを示せばよい。
 証明の詳細な手順は、拙著 「論理データベース論考」 131ページ を参照されたい。 □

 



[ 補遺 ] (2007年11月16日)

 ゲーデル 氏の有名な仕事として、「第 1階述語論理の完全性」 「算術の不完全性」 「連続体仮説の無矛盾性」 を証明したこと、さらに、アインシュタイン の一般相対性理論の 「特殊解」 をみつけたことを列挙できるでしょう。「第 1階述語論理の完全性」 が、ふつう、「完全性定理」 とよばれ、「算術の不完全性」 が、ふつう、「不完全性定理」 とよばれています。「完全性」 とか 「不完全性」 という ことば は、数学的意味と日用の語法では違いがあるので、まず、数学的な意味を理解しなければならないでしょうね。特に、「不完全性」 という ことば は、日用語法では、「欠陥がある」 点を想像しがちなので。

 まず、以下の用語を理解して下さい。

 (1) 無矛盾
 (2) 完全性

 「矛盾」 というのは、「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) 恒真
  (2) 充足的
  (3) 恒偽

 「恒真」 というのは、任意の (all という意味) 変域の任意の (all という意味) 値について真であることを云います。「命題論理」 では、「恒真」 のことを 「トートロジー (同語反復)」 と云います。恒真命題の例としては、「A ∨ ¬A」 とか。「トートロジー」 という言いかたは、ウィトゲンシュタイン が導入した概念です。「充足的」 というのは、或る変域の或る値について (適当な代入値をとれば) 真と成り得ることを云います。「命題論理」 では、事態が 「充足」 しているかどうか--事態の成立・不成立--は 「真理値表」 を使って判断されます。すなわち、真・偽を判断する 「一般手続き」 が、「命題論理」 にはあるのですが、いっぽうで、対象が 「無限」 になったとき--すなわち、「∀」 という量化が適用されたとき--や、∃x としても、対象の数が非常に多いときには、「真理値表」 を使って真・偽を験証することができないでしょうね。そういう状態のときには、「恒真性の テスト」 は、「証明」 を使わなければならないでしょう。となれば、「第 1階の述語論理」 が--言い換えれば、「述語論理」 の公理系が--、恒真命題 (トートロジー) を証明できるかどうかという 「完全性」 が争点になります。その争点に対して、肯定的な答えを与えたのが、ゲーデル の 「完全性定理」 です。すなわち、「(『第 1階の述語論理』 において、) 恒真命題は、すべて、証明可能である」 と。

 ただし、ゲーデル 氏が証明したのは、「対偶」 を使って--すなわち、「p → q」 なら、「¬q → ¬p」 が同値であることを使って--、「証明可能でない命題には、反例の モデル が存在する」 という点でした。ゲーデル 氏の証明では、「ケーニヒ の補題」 が流用されています。ただ、ゲーデル 氏の証明法は、反例の構成を見通すのが難しいので、のちに、ヘンキン 氏が一般形として具体的に モデル を構成しました (1949年)。拙著 「論理 データベース 論考」 131ページ で まとめた 「完全性定理」 は、「一般完全性定理」 (モデル の存在定理) を使った証明法です。

 「意味論」 の領域では、ゲーデル、タルスキー、カルナップ、モンタギュー、デヴィドソン、カプラン、クリプキに至る系統が重視されていますので、われわれ システム・エンジニア が、もし、モデル を本格的に学習するならば、かれらの説を学習しなければならないのですが、いっぽうで、数学上、「モデル 論」 として、レーヴェンハイム と スコーレム は 「原点」 でしょうから、レーヴェンハイム と スコーレム も学習して下さい。

 ちなみに、ゲーデル の 「完全性定理」 は、「意味論的な 『真』 が、構文論的な 『証明可能性』 と同値である」 ことを示しました。そして、ゲーデル 氏・タルスキー 氏と交友関係のあった カルナップ 氏が 「『(事実的な) F-真」 概念と 『(導出的な) L-真』 概念」 を提示しました。  




  << もどる ベーシックス すすむ >>
  数学基礎論