(有)未来検索ブラジルが運営するあらゆる言葉についての記事を閲覧・編集したり、コメントをしたりするサイトです。

単語記事; 不完全性定理

編集

不完全性定理とは、ゲーデルが1931年に発表した定理である。

概要

この定理には

第一「再帰的で(ω)無矛盾な自然数論を充分に表現できる形式系は完全ではない.」

第二「再帰的で無矛盾な自然数論を充分に表現できる形式系は自分自身の無矛盾性を証明できない.」

の二つがある。

(以下、理論=形式系、仮定=公理、主張=論理式(命題)とする。)

要約すると

一つ目は、どんな数学理論にもその理論の中で表現できる主張で正否の判定ができないものが存在する。

この例として、ZFに対する選択公理、ZFC（ZF＋選択公理）に対する連続体仮説などが存在する。

二つ目は、数学理論の無矛盾性はその理論又はそれより強くない(より多くの仮定を含まない)理論からは示せないということ。

このことから、理論Aにbという仮定を付け加えた理論A+bがあるとき、A+bからAの無矛盾性が示せれば、bはAでは証明できないことが分かる。

 

ゲーデルは、数学理論をそれ自体の中で(自然数を使って)表現することで、「この命題は証明できない」と解釈できる命題を理論内で表現しこの二つの定理を証明している。この技法(ゲーデル数化)は現在でいうところのコンパイルなどに相当する（論理式(プログラム)->機械語という意味で）。

この定理は数学、情報科学、さらには哲学などにも大きな衝撃と影響を与えた。

関連動画

 

 

 

関連商品

 

 

関連コミュニティ

関連項目

携帯版URL:
http://dic.nicomoba.jp/k/a/%E4%B8%8D%E5%AE%8C%E5%85%A8%E6%80%A7%E5%AE%9A%E7%90%86
ページ番号: 4451888 リビジョン番号: 1116090
読み：フカンゼンセイテイリ
初版作成日: 10/09/01 17:58 ◆ 最終更新日: 11/03/23 06:08
編集内容についての説明/コメント: 微修正
記事編集 / 編集履歴を閲覧 /

不完全性定理について語るスレ

-不完全性定理の記事へ戻る- 1-
2 ： ななしのよっしん ：2010/09/02(木) 21:16:02 ID: 611hircYr8
>>ZFに対する選択公理、ZFC（ZF＋選択公理）に対する連続体仮説
どちらもZF, ZFCに対して独立なので例になってないですよ。

不完全性なので公理系と証明体系から作られる命題で否定も肯定もできない例でないといけないですが、そうした例は有名なものってあんまり無かったような（不完全性定理の証明で作られるような人為的なもの以外の命題はあるにはあるがどれもかなりマニアックだった記憶がある）。
3 ： ななしのよっしん ：2010/09/02(木) 21:23:07 ID: jEOd0DcN5U
これは論理学の本で読んだけど…orz
4 ： 山元 ：2010/09/02(木) 22:56:57 ID: ayjw8SRaB+
>>2
選択公理も、連続体仮説もZFの言葉で書かれた命題であり
「公理系と証明体系から作られる命題で否定も肯定もできない例」
になっています。
この記事が充分ではないし、間違いはあるかもしれないけど、
その指摘は間違いです。
というか第一不完全性定理で述べられているような命題を独立命題と言い、体系内に独立命題が存在するのを主張するのが第一です。
関連商品の本を一冊読破することをお勧めします(ブルーバックス以外で、BBは初等的すぎるのと間違いだらけなので、勉強にはお勧めできません)。
5 ： ななしのよっしん ：2010/09/04(土) 18:02:32 ID: CkIt1hQKwH
読んでいて何かおかしいと思ったら不確定性原理の記事だと思って読んでいた
6 ： ななしのよっしん ：2011/08/01(月) 00:49:28 ID: jEOd0DcN5U
「ω矛盾かつ完全なロビンソン算術Qの再帰的拡大は存在しない」

いろんな表現があるんだな…分からんけど。
7 ： 山元 ：2011/08/07(日) 00:53:56 ID: ayjw8SRaB+
>>6
そこは、"ω無矛盾"な
8 ： ななしのよっしん ：2011/09/26(月) 20:19:05 ID: jEOd0DcN5U
ごめんorz
9 ： ななしのよっしん ：2012/01/20(金) 19:37:23 ID: 9zV5isJXlX
第二不完全性定理を、ものの数分程度で第一不完全性定理から導かれて唖然とした経験があるのは俺だけじゃないはず。
第一のほうで出てくる「肯定も否定も示せない命題」と
「自分自身が無矛盾であるという命題」が同値であることが容易に示せるんだよね。

ところで
>一つ目は、どんな数学理論にも…
の部分がどうしても気になる。
無限集合に対する全称や存在を考えなくていい体系ならどんな命題でも、
全ての場合を確認することで正否が判定できるわけで…。
だが「○○であるどんな数学理論にも…」の○○に入る、わかり易い語句が思い付かない…。
というわけで、表記が厳密でないのを承知でこの表現になっているのなら別にいいのですが、
何かいい表現があれば修正お願いします。
10 ： ななしのよっしん ：2012/01/21(土) 00:18:50 ID: ayjw8SRaB+
>>9
数学理論は"再帰的で(ω)無矛盾な自然数論を充分に表現できる形式系"の言い換えで、
正確の言えば、論理に関数記号や公理などを付け加えたものは全部数学理論だろうけど、
通常の数学理論は大抵この条件を満たしてるからこう言い換えてもいいかなって考えた。
ゲーデルもこの条件は数学理論が数学理論であるための最低条件だ！
(不完全性定理が成り立つための充分条件でもあるが)
ってのりで書いてるだろうからいいかなと。

平易な言葉なら、"健全で強力な数学理論"とかいうことはできるだろうけど、
説明したようでしてない修飾つけて無駄に長くなるより関節な方がいい気がするんだよね。
11 ： ななしのよっしん ：2012/02/05(日) 16:22:18 ID: 7Q1f/sgBzf
タマヒュン動画（ω）
-不完全性定理の記事へ戻る- 1-
ページトップへ戻る