不完全性定理（読み）フカンゼンセイテイリ（その他表記）incompleteness theorem

デジタル大辞泉

ふかんぜんせい‐ていり〔フクワンゼンセイ‐〕【不完全性定理】

⇒ゲーデルの不完全性定理

出典　小学館

改訂新版　世界大百科事典

不完全性定理 (ふかんぜんせいていり)
incompleteness theorem

ゲーデルの定理とも呼ばれる。形式的体系は，その体系内で定式化できるどんな命題Aに対してもAまたはその否定（￢A）が証明できるとき，完全であるといわれる。1931年，K.ゲーデルは超数学の算術化という手法を導入して，本質的に自然数論を含むような形式的体系Sが無矛盾であれば，Sは不完全であることを示した（第1不完全性定理）。彼は無矛盾よりも強い条件であるω-無矛盾という仮定のもとでこれを証明したが，後にロッサーJ.B.Rosserは無矛盾という仮定で十分であることを指摘した。数学の上述の意味での〈完全〉な形式的体系を与えるということは，これにより原理的に不可能なことが明らかになった。さらに，ゲーデルは上記定理の証明を検討することにより，〈本質的に自然数論を含む数学の形式的体系が無矛盾ならば，その無矛盾性を，その体系内で形式化できるような手法のみによって証明することはできない〉（第2不完全性定理）ことを証明した。これは，数学の無矛盾性の証明を有限の立場で行うというD.ヒルベルトの計画に深刻な問題を投げかけるものとなった。しかし，これによってヒルベルトの計画が挫折したことを意味するものではない。実際に，36年，ゲンツェンG.Gentzenは有限の立場を一段と深化させることによって，純粋数論（算術）の無矛盾性を達成した。その証明には算術の範囲を超える論法が用いられているが，十分構成的なものである。さかのぼって，ゲーデルは1930年，第1階の述語論理の論理式で〈普遍妥当〉なものはすべて第1階の述語論理の形式的体系の中で証明可能であることを示した。これをゲーデルの完全性定理というが，この完全性は上述の〈完全性〉とは別の概念である。
→数学基礎論
執筆者：柘植 利之

出典　株式会社平凡社「改訂新版　世界大百科事典」

百科事典マイペディア

不完全性定理【ふかんぜんせいていり】

ある体系内で定式化できるあらゆる命題に対して，その真偽がすべて決定できるとき，その体系は完全といわれる。不完全性定理とは〈自然数論を含む形式的体系が無矛盾ならば，それは完全ではない〉（ゲーデルの第１不完全性定理），〈自然数論を含む形式的体系が無矛盾ならば，その無矛盾性をその体系内から導くことはできない〉（ゲーデルの第２不完全性定理）をいう。1931年ゲーデルが発表。ゲーデルは第１不完全性定理を無矛盾性よりも強いオメガ無矛盾という仮定のもとで証明したが，その後ロッサーJ.B.Rosserがオメガ無矛盾を無矛盾に置き換えても第１不完全性定理が成り立つことを証明し，現在の形となっている。

出典　株式会社平凡社

ブリタニカ国際大百科事典 小項目事典

不完全性定理
ふかんぜんせいていり
incompleteness theorem

自然数論を含む理論では，Aが証明されても非Aが証明されても矛盾が起るような，命題Pが存在するという定理。 K.ゲーデルがこの定理を証明して以来，いわば数学の対象化としての性格が数学基礎論にもたらされ，20世紀後半における基礎論の隆盛にいたった。

出典　ブリタニカ国際大百科事典 小項目事典

世界大百科事典（旧版）内の不完全性定理の言及

【計算可能性】より

…したがって，Pが計算可能でないこと，つまり決定不能であることがわかる。
[論理との関係]
　計算可能性の概念はゲーデルの不完全性定理の証明でも重要な役割を果たしている。このように計算と論理は密接な関係にあるが，とくに近年になり構成的論理とλ計算との深い関係が明らかになり，論理が近代的なプログラミング言語の設計とその理論的基礎を与えるようになりつつある。…

【ゲーデル】より

…最初の著名な論理学上の業績として，第一階述語論理の〈完全性定理〉の証明がある(1930)。これに続いて〈不完全性定理〉を見いだした(1931)。これは20世紀前半における論理学および数学基礎論のもっとも重要な発見であり，ゲーデルの名を不朽ならしめた。…

※「不完全性定理」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」