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


 
 今回は、ゲーデル の不完全性定理を概説する。

 
1. ω-完全と ω-無矛盾

 形式的言語 L のなかで自然数 n を考え、Sn0は、記号 0 の前に S を n 個、置いた記述である、とする。

(1) ω-完全

 「ω-完全」 とは、L の式 A (x) があれば、タイプ N において、以下が成立することをいう。

      任意の自然数 n について、A (Sn0) は、N において トートロジー ならば、
      ∀x ∈ N A (x) は、N において トートロジー である。

(2) ω-無矛盾

 「ω-無矛盾」 とは、形式的言語 L の式 A (x) において、以下が成立することをいう。

      任意の自然数 n について、A (Sn0) は、N において証明可能ならば、
      ¬∀y ∈ N A (y) は、N において証明可能ではない。

 
2. 不完全性定理

 不完全性定理 (1931年) の正式名称は、「『プリンシピア・マセマティカ』 や、その関連体系の形式的に決定不可能な命題について」 という。不完全性定理は、以下のように 2つの 「解釈 (意味論および構文論)」 が成立する。

(1) 意味論

 形式的言語 L が無矛盾であれば、L のなかの式について、どのような ω-完全な モデル においても真であるのに、L のなかでは証明できない式がある。

(2) 構文論

 L が ω-無矛盾であれば、L のなかの式 G について、G も ¬G も L のなかでは証明できない。

 
3. 決定不能

 G も ¬G も証明できないなら、L において 「決定不能」 である、という。

 
4. 不完全性定理の証明概観

 以下に記述する手順は、ゲーデル の論文のなかで、論文の最初に記述されている 「証明の概観」 を、若干、変更している。なお、ゲーデル の原文は、以下の文献を参照した。
 Kurt Godel, "Some metamathematical results on completeness and consistency, On formally undecidable propositions of Principia mathematica and related system I, and On completeness and consistency (1930b, 1931 and 1931a)", edited by Jean van Heijenoort, UMI, 1970.

(1) 形式的体系は原始記号の有限列である。証明も、形式的な見かたをすれば、論理式の有限列である。

(2) 原始記号に対して自然数を対応する。
  ゲーデル の論文では、体系 P (PM の公理系に対して ペアノ の公理系を付加して得られる公理系) の原始記号に対して、自然数 13 よりも小さな素数 (1, 3, 5, 7, 9, 11, 13) を 1対1 に対応させて、タイプ N の変数として、pn(p は 13 よりも大きな素数) という自然数を対応させている。
  このように、素数を使って割り当てられた数を ゲーデル 数という。
  (以後、ゲーデル 数を自然数として記述する。)

(3) 論理式は自然数の有限列になる。証明は 「『自然数の有限列』 の有限列」 になる。

(4) PM のなかに、1つの自由変数 v をもつ論理式 F (v) を作る。
  F (v) は「v は証明可能な論理式である」 ことを意味する。

(5) PM のなかに、A も ¬A も証明できない命題 A を作る。
  (5)-1 単項述語記号を導入する。
   単項述語記号とは、変数が自然数の タイプ であるような 1つの自由変数をもつ論理式のことをいう。
  (5)-2 単項述語記号を、すべて、一列に並べる。n 番目を R (n) とする。

(6) a を任意の単項述語記号とする。

(7) [ a; n ] を考える。
  つまり、単項述語記号 a の自由変数を ゲーデル 数で置換した論理式である。

(8) 自然数の集合 K を定義する。
  (8)-1 n ∈ K ⇒ ¬Bew [ R (n); n ].
  (8)-2 ¬Bew [ R (n); n ] ⇒ n ∈ K.
 ( Bew (x) は、「x は証明可能な論理式である」 ことを意味する。)

(9) K も PM のなかに作ることができる。

(10) 論理式 [ S; n ] を考える。
  すなわち、自然数 n が K に属しているような単項述語記号 S が存在する。
  S は単項述語記号であるから、どれかの R (q) と同じである [ S = R (q) ]。

 さて、以上の前提を整えたならば--以上の 「着想」 は、到底、われわれ凡人には思い浮かぶことができないし、ゲーデル が、以上の 「着想」 を整えることができたから、天才といわれる所以である(!)--、証明自体は、以下のように単純明快である。

(11) [ R (q); q ] が証明可能なら 「真」 となる。
  しかし、q は K に属していて、¬Bew [ R (q); q ] が成立することになって、証明不能となる (前提に反する)。

(12) ¬[ R (q); q ] が証明可能なら-- 「¬(q ∈ K) 」 となるから--、Bew[ R (q); q ] が成立する (前提に反する)。

 したがって、[ R (q); q ] は PM において決定不能である。

 
5. 不完全定理の他の証明法 (ゲーデル 以後)

 ゲーデル の不完全性定理が公にされたのは 1931年である。
 70年ほど前の証明であるから、ゲーデル が証明した以後、ほかの証明法も提示されている (そして、以後のやりかたは、当然、エレガント な証明になっている。)

 小生 (佐藤正美) は数学の門外漢なので、ゲーデル 以後の証明を、すべて、知っている訳ではない。
 小生は、たまたま、他の証明法として知り得たやりかたとして、「タルスキー の定理」 が好きである。
 タルスキー の定理:

       代入関数をもつ整合的な理論では、真理関数は存在しない。

 さて、タルスキー の証明については、「読書案内」 のなかで紹介した文献を読んでください。

 小生は、ゲーデル の (不完全性定理の) 論文を読み返すたびに、天才の 「着想」 に対して敬意を抱き、ただただ、(天才の ゲーデル に対する) 驚嘆と (振り返って、凡夫の我が身に対する) 溜息が出るばかりである、、、。□

 



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

 (以下の文は、本 ホームページ 「『論理 データベース 論考』 を読む」 の 「文献編第 14章 『ゲーデル を読むために』」 で綴った文のなかから転載しました。)

 ゲーデル 氏は、いわゆる 「不完全性定理」 として、「適当な条件の下で構成された--言い換えれば、算術化された--無矛盾な形式的体系には、かならず、その体系のなかで、『決定不能な』 命題が存在する」 ことを証明しました。つまり、真とも偽とも証明されないような命題が存在するのです。

 タルスキー 氏は、「『真理』 は、ひとつの言語体系のなかで定義できないので、ほかの言語として--『対象言語』 に対する言語として、クラス 算のような--『メタ 言語』 を導入する」 ことを示しました。ラッセル 氏流の タイプ理論で云うなら、タイプ n の充足関係は、タイプ 「n − 1」 が対象になるということです。

 ゲーデル 氏は、「不完全性定理」 を証明する前に、「完全性定理」 を証明しています。「完全性定理」 は、「無矛盾な第一階理論は モデル をもつ」 という証明です。「モデル が存在する」 ということは、「証明可能性」 のことです。そして、ゲーデル 氏は、(「完全性定理」 で導入した) 「証明可能性」 を使って、「不完全性定理」 を証明しました。すなわち、純粋に数学的な接近法を使ったのですが、前述した (タルスキー 氏の) 「定義不可能性」--「証明可能性」 とは逆の着想になるのでしょうが--を使って、「不完全性定理 = 定義不可能性 + 算術化された完全性定理」 として証明することもできるそうです。通俗的に言えば、「不完全性定理 = パラドックス + 算術化された完全性定理」 ということです。ウィトゲンシュタイン 氏は、ゲーデル 氏の 「不完全性定理」 に関して、この意味論的な着想に気づいていたようです。ウィトゲンシュタイン 氏は、「不完全性定理」 を 「無意味」 としています。ゲーデル 氏は、(「不完全性定理」 に対する ウィトゲンシュタイン 氏の 意見に関してして、) 以下のように言っています。

    かれ (ウィトゲンシュタイン) は、この定理を一種の論理的 パラドックス と解釈していますが、
    この定理は、数学の中でも最も議論の生じる余地のない領域 (有限数論) における数学的
    定理です。

 ウィトゲンシュタイン 氏の使った 「無意味」 という用語が、原語では、どういう語であるかを調べなければならないのですが--「無意味」 という意味が、「現実的事態と対応する語-言語ではない」 という意味なのかどうかを調べなければならないのですが (ただし、私は調べていない)--、かれの著作 「数学の基礎」 には、以下の文が綴られています。

    いかに奇妙に思われようとも、ゲーデル の不完全性定理に関する私の課題は、ただ単に、
    「これは証明可能である、と仮定せよ」 といった命題は数学においては何を意味するのか、
    ということを明確にすることであるように見える。

 ウィトゲンシュタイン 氏は、「言語 ゲーム」 のなかで、証明に関して、以下の考えかたをもっていました。

  (1) 物理的対応と数学的対応との違いは、実験と計算の違いと同型である。
  (2) 証明は、実験した結果としての命題を持つわけではなくて文法規則を持つ。
  (3) 証明は、対象についての高次の実験である、という考えかたは間違いである。

 ウィトゲンシュタイン 氏は、あきらかに、「不完全性定理」 を 「言語 ゲーム」 のなかで見極めようとしていますね。

 さて、本 エッセー のなかで記載した書物を読んで、ゲーデル 氏の 「完全性定理」 「不完全性定理」 を、もっと、学習したいと思ったならば、以下の書物を読んで下さい。

  ● 「ゲーデル と 20世紀の論理学 (1 〜 4)」、田中一之 編、東京大学出版会。

 2006年・2007年に出版された 4分冊です。私は、(1) から (3) を読みましたが、まだ、(4) を購入していない。




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