ゲーデルの不完全性定理

提供: miniwiki
移動先:案内、検索
50x40px
 この記事は語句の内部リンク、見出しのマークアップなどスタイルマニュアルに沿った修正が必要です。ウィキペディアの体裁への修正にご協力ください（ヘルプ）。（2018年7月）

ゲーデルの不完全性定理（ゲーデルのふかんぜんせいていり、独: Gödelscher Unvollständigkeitssatz）又は単に不完全性定理とは、数学基礎論における重要な定理で、クルト・ゲーデルが1930年に証明した[1]ものである。

概要

第1不完全性定理 
自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。
第2不完全性定理 
自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない[2]。

ゲーデルの定理でいう証明不能命題[math]G[/math]は、「[math]G[/math]は証明できない」という命題と同値である。[math]G[/math]はゲーデル文と呼ばれる。

[math]G[/math]が証明可能であれば、[math]\Sigma_1[/math]完全性により命題「[math]G[/math]は証明できる」もまた証明可能である。一方[math]G[/math]は命題「[math]G[/math]は証明できない」と同値であることが証明可能であるので、両者から矛盾が導かれる。

つまり

「[math]G[/math]は証明できる」ならば「矛盾が証明できる」…(A)

したがって、対偶を取れば

「矛盾が証明できない」ならば「[math]G[/math]は証明できない」…(B)

となる。 また、[math]\lnot G[/math]が証明可能であれば、[math]G[/math]の性質から命題

「[math]G[/math]は証明できる」

も証明可能である。この際、もし[math]G[/math]そのものが証明不能だとすると、ω矛盾ということになる。ω無矛盾であれば[math]G[/math]も証明可能である。しかし[math]G[/math]が証明可能であれば

「[math]G[/math]は証明できない」

も証明可能であるので、やはり両者から矛盾が導かれる。したがってω無矛盾であれば[math]\lnot G[/math]も証明できないのである。よってω無矛盾であれば、[math]G[/math]も[math]\lnot G[/math]も証明できない（第一不完全性定理）。

なお、証明可能性の代わりに真理性を用いるならば、パラドックスが導かれる。このことから、自然数論における真理性は自然数論の中では表現できないことが示される（タルスキの定理）。

ゲーデル文を構成するためには自然数論の式を自然数に変換するゲーデル数および自己言及で用いられる対角化の技法（を形式化したもの）が必要である。後者は対角化補題と呼ばれる。

自然数を変数とする述語

「[math]x[/math]は…である」

の対角化は、左記の述語の[math]x[/math]に

「[math]x[/math]は…である」

のゲーデル数を代入した命題である。その意味は

「[math]x[/math]は…である」は…である」

となる。 ゲーデル文[math]G[/math]は

「「[math]x[/math]で表される述語の対角化は証明できない」

で表される述語の対角化は証明できない」と表される。

「[math]x[/math]で表される述語の対角化は証明できない」

の対角化は、[math]G[/math]自身と同値になる。 さて、自然数論の無矛盾性とは、

「自然数論において矛盾を証明できない」

ということである。そして、自然数論による自然数論の無矛盾性証明とは、「」内が、自然数論で証明できるということである。

「自然数論で矛盾が証明できない」

と自然数論で証明できれば、第一不完全定理での議論中の(B)より

「[math]G[/math]は証明できない」

と証明できる。 しかし、

「[math]G[/math]は証明できない」

とは[math]G[/math]と同値であるから、[math]G[/math]も証明されることとなり、そこから第一不完全定理での議論中の（A)により、矛盾が証明される。

したがって自然数論が無矛盾、すなわち自然数論で矛盾が証明されないならば、そのこと自体も自然数論では証明できない（第二不完全性定理）。

詳細

ゲーデルの定理は

「自然数論を含む帰納的公理化可能な無矛盾理論」

に対して示されているが、ここでは簡単の為、自然数論のみを扱う。一般の場合も同様。

ゲーデル文の構成

概要でも説明したように、ゲーデル数というテクニックを使って間接的に自己言及を可能とし、ゲーデル文を構成する。

コンピュータでは全てのデータを一意な数値で表しており、特に文字列や論理式そして論理式の列も数値で表す。このように、論理式を数値で表す行為を論理式のゲーデル数化といい、命題[math]P[/math]に対応する数値を[math]P[/math]のゲーデル数という[注釈 1]。

ゲーデル数化により、論理式に関する様々な性質を論理式として表すことができる。たとえば、

  • [math]Axiom(x)[/math]： [math]x[/math]は公理のゲーデル数である。
  • [math]MP(x,y,z)[/math]： [math]x[/math]をゲーデル数に持つ論理式と[math]y[/math]をゲーデル数に持つ論理式から三段論法により[math]z[/math]をゲーデル数に持つ論理式が導ける。

といった論理式を作ることができる。ここで、[math]Axiom[/math]や[math]MP[/math]の引数が論理式自身ではなく自然数であることが重要である。前述のように自然数論は

「命題に言及する命題」

を取り扱うことはできないが、

「命題のゲーデル数に言及する命題」

なら取り扱うことができるのである。

[math]Axiom(x)[/math]や[math]MP(x,y,z)[/math]などを組み合わせれば、

  • [math]Proof(y,z)[/math] : [math]z[/math]をゲーデル数に持つ論理式を[math]P[/math]とするとき、[math]y[/math]をゲーデル数に持つ論理式の列が論理式[math]P[/math]の証明になっている。

という論理式も作ることができる。

さらに[math]Proof[/math]を「[math]\exists[/math]」と組み合わせることで、

  • [math]Provable(z)[/math] : 「[math]\exists y : Proof(y,z)[/math]」である。すなわち、[math]z[/math]をゲーデル数に持つ論理式を[math]P[/math]とするとき論理式Pは証明可能である。
  • [math]ProvableARG(z,x)[/math] : 「[math]\exists y : Proof(y,z,x)[/math]」である。すなわち、[math]z[/math]をゲーデル数に持つ論理式を[math]Q[/math]とするとき、[math]Q[/math]中の変数に自然数[math]x[/math]を代入した論理式[math]Q(x)[/math]は証明可能である。

という論理式も作ることができる（上では[math]P[/math]は引数を持たず、[math]Q[/math]の引数は1つである）。

論理式[math]\lnot ProvableARG(x,x)[/math]のゲーデル数を[math]m[/math]とすると、[math]x[/math]に[math]m[/math]を代入した論理式[math]\lnot ProvableARG(m,m)[/math]がゲーデル文となる（対角化）。

第一不完全性定理の証明

ゲーデル文[math]\lnot ProvableARG(m,m)[/math]のゲーデル数を[math]npmm[/math]とする。

否定命題の証明不能性

否定命題[math]\lnot ProvableARG(m,m)[/math]が証明可能とすると、[math]Provable(npmm)[/math]は真である。このとき[math]\Sigma_1[/math]完全性より[math]Provable(npmm)[/math]は証明可能である。

一方[math]\lnot ProvableARG(m,m)[/math]は

「[math]m[/math]をゲーデル数に持つ論理式に[math]m[/math]を代入したものは証明不能」

という意味である。 [math]m[/math]をゲーデル数に持つ論理式に[math]m[/math]を代入したものは[math]npmm[/math]であるから

[math]\lnot ProvableARG(m,m) \Leftrightarrow \lnot Provable(npmm)[/math]

が証明可能である。したがって、

[math]\lnot Provable(npmm)[/math]

は証明可能である。

したがって[math]Provable(npmm)[/math]および[math]\lnot Provable(npmm)[/math]が証明され、これは矛盾である[注釈 2]が、これは自然数論が無矛盾であるという仮定に反する。

肯定命題の証明不能性

肯定命題[math]ProvableARG(m,m)[/math]が証明可能だとすると、

[math]ProvableARG(m,m) \Leftrightarrow Provable(npmm)[/math]

により

[math]Provable(npmm)[/math]

が証明可能である。

このときω無矛盾性を前提すると、[math]npmm[/math]をゲーデル数とする論理式[math]\lnot ProvableARG(m,m)[/math]が証明可能である。[注釈 3]

それ故、矛盾が証明されるが、これは自然数論が無矛盾であるという仮定に反する。

第二不完全性定理の証明

矛盾を「[math]\bot[/math]」で表し、「[math]\bot[/math]」のゲーデル数を[math]b[/math]とする。すると、「自然数論の体系内で自然数論の無矛盾性を証明できる」という言説を

自然数論の体系内で「[math]\lnot Provable(b)[/math]」を証明できる

の意味に解することができる。

まず

[math]\lnot Provable(b)[/math]

が自然数論の体系内で証明可能であると仮定する。 第一不完全性定理のところで示したように、[math]\lnot ProvableARG(m,m)[/math]が証明できれば矛盾が証明できる。この議論を自然数論の体系内で行うことで、

[math]Provable(npmm) \Rightarrow Provable(b)[/math]

が自然数論の体系内で証明可能なことがわかる。故に対偶を取ることで

[math]\lnot Provable(b) \Rightarrow \lnot Provable(npmm)[/math]

が自然数論の体系内で証明可能なことがわかる。したがって、仮定および[math]\lnot ProvableARG(m,m) \Leftrightarrow \lnot Provable(npmm)[/math]から

[math]\lnot ProvableARG(m,m)[/math]

が自然数論の体系内で証明可能なことがわかる。第一不完全性定理の所で示したように、[math]\lnot ProvableARG(m,m)[/math]が証明可能だと、矛盾が証明される。したがって矛盾が証明されないならば、[math]\lnot Provable(b)[/math]は証明されない。

決定不能命題の例

数学と計算機科学（コンピュータ科学）において、「決定不能」という言葉には二つの異なった意味がある。一つ目は証明論の文脈でゲーデルの定理に関連して使われる意味であり、特定の形式的体系の下で或る命題を証明も否定の証明もできないことを言う。二つ目は（本項では詳述しないが）計算可能性理論に関連した用法であり、命題ではなく決定問題に適用される。決定問題とは入力に対して答が真か偽のいずれかになるような問題である。ある問題を全ての入力に対して正しく解答するような計算可能関数が存在しないとき、そうした問題は決定不能であると言う。

このように決定不能という言葉には二つの意味があるので、代わりに独立（English版）という用語をもって「証明も否定の証明もできない」という意味にあてる場合がある。ところが「独立」という用語にしても依然曖昧な部分がある。単に「証明できない」という意味を表し、「否定の証明もできない」かどうかについてはあえて含意していない場合があるからである。

以下、本節では一つ目の意味で「決定不能」と書く。特定の形式的体系の下である命題が決定不能であることは、その命題の真理値がwell-definedであるかどうかや他の手段で決定可能かどうかについては明らかにしない。決定不能ということが意味するのは、あくまで使用されている特定の形式的体系の下ではその命題の真偽をいずれも証明できないということにすぎない。真理値を決して知ることができないか、または真理値の定義自体が無効となるような、いわゆる「絶対的決定不能」命題が存在するのかどうかは数理哲学における論争の的となっている。

ゲーデルとポール・コーエンの仕事を合わせて、決定不能命題の確かな実例が得られた。連続体仮説はZFC（集合論における標準的な公理系）の下では証明も否定の証明もできない。また、選択公理もZF（ZFCに含まれる公理から選択公理を除いたもの）では証明も否定の証明もできない。これらの結果は不完全性定理を必要としない。1940年、ゲーデルはこれらの命題が何れも ZF または ZFC 集合論では否定を証明できないことを証明した。1960年代、コーエンはこれらがいずれも ZF から証明できず、また連続体仮説が ZFC から証明できないことを証明した。

マチャセビッチによるヒルベルトの第10問題によって決定不能な命題の例が得られる。そのような例はディオファントス方程式の外側に存在量化子を幾つか並べた形として得られる。すなわち不完全性定理の前提条件を満たす形式的体系において、解の存在が証明も反証もできないようなディオファントス方程式が存在する。

1973年、群論におけるホワイトヘッドの問題（English版）が標準的な集合論では決定不能であることが示された。

1977年、パリスとハーリントンは、ラムゼーの定理の一種であるパリス・ハーリントンの定理（English版）が、一階算術の公理体系であるペアノ算術の下では決定不能だが、より大きな二階算術の体系では真であることを証明できることを証明した。カービーとパリスは後にグッドスタインの定理（自然数の数列に関する命題であり、パリス・ハーリントンの原理よりもいくらか易しい）がペアノ算術では決定不能であることを示した。

計算機科学で応用される Kruskal の木定理（English版）はペアノ算術では決定不能だが集合論では証明できる。実際、Kruskalの木定理（またはその有限版）は、可述主義（English版）[注釈 4]と呼ばれる数学的哲学に基づいて構築されたもっと強い体系の下でも決定不能である。これに関連し、更に一般的な graph minors 定理（English版）（2003年）は計算複雑性理論に影響する。

グレゴリー・チャイティンはアルゴリズム情報理論における決定不能命題を発見し、その状況下で新たな不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能ないかなる理論においても、どのような数であっても [math]c[/math] よりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 [math]c[/math] が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。

ゲーデルの定理に関する制限

第1不完全性定理はロビンソン算術を含んでいれば十分である。またω無矛盾性の仮定は単なる無矛盾性の仮定に弱められる（後述）。第2不完全性定理はロビンソン算術にΣ1論理式に対する数学的帰納法の公理図式を追加した体系（[math]I\Sigma_1[/math]）を含んでいれば十分である。ペアノ算術はこれを含むから、ペアノ算術を含む理論は第2不完全性定理の適用範囲である。

ゲーデルの定理は無矛盾な理論についてのみ適用できる。一階論理では、ex falso quodlibet (en) により、矛盾した理論 [math]T[/math] はその言語上の如何なる式であれ証明できてしまい、その中には「[math]T[/math] は無矛盾である」と主張する式も含まれる。

ゲーデルの定理が成り立つのは、あくまで定理が必要としている仮定を満足するような形式的体系に限られる。全ての公理系がこれらの仮定を満たす訳ではなく、中には自然数論の標準モデルを部分構造として持つようなモデルを持っていてもなお仮定を満たさないような公理系もある。例えば、ユークリッド幾何学の一階公理化理論、実閉体の理論、乗算が全域で可能なことを証明できないような算術理論、これらは何れもゲーデルの定理に必要な仮定を満たさない。要点は、これらの公理系では自然数の集合を定義することや自然数の基本的な性質を証明することができないことにある。三つ目の例に関して Dan E. Willard は第二不完全性定理に必要な仮定を満たさないような様々な弱い算術理論を調べた（例えば Willard 2001）。

ゲーデルの定理は実効的に生成された（即ち帰納的可算な）理論についてのみ適用できる。自然数に関する真である文を全て公理とするような理論を考えれば、この理論は無矛盾かつ完全であり、かつペアノ算術を含んでいる。これはゲーデルの定理と矛盾しない。何故ならこの理論は帰納的可算ではないからである[注釈 5]。

第二不完全性定理が示すのは、ある公理系の無矛盾性はその公理系自身では証明できないということであって、他の無矛盾な公理系からも証明できないとは言っていない。例えば、ペアノ算術の無矛盾性はZFCから証明できるし、算術の理論にε0までの超限帰納法を加えて得られたゲンツェンによる無矛盾性の証明（English版）もある。

不完全性定理の成立しない体系

不完全性定理は「『自然数論を含む帰納的公理化可能な理論が、無矛盾（ω無矛盾）であれば』～」という形の定理である。したがって、自然数論を含まない公理系や、帰納的公理化可能でない理論が完全であっても、不完全性定理とは矛盾しない。

真の算術やペアノ算術の無矛盾完全拡大などは無矛盾かつ完全であるが、帰納的公理化可能でない。とくに真の算術は算術的に定義不能である。この結果はタルスキの真理定義不可能性として知られる。

プレスバーガー算術は帰納的公理化可能、無矛盾かつ完全である。プレスバーガー算術は加法しか含まない公理系であり、ゲーデル数によるコード化のテクニックを扱えない。そのため、不完全性定理は適用できない。また、実閉体の理論やユークリッド幾何学も完全であり、（直観に反して）算術を含まないため、不完全性定理は適用できない。したがって実閉体の理論は決定可能である。もっと精密にいうと実閉体の理論では量化記号消去が可能である。この事実は数式処理系の実装などに応用されている。

なお、群や環の公理などは、「自然数論を含まない帰納的公理化可能かつ無矛盾な公理系」であり、不完全性定理は適用できないが、不完全である。例えば、可換群と非可換群がともに存在することから、健全性定理より、群の公理からは積の可換性は証明も反証もできない。

その影響・応用

"「数学基礎論」および「ゲーデル」"

ゲーデルの定理は、数学基礎論のうち、数学の無矛盾性の証明を目標としていたヒルベルト・プログラムには、深刻な影響を与えた。ヒルベルトは公理の適切な設定によって完全かつ無矛盾な体系を達成できると楽観視していたが、第二不完全性定理により、ヒルベルトの計画は頓挫した。

上記のような述語論理式を自然数論の体系内に構成し、証明を形式的に進めるために、ゲーデルはゲーデル数化という操作を導入した。自由変数、論理式、証明図などを自然数でコード化し証明可能、反証可能などの概念を数論的関数として表現する。このように、論理式や証明を数学的に表現して数学内に埋め込む上記の手法は、数学そのものを分析する「メタ数学」を、分析すべきの数学の中に写像する技法の先駆けであり、その後数学基礎論や理論計算機科学でよく用いられるようになる。

ゲーデル以後の展開

第一不完全性定理の拡張として、証明の定義に、命題の証明より小さな、否定命題の証明が存在しないという性質を追加した上で、前提のω無矛盾性を無矛盾性に弱めた定理がジョン・バークリー・ロッサー (1936年) によって示された。この事実はω矛盾した算術理論を考える場合などにおいて重要となる。なお算術を内包する真である体系（自然数の標準モデルで真である公理に基づく体系）はω無矛盾なので、第1不完全性定理は原型のままでも適用できる。今日ではこちらの無矛盾性のみを仮定する強い定理もゲーデルの不完全性定理と呼ばれるが、単にロッサーの定理、ゲーデル・ロッサーの定理などと呼ばれることもある。

第二不完全性定理に関しては、ゲーデルによる証明の定義に代えて、ロッサーによる上記の証明の定義を用いれば、体系自身の無矛盾性が証明できることが、クライゼル (1960) によって指摘されている。2つの証明の定義の同値性は体系内では証明できないため、第2不完全性定理とは矛盾しない。

レオン・ヘンキンは、対角化により「Hは証明できる」と同値となる命題H（ヘンキン文）を構成し、その証明可能性に関する問題を1952年に提起した。この問題は3年後の1955年に、マーティン・レーブによって解かれた。彼は、「Hの証明が存在すればHである」が証明可能であれば、Hもまた証明可能であることを示した（レーブの定理）。Hに矛盾を代入すれば、レーブの定理から第二不完全性定理が示せる。

不完全性定理の代数化

不完全性定理は他の論理構造と同じく抽象代数による簡易な表現が可能である。リンデンバウム代数（English版）を次のように定義する。

  • 理論 [math]T[/math] のリンデンバウム代数 [math]T_L[/math] は，文に順序構造を入れたものである。
  • 順序は、もし理論 [math]T[/math] で [math]A \Rightarrow B[/math] を証明できるならば [math]A \ge B[/math] と定義される。
  • [math]A[/math] と [math]B[/math] の順序が等しいなら、[math]A[/math] と [math]B[/math] を同一視する。

[math]T[/math] で無条件に証明可能な文 [math]A[/math] は，この順序で最小元となり、[math]T[/math] で [math]\lnot A[/math] を証明できるとき、[math]A[/math] はこの順序の最大元となる。よって最大元でも最小元でもないものは独立命題のみ。つまり不完全であるためにはリンデンバウム代数の位数は3以上であることが要請される。一方 [math]B[/math] を，一階述語論理のリンデンバウム代数とすると、どんな理論のリンデンバウム代数 [math]L[/math] についても，あるイデアル [math]I \subseteq B[/math] が存在して、[math]L=B/I[/math] と表される。よって [math]T[/math] が生成するイデアル [math](T)[/math] が [math]T[/math] が生み出す定理全体となる。このとき、理論 [math]T[/math] のリンデンバウム代数は、剰余代数 [math]B/(T)[/math] である。ここでロビンソン算術に対応する [math]B[/math] の部分集合を [math]Q[/math] とする。このとき、ゲーデルの第一不完全性定理は次のようにして表現される。

  • [math](Q)[/math] を含む再帰的可算素イデアル [math]p \subset B[/math] は存在しない。

他に、ザリスキ位相や素スペクトルによる表現が知られている。

誤解

計算機科学者（コンピュータ科学者）・電子工学者のトルケル・フランセーンによれば、不完全性定理のインパクトと重要性について、しばしば大げさな主張が繰り返されてきた[3]。たとえば

「数学の思考に変革をもたらした」「数学ばかりでなく、科学全体も一新した」

「数学だけではなく、哲学、言語学、計算機科学と宇宙論にまで革命を起こした」

という言があるが、これらは乱暴な誇張とされる[3]。不完全性定理が一番大きな衝撃を与えたと思われる数学においてさえ、「革命」らしきものは何も起きていない[3]。

この定理は、数理論理学（数学の比較的小さな領域）で常に使われているが、普通の数学者の仕事にはほとんど何の役にも立っていない[3]（そもそも計算機科学は、不完全性定理の証明後に、アラン・チューリング主導で成立した。不完全性定理が計算機科学に革命を発生させたと述べるのは、時系列が誤っている）[4]。

ゲーデルの完全性定理と不完全性定理は、革命的出来事ではなく時代の流れの産物だった[4]。ゲーデル以外の誰かがこれらの定理を発見するのは時間の問題だったとされており、ゲーデル自身もそう見ていた[4]。

誤用

フランセーンは『ゲーデルの定理：利用と誤用の不完全ガイド』において、ゲーデルの定理が広範に誤用されていることについて論じている[5]。

一般社会・インターネット

数学者の田中一之によれば、ゲーデルの名や定理は「知的会話」に頻出している[6]。フランセーンが述べたように、インターネットのどんなニュースグループでも、遅かれ早かれ誰かがゲーデルの定理を持ち出す[6]。そういった一般的な引用における間違いを正すことが、フランセーンの著書の目的となっている[6]。

1931年にゲーデルが示したのは、「特定の形式体系[math]P[/math]において決定不能な命題の存在」であり、一般的な意味での不完全性についての定理ではない[7]。

フランセーンによれば、ゲーデルの不完全性定理と結び付けられるテーマはロジック、数学、計算、哲学、物理学、進化論、政治、宗教、無神論、神学、文学、詩歌、写真、建築、音楽、ヒップホップ、デートなど多岐にわたる[8]。

形式論理学のような専門領域の外では、不完全性定理についての言及の多くは、誤解や自由連想に基いており、馬鹿げているとさえ言える[5]。たとえば、

ゲーデルの不完全性定理は、客観的現実の存在は証明できないことを示している
ゲーデルの不完全性定理によって、すべての情報は本質的に不完全で、自己言及的である
存在と意識を同等に考えることによって、私たちはゲーデルの不完全性定理を進化論に応用できる

などが見られる[5]。

アラン・ソーカルとジャン・ブリクモンは、ポストモダニズムに対する論評の中で、「ゲーデルの定理こそ汲めども尽きぬ知的濫用の泉である」と述べ、レジス・ドブレ、ミシェル・セールらの文章を批判している[5]。ゲーデルの理論の誤解は、さらに一般的な人々の間でも起こっている[5]。たとえば

ある種の事実は、論理や数学でうまく証明できない
何ものも確実に知り尽くすことはできない
人間の心は計算機（コンピュータ）ができないこともできる

などである[5]。

数学者以外の学者

田中によれば、ゲーデル自身が不完全性定理について明言しているのは、1963年8月28日の次の文言である[7]。

ある程度の有限的算術を含むどんな無矛盾な形式体系にも決定不能な算術命題が存在し、さらにそのような体系の無矛盾性はその体系においては証明できない。[7]

ゲーデルは慎重を重ねて言葉を選んでいるため、この表現を安易に変えようとすると、不具合を生じる[7]。実際、この定理のいずれかの条件が落とされることで、多数の誤解が生じている（特に「有限的算術を含む」という条件が落とされていることが多い）[7]。

「ある程度の有限的算術を含む」という条件を、「十分大きな」「十分複雑な」「十分表現力のある」などといった曖昧な条件に置き換えることは誤りだが、一般向けの解説などには横行している（実際には、大きな理論で完全なものもあれば、小さな理論で不完全なものもある）[7]。

さらに見落とされやすい点は、不完全性定理の前提および結論部に「算術の条件」があることである[9]。要するに不完全性定理は、「算術を含む体系がその算術部分で不完全である」という主張であり、その算術の外側が完全か不完全かについては、この定理は何も語っていない[10]。

高名な物理学者でさえ、間違いを冒すことがある[10]。フリーマン・ダイソンとスティーヴン・ホーキングの論説は、万物理論の可能性を否定するのにゲーデルの定理を持ち出した[10]。しかし仮に物理理論に不完全性定理が適用できたとしても、不完全性はその算術部分に見つかるだけで、その理論が完全か不完全かは別の問題である[10]。

また、哲学者によるゲーデル関係の本が、フランセーンの本と同じ頃に書店販売されていたが、哲学者の本は専門誌によって酷評された[11]。その本は全体として読みやすく一般読者からの評判は高かったが、ゲーデルの証明の核（不動点定理）について、根本的な勘違いをしたまま説明していた[11]。同様の間違いは他の入門書などにもあり、田中は「一般の哲学者は、論理の専門家ではない」と述べている[11]。

宗教

フランセーンによれば、次のような講釈さえ存在する[12]。

ゲーデルの不完全性定理は、数学的なアプローチや証明なしにも直観的に理解しうるものである。実際、禅仏教思想のなかにも明瞭にそれとわかる形で不完全性の概念が出現しているからだ。[12]

実際には不完全性定理は、「形式体系の無矛盾性と完全性についての定理」である[12]。確かに「矛盾」「無矛盾」「完全」「不完全」「体系（システム）」という語は、専門用語でない言語とも結びつきがあるが、およそこのような結びつきは不完全性定理と関係が無い[12]。

神学

神学にも不完全性定理は持ち込まれ濫用されており、たとえば『キリスト教と数学の書誌学』（1983年）がある[13]。

ゲーデルの不完全性定理は … 神の自由への道を示す。[13]
〔この論文では〕ゲーデルの定理を用いて、物理学者が物質的実在の最終的理論を決して定式化できないことを示す。 … 人間の心がたんなる論理機械以上のものであるという適切な見方を発展させる[13]
数学者も彼らのシステムで数学的真理のすべてを把握できないのだから、神学者が、すでに明らかになった真理をうまく体系化できなくても気に病むには及ばない。[13]
科学の方法、技法、仮定が、完全に科学に基礎づけられるはずはないことは、ゲーデルの定理からの類推によって説明される。それらの妥当性を判定するためには、科学の外のリソースを使わなくてはならない。[14]

ダニエル・グレーブスは次の通り「考察」をしている。[13]

ユダヤ・キリスト教は、真理はたんなる理性で推し量れる域を越えていると長い間考えてきた。霊的な真理は、霊魂によってのみ理解される、と私たちは教えられている。それも、そうあるべくしてそのようにある。ゲーデル流の構図は、キリスト教徒が宇宙について信じていることに適っている。[15]

ナジャムディン・モハメッドも、神学的に「応用」している[16]。

あなたが世界をどのように（論理的規則で）記述しても、あなたに真か偽か判定できない「何ものか」がつねにあるであろうことが指摘されている。 … これは、ゲーデルの不完全性定理の基本である。

もし私たちが論理や推論だけに頼るなら、互いに矛盾しているが論理的に自己無矛盾な推論・論理システムが多数生じ、完全な混乱状態で終わることもありうる。どっちが正しいか？　すべての事柄は、何がよいか悪いかのように現在の心理的な傾向に依存するものなのか？　こういう場合には「正しさ」は意味をもたず、まさにこのことが不可知論的無神論の立場を招きうるのだ。[16]

これらの考察と、「ポストモダン的状況」という考え方には類似性がある[17]。そうした理屈では、不完全性は無数の様々な無矛盾理論を導き、どこで「真理」が手に入るかは誰も知らない（したがって、理性だけで正しい道を歩むことはできず、信仰が進むべき道となる[18]）。

しかし実際の数学では、そのような枝分かれは無く、「決定不能性の海」の中でもがくようなことも無いため、そのような「混乱」は神学的幻想に過ぎないとされている[18]。

誤用の分類

田中はゲーデルの定理の様々な誤用を分類している[19]。その一つは、人間の悟性が陥りやすい間違った傾向である[19]。たとえば、自分が思いつく有意義そうな体系がどれも不完全であるので、「有意義な体系はすべて不完全である」と思い込み、さらにその原因を定理か何かに帰着させようとする傾向である[20]。

別の誤用は、言語の誤用である[19]。不完全性定理に含まれる「矛盾」「完全」「体系（システム）」などの語は、日常では多様に使われている[19]。そこを混同すれば、ゲーデルの定理までがインフォーマル（非公式・非正式）な意味と結び付けられる[19]。

脚注

注釈

  1. ↑ 歴史的には論理式のゲーデル数化の概念が先に生まれ、後にコンピュータがデータを数値で表すようになった。なお、ゲーデル自身は、素因数分解の一意性を利用して論理式のゲーデル数化を実現している。
  2. ↑ 実際、[math]\lnot ProvableARG(m,m)[/math]が証明可能なら[math]\not ProvableARG(m,m)[/math]の証明系列[math]P_1,\ldots,P_{n_0}[/math]が存在するので、論理式の列[math]P_1,\ldots,P_{n_0}[/math]のゲーデル数を[math]a[/math]とすると、「Proof[math](a,m,m)[/math]」が証明可能、したがって特に「[math]\exists y : Proof(y,m,m)[/math]」=「[math]ProvableARG(m,m)[/math]」が証明可能。一方我々は「[math]\lnot ProvableARG(x,x)[/math]」が証明可能な事を仮定していたので、これは矛盾である。
  3. ↑ ω無矛盾とは[math]\exists yP(y)[/math]が証明できれば、[math]P(u)[/math]を満たす自然数[math]u[/math]が実際に存在することを指す。定義より「[math]ProvableARG(m,m)[/math]」は「[math]\exists y : Proof(y,m,m)[/math]」であった。ω無矛盾性より、「[math]Proof(u,m,m)[/math]」を満たす自然数[math]u[/math]が実際に存在し、[math]u[/math]をゲーデル数に持つ論理式の列が[math]\not ProvableARG(m,m)[/math]の証明系列になる。
  4. ↑ 訳注：自己言及的でないこと。
  5. ↑ 訳注：この場合の「帰納的可算」とは、すべての定理のゲーデル数を枚挙する計算可能関数が存在する（実効的に枚挙可能）ことを意味する。クレイグのトリックによれば、このことは定理集合が帰納的な公理系から生成される（演繹閉包である）ことと同値である。

出典

  1. ↑ Gödels Unvollständigkeitssatz 2018年7月15日閲覧。
  2. ↑ webcache.googleusercontent.com 2018年7月15日閲覧。
  3. ↑ 3.0 3.1 3.2 3.3 フランセーン 2011, p. 9.
  4. ↑ 4.0 4.1 4.2 フランセーン 2011, p. 10.
  5. ↑ 5.0 5.1 5.2 5.3 5.4 5.5 フランセーン 2011, p. 4.
  6. ↑ 6.0 6.1 6.2 フランセーン 2011, p. 229.
  7. ↑ 7.0 7.1 7.2 7.3 7.4 7.5 フランセーン 2011, p. 230.
  8. ↑ フランセーン 2011, pp. 3-4.
  9. ↑ フランセーン 2011, pp. 230-231.
  10. ↑ 10.0 10.1 10.2 10.3 フランセーン 2011, p. 231.
  11. ↑ 11.0 11.1 11.2 フランセーン 2011, p. 233.
  12. ↑ 12.0 12.1 12.2 12.3 フランセーン 2011, p. 7.
  13. ↑ 13.0 13.1 13.2 13.3 13.4 フランセーン 2011, p. 126.
  14. ↑ フランセーン 2011, p. 127.
  15. ↑ フランセーン 2011, p. 128.
  16. ↑ 16.0 16.1 フランセーン 2011, p. 131.
  17. ↑ フランセーン 2011, pp. 131-132.
  18. ↑ 18.0 18.1 フランセーン 2011, p. 132.
  19. ↑ 19.0 19.1 19.2 19.3 19.4 フランセーン 2011, p. 234.
  20. ↑ フランセーン 2011, pp. 234-235.

関連文献

原論文
  • K. Gödel (1931), Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38: 173-98.
原論文の日本語訳
  • 林晋・八杉満利子訳・解説 (2006), ゲーデル 不完全性定理, 岩波書店, ISBN 4-00-339441-0
    （前半の58頁が原論文の邦訳、残りの233頁が歴史的な背景を中心とした解説、という構成）
  • 廣瀬健・横田一正 (1985),ゲーデルの世界: 完全性定理と不完全性定理, 海鳴社, ISBN 4-87525-106-8
    （ゲーデルの完全性定理と不完全性定理の解説書。両方の原論文の邦訳が収録されている）
教科書
  • 前原昭二 (2006), 数学基礎論入門, 朝倉書店, ISBN 4-254-11723-X
  • 新井敏康 (2011), 数学基礎論, 岩波書店, ISBN 4-000-05536-4
  • 田中一之 編著 (1997), 数学基礎論講義―不完全性定理とその発展, 日本評論社, ISBN 4-535-78241-5
  • Per Lindstrom (1997), Aspects of Incompleteness, Springer-Verlag, ISBN 3-540-63213-1
  • Petr Hajek and Pavel Pudlak (1993), Metamathematics of First-Order Arithmetic, Springer-Verlag, ISBN 3-540-63648-X
講義ノート
誤用と誤解について
  • フランセーン, トルケル 『ゲーデルの定理：利用と誤用の不完全ガイド』 田中一之訳、みすず書房、2011年。ISBN 978-4622075691。

関連項目

外部リンク

テンプレート:Metalogic



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=ゲーデルの不完全性定理&oldid=114128」から取得