不完全性定理

不完全性定理

(サイエンス)
ふかんぜんせいていり

ゲーデルの不完全性定理(Gödel's Theorem)とも。
簡単に言えば、「完全で無矛盾な公理系は存在しない」ということを証明した*1
数学基礎論の分野で提出された定理だが、その影響は数学はもとより、論理学や哲学やその他の人間の知(理性)の全分野にも及ぶものであり、フォン・ノイマンをして「(その業績は)不滅以上のものである」と言わしめた。

解説

不完全性定理には第一定理と第二定理があり、第一定理は、ある程度の強さを持った*2任意の公理系について、それが公理系としての標準的な条件*3を満たし、且つ無矛盾*4であるならば証明も反証も出来ない文が存在することを主張する。

それに対して第二定理はある程度の強さを持った任意の公理系について、それが公理系としての標準的な条件を満たし、且つ無矛盾ならば、その公理系の無矛盾性を表わす文はその公理系で証明も反証もできない、という事を述べている。ただし、第一定理の成立よりも強い条件を必要とする。それはその公理系の強さに対する条件である。というのも第二定理は第一定理をその公理系の中で形式化して証明させる事で得られるので、第一定理を形式化できる程度の強さがなければならないからである*5
第一不完全性定理は公理系という手法の限界の一つを示したといえよう。第二不完全性定理は20世紀初めに起こった数学基礎論の運動の中で、論理主義直観主義に並ぶ、ヒルベルトの形式主義(いわゆるヒルベルト・プログラム)に対して決定的な打撃を与えた事で有名である。

関連語

リスト::数学関連
リスト::定理
ゲーデル
チューリング

*1:より正確には「無矛盾な公理系は不完全であると証明した」だが。完全とか不完全の中身は省略する。

*2:厳密には弱い算術が展開できる程度であり、ロビンソン算術より強い事が必要である。

*3:厳密にはその公理系の公理の集合がrecursiveである事。

*4:ゲーデルの原論文ではより強い条件が仮定されていたが、後にロッサーによってこの条件に弱められた。

*5:数学的帰納法が入ったペアノ算術が典型である。

ネットの話題: 不完全性定理

人気

新着

新着ブログ: 不完全性定理