不完全性定理単語

フカンゼンセイテイリ
  • 4
  • 0pt
掲示板へ

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

概要

この定理には

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

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

の二つがある。

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

要約すると

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

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

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

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

 

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

チューリングマシンの停止問題は、この不完全性定理をコンピュータの用に置き換えたものである。

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

関連動画

 

 

 

関連商品

 

 

関連コミュニティ

関連項目

【スポンサーリンク】

  • 4
  • 0pt
スマホ版URL:
https://dic.nicovideo.jp/t/a/%E4%B8%8D%E5%AE%8C%E5%85%A8%E6%80%A7%E5%AE%9A%E7%90%86
記事編集 編集履歴を閲覧

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

不完全性定理

38 ななしのよっしん
2021/02/02(火) 11:07:46 ID: 0OFcIKVMzj
不完全性定理の誤った説明は大体次に由来する:
1. 「再帰的」「全」「理論」「矛盾」などの言葉が数理論理学で正確に定義されているにも関わらず、それらを用いずに「数学理論」などの既存の教科書には出てこないような意味不明瞭のオリジナルワードを持ち出してくる人が多いこと。
2. メタ明と形式的体系上の「明」の区別をできていない人が多いこと。後者の「明」は前者を形式的体系上で形式化したもの。また、前件肯定やΣ1全性定理のようなメタすらもペアノ算術PA(のRE拡大)の内部で形式化されるという理解が曖昧な人が多いこと。

2を理解していれば、第二不完全性定理はいわば、第一不全性の明をPA(もっというとΣ1論理式に対する帰納法の公理図式を持っていれば良い)の内部で形式化することで明される、ということがわかるはず。
ちなみに、【この方法】による第二不完全性定理明は形式化された(Σ1論理式に関する)数学的帰納法を用いるので、数学的帰納法公理図式を全く持たないロビンソン算術Qに対して【この方法】を適用することができない。
(省略しています。全て読むにはこのリンクをクリック!)
39 ななしのよっしん
2021/02/08(月) 19:03:23 ID: MSU/AwZjSn
>>38
すみませんお手上げっす
>>37
不完全性定理は「数学で用いる論理を含み、」→まぁ何とか分かる
自然数理論が展開でき、」→ギリギリ分かるかも・・・
「その公理系、推論規則を実際に与えることができるような形式的体系では」→お手上げ

「つまり不完全性定理は、数学内の形式体系(=数学基礎論の一)で成立する定理」→へえ、じゃあ他の体系では成立しないの?
「TA(=True Arithmetic)やプレスバーガー算術や「実閉体の理論」といった数学体系では成立しない」→かなり分かりやすい!
「それくらい狭く限定的で、他の数学体系や哲学との関係が少ない定理」→そういうことかぁ
40 ななしのよっしん
2021/08/25(水) 21:15:27 ID: s+H+BN2e90
直接には関係がないが,全く縁とも言えないホットなニュースが最近あった.
”ある物体(の熱状態)の初期状態を与えられているとき,それが熱衡に至るのかどうかを決定する方法が存在しない”
ということが数学的に明されたらしい.

温度の異なる物体を接しておいて放置するとやがて熱衡に至るのが普通だが,稀に熱衡に至らない場合があった.
この事実に対して,どのような物体(条件)で熱衡化するのかどうかを決定する問題あり,多くの研究者が取り組んできたが成果があがらなかった.
今回の学習院大学研究結果は,熱衡に至る過程のモデルと計算理論モデルを対応させ,ある種の停止問題の決定不能性に帰着させることで,そもそもその方法自体が存在しないということを明したというものだ.

これは一見否定的な結論だが,見方を変えれば,物体の熱衡に至る過程の数学モデルが,ある種の不完全性定理が成立するほどに複雑な構造をしているということを意味している.
41 ななしのよっしん
2021/09/07(火) 22:34:08 ID: Ld5GIE96Va
不完全性定理」があるということは、「不完全性定理が成立しない体系(ユークリッド幾何学など)」や「全性定理」や「ゲンツェンの矛盾明」もあるということなので
「ある種の不完全性定理」があるなら、「ある種の不完全性定理が成立しない体系(ある種のユークリッド幾何学など)」や「ある種の全性定理」や「ある種のゲンツェンの矛盾明」もある
意味不明なことになる
42 ななしのよっしん
2021/09/11(土) 22:28:59 ID: s+H+BN2e90
>>41
>「ある種の全性定理」や「ある種のゲンツェンの矛盾明」もあると意味不明なことになる
表面上の見出しだけ追って内容を読まない(読めない)典例.
「ゲーデルの不完全性定理の系」と呼ばれる一連の現は記念碑的なゲーデル自身によるPAω矛盾性についての明から始まった.
今日ではこれを第一不完全性定理とよぶ.後にロッサーがPAに関しての不完全性定理完成形を発表する.
この場合の「全性」は形式的全性・構文論的全性というべきもので,
「数理論理学上のある形式体系において,その体系で形式表現可なあらゆる言明において,その肯定あるいは否定のどちらかが明可である」
という場合の意味である.

全性定理全性は意味論的全性というべきもので,
「その形式体系における恒命題は必ず明可である」
ということを意味する.
(省略しています。全て読むにはこのリンクをクリック!)
43 ななしのよっしん
2021/09/11(土) 22:49:23 ID: s+H+BN2e90
>>41
さらに,不完全性定理が成立しない(弱い)体系が存在することがオカシナコトにはならない.

ペアノ的自然数と通常の加法・乗法を定義した古典論理的な形式体系において,「矛盾であるなら(構文論的)全性の意味において不全である」というが初期の不完全性定理である.
この形式体系の前提はもう少し弱めることもでき,最初のものより弱いいくつかの体系でも不完全性定理が成り立つことが知られている.
しかし,ユークリッド幾何学の形式体系などのようにペアノ的整数を含む体系よりもかなり単純な体系では不完全性定理は成立しない.
これは矛盾でもオカシナコトでもない.
また,ZFCでも不完全性定理が(PAのそれとは異なるが)成り立つが,ZFCにより強い公理を加えた集合論の体系からはZFC矛盾性は明できてしまう.

こういった常識的なことで迷ったり,誤ったをする前に全性定理不完全性定理のまともな明をまず理解するべきである.
そうでなければ,「自分は不完全性定理全性定理
(省略しています。全て読むにはこのリンクをクリック!)
44 ななしのよっしん
2021/09/15(水) 13:33:00 ID: MSU/AwZjSn
>>40
数学的に明されたらしい」とな? それで「ある種の不完全性定理が成立する」と? わかるようなわからんような・・・
ある種のピタゴラスの定理とか、ある種の因数定理みたいなものがあるのか?
“こっちでは○○定理が成立するが、あっちでは○○定理は成立せず、ある種の○○定理が成立する”、とか・・・?

不完全性定理数学基礎論の一部分だよね
数学基礎論での明が関係ある分野は、数学基礎論や計算機科学なのでは?
衡とかの力学分野でなく

衡(熱力学や量子熱力学)に関して何かが数学的に明されたのなら、その明は数理力学での明であるか、数理物理学での明であるんじゃないかと
45 ななしのよっしん
2021/09/18(土) 12:50:21 ID: s+H+BN2e90
>ある種のピタゴラスの定理とか、ある種の因数定理みたいなものがあるのか?
あるよ.
よく知りもしないのに,言葉にを取らまえて突っかかってきなさんな.
上でも散々書かれているように,不完全性定理の系はただ単一の数学のことをすのではない.
大雑把には,ゲーデルの記念碑的なPAに関するω矛盾性の文脈においての不完全性定理のことや,ロッサーによる強化された結果を暗黙にす.
PA以外の形式体系のモデルに関して,先の不完全性定理と同様,あるいは類似現が成り立つという様々な結果のこと全体を不完全性定理とよぶ.
例えば,数論の算術形式であるPAについての不完全性定理の内容と集合論の一つの形式であるZFCについての不完全性定理では,その結論(現)を示す要部分の写像の構成が異なるので厳密には異なる現している.
ただし,明論の文脈においては同様の現なので不完全性定理と呼ぶのだ.

46 ななしのよっしん
2021/09/18(土) 12:53:30 ID: s+H+BN2e90
(続き)
さらには,計算理論(形式言理論も含む)の古典的分野においても,計算可性という文脈においての「プログラムの停止性問題の非決定性」という定理がちょうど数理論理学のゲーデルの不完全性定理と対応する.これは,コルモゴロフチャイティンらによる成果だ.
これも不完全性定理の類似物であり,多くの文脈で「不完全性定理の一種」とされている.
実際,第二不完全性定理にはコルモゴロフ複雑性による別解釈・別明が存在する.

今回の熱力学における成果は,「計算理論における停止問題の非決定性の構造」と「熱衡に至る熱理論の数理モデル」を対応させることで,解決している.
つまりは,数理物理の問題解決に純数学理論が使われたというありふれたことでしかない.

それとも,数理物理理論物理は純数学理論を利用してはいけないのかい?
47 削除しました
削除しました ID: s+H+BN2e90
削除しました