ゲーデルの不完全性定理
ゲーデルの不完全性定理(ゲーデルのふかんぜんせいていり、英: Gödel's incompleteness theorems、独: Gödelscher Unvollständigkeitssatz)または不完全性定理とは、数学基礎論とコンピュータ科学(計算機科学)の重要な基本定理。(数学基礎論は数理論理学や超数学とほぼ同義な分野で、コンピュータ科学と密接に関連している。) 不完全性定理は厳密には「数学」そのものについての定理ではなく、「形式化された数学」についての定理である。クルト・ゲーデルが1931年の論文で証明した定理であり、有限の立場(英語版)(形式主義)では自然数論の無矛盾性の証明が成立しないことを示す。なお、少し拡張された有限の立場では、自然数論の無矛盾性の証明が成立する(ゲンツェンの無矛盾性証明(英語版))。
数学基礎論研究者の菊池誠によると不完全性定理は、20世紀初め以降に哲学から決別した数学基礎論の中で現れた。コンピュータ科学者・数理論理学者のトルケル・フランセーンおよび数学者・数理論理学者の田中一之によると、不完全性定理が示した不完全性とは、数学用語の意味での「特定の形式体系Pにおいて決定不能な命題の存在」であり、一般的な意味での「不完全性」とは無関係である。
ゲーデル文 ¬ P r o v a b l e A R G ( m , m ) {\displaystyle \lnot ProvableARG(m,m)} のゲーデル数を n p m m {\displaystyle npmm} とする。