ふかんぜんせい‐ていり〔フクワンゼンセイ‐〕【不完全性定理】
読み方:ふかんぜんせいていり
ゲーデルの不完全性定理
(不完全性定理 から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/12/30 09:31 UTC 版)
ゲーデルの不完全性定理(ゲーデルのふかんぜんせいていり、英: Gödel's incompleteness theorems、独: Gödelscher Unvollständigkeitssatz)または不完全性定理とは、数学基礎論[1]とコンピュータ科学(計算機科学)の重要な基本定理[2]。(数学基礎論は数理論理学や超数学とほぼ同義な分野で、コンピュータ科学と密接に関連している[3]。) 不完全性定理は厳密には「数学」そのものについての定理ではなく、「形式化された数学」についての定理である[4][注 1]。クルト・ゲーデルが1931年の論文で証明した定理であり[5]、有限の立場(形式主義)では自然数論の無矛盾性の証明が成立しないことを示す[3][5]。なお、少し拡張された有限の立場では、自然数論の無矛盾性の証明が成立する(ゲンツェンの無矛盾性証明)[3][注 2]。
注釈
- ^ 原文:
数学の基礎をめぐる論争の実質的な勝者が形式主義である … .不完全性定理は数学そのものについての定理ではなく,「形式化された数学」に関する定理であり,形式主義的な数学観についての定理である.
[4] - ^ 原文:
ゲーデルの不完全性定理は有限の立場(形式主義)で数学の無矛盾性を証明することはできないことを示した.ゲンツェン(Gentzen)は,有限の立場より緩い制限のもとで自然数論の無矛盾性を証明した.
[3] - ^ 詳細は「ゲーデルの不完全性定理#数学と哲学の分離」を参照
- ^
- ^ 詳細は「ゲーデルの不完全性定理#誤用例」を参照
- ^ 歴史的には論理式のゲーデル数化の概念が先に生まれ、後にコンピュータがデータを数値で表すようになった。なお、ゲーデル自身は、素因数分解の一意性を利用して論理式のゲーデル数化を実現している。
- ^ 実際、が証明可能ならの証明系列が存在するので、論理式の列のゲーデル数をとすると、「Proof」が証明可能、したがって特に「」=「」が証明可能。一方我々は「」が証明可能な事を仮定していたので、これは矛盾である。
- ^ ω無矛盾とはが証明できれば、を満たす自然数が実際に存在することを指す。定義より「」は「」であった。ω無矛盾性より、「」を満たす自然数が実際に存在し、をゲーデル数に持つ論理式の列がの証明系列になる。
- ^ 訳注:自己言及的でないこと。
- ^ 訳注:この場合の「帰納的可算」とは、すべての定理のゲーデル数を枚挙する計算可能関数が存在する(実効的に枚挙可能)ことを意味する。クレイグのトリックによれば、このことは定理集合が帰納的な公理系から生成される(演繹閉包である)ことと同値である。
- ^ 数学基礎論と不完全性定理
…
数学の正しさには一分の隙もなく,数学では矛盾する二つの結論が導かれることは決して無いと昔から信じられている. … そもそも「信じられている」という言葉を使うことは不適切であり,不謹慎でさえあるかも知れない.この数学の正しさと無矛盾性に対する確信が揺らいだことがかつて一度だけあった. … 19世紀末から20世紀初めにかけて数学の中で次々と逆理が発見された.正しさは数学の絶対的な規範であり,たとえ一ヵ所にでも亀裂が入れば数学の世界全体は粉々に砕けてしまう.[23] …
この数学の基礎に関する「不安の時代」には … 果たして数学は正しく無矛盾なのか,そもそも定理や証明とは何なのかといった哲学的な問題に対して,伝統的な哲学的手法によってではなく,数学的手法を用いて答えようとする形式主義の試みの中から数学基礎論と呼ばれる数学の一分野が生まれた.[25] - ^ 宴のあと
…
数学の危機が真面目に論じられていた「不安の時代〔19世紀末~20世紀初頭〕」は意外に簡単に終わった.現在,数学の基礎を本気で心配している数学者はまずいない. … 「不安の時代」が通り過ぎた後,数学基礎論は哲学と袂を分かち,独自の数学的な問題意識や価値観を見出した.数学基礎論の専門家は「哲学的な動機のもとで数学基礎論を語る時代は終わった」と考えるようになり … 数字基礎論は普通の数学に生まれ変わった.不完全性定理についても数学基礎論の専門家の間では,哲学的な意義よりも様々な数学的応用可能性のほうが大切であると考えられるようになった.
電子技術の爆発的な発展と共に成長した計算機の基礎理論においても不完全性定理は重要な基本定理の一つであるが,そこでも不完全性定理は定理の主張そのものよりも,定理の証明の中で提案され用いられた様々な考え万や,不完全性定理から導かれる事実のほうが遥かに重要であると考えられているであろう.[2] - ^
数学と哲学
20世紀初頭の数学の基礎に関する「不安の時代」には,数学者と哲学者は共に数学の基礎について論じていた.
それが今では数学者と哲学者は極めて疎遠である.数学者,特に数学基礎論の専門家は哲学者による数学の基礎についての議論を最近の数学を無視した色褪せた100年前の論争の焼き直しに過ぎないと感じ,哲学者は最近の数学としての数学基礎論の進展を重箱の隅をつつくような技術的で瑣末な話題だと考えている.[26] …数学基礎論が哲学との繋がりを失ったことを知らない数学者は今でも数学基礎論のことを「哲学のようなもの」と考えている. … この,数学基礎論が「哲学のようなもの」であるという考えは,「哲学のような深い立派なもの」ではなく,「哲学のようなツマラナイコト」という意味であるため,このような考えを「他愛ない無邪気なもの」とは見過ごせない数学基礎論の専門家は,数学基礎論が哲学ではなく数学であることの説得を,何度となく試みてきた.[27]
- ^ フランセーンはストックホルム大学で哲学を専攻し、1987年に「Ph.D.(哲学)」を取得[7]。ルレオ工科大学でのフランセーンのページによると、「(哲学における)自分の博士論文 “my PhD thesis (in philosophy)”」は世界各国の大学図書館で閲覧できる[28]。
出典
- ^ 青本 et al. 2005, p. 510.
- ^ a b c d e 菊池 2014, p. iii.
- ^ a b c d 青本 et al. 2005, p. 294.
- ^ a b 菊池 2014, p. 9.
- ^ a b c d e f g 日本数学会(編) 2011, p. 357.
- ^ 菊池 2014, pp. ii–iii.
- ^ a b c d フランセーン 2011, p. 奥付け.
- ^ a b c d e f g h フランセーン 2011, p. 230.
- ^ a b c フランセーン 2011, p. 145.
- ^ フランセーン 2011, p. 4, 7, 126-127.
- ^ a b c d フランセーン 2011, p. 54.
- ^ 菊池 2014, p. 5.
- ^ a b c 菊池 2014, p. 248.
- ^ 照井一成 (2018年). “数理論理学 II (不完全性定理)” (PDF). 2023年4月6日閲覧。
- ^ 青本 et al. 2005, p. 116.
- ^ a b 日本数学会(編) 2011, p. 355.
- ^ フランセーン 2011, pp. 21–22.
- ^ a b フランセーン 2011, p. 22.
- ^ フランセーン 2011, pp. 22–23.
- ^ a b フランセーン 2011, p. 47.
- ^ フランセーン 2011, pp. 47–48.
- ^ 菊池 2014, p. 奥付け.
- ^ a b 菊池 2014, p. i.
- ^ 菊池 2014, pp. i–ii.
- ^ a b c 菊池 2014, p. ii.
- ^ a b c 菊池 2014, p. 11.
- ^ a b 菊池 2014, pp. 11–12.
- ^ a b Franzén 2008, p. Torkel Franzén.
- ^ a b c d フランセーン 2011, p. 9.
- ^ a b c d フランセーン 2011, p. 10.
- ^ a b c d e f フランセーン 2011, p. 4.
- ^ a b c フランセーン 2011, p. 229.
- ^ フランセーン 2011, pp. 3–4.
- ^ フランセーン 2011, pp. 230–231.
- ^ a b c d フランセーン 2011, p. 231.
- ^ フランセーン 2011, pp. 125–126.
- ^ a b c d e f フランセーン 2011, p. 126.
- ^ ソーカル & ブリクモン 2012, p. 262.
- ^ a b c フランセーン 2011, p. 233.
- ^ フランセーン 2011, p. 107.
- ^ a b フランセーン 2011, p. 108.
- ^ フランセーン 2011, pp. 108–109.
- ^ フランセーン 2011, pp. 112–113.
- ^ a b c d フランセーン 2011, p. 120.
- ^ a b c d フランセーン 2011, p. 7.
- ^ フランセーン 2011, p. 127.
- ^ フランセーン 2011, p. 128.
- ^ a b フランセーン 2011, p. 131.
- ^ フランセーン 2011, pp. 131–132.
- ^ a b フランセーン 2011, p. 132.
- ^ a b c d e フランセーン 2011, p. 234.
- ^ フランセーン 2011, pp. 234–235.
不完全性定理
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/18 15:00 UTC 版)
ゲーデルの不完全性定理は、ロビンソン算術 Q の再帰的拡大(またはRE拡大)である理論 T がω無矛盾(または無矛盾)であるとき、 T ⊬ Con ( T ) {\displaystyle T\nvdash \operatorname {Con} (T)} である、すなわち理論自身では自身の無矛盾性を証明できないことを述べている。
※この「不完全性定理」の解説は、「無矛盾」の解説の一部です。
「不完全性定理」を含む「無矛盾」の記事については、「無矛盾」の概要を参照ください。
不完全性定理と同じ種類の言葉
- 不完全性定理のページへのリンク