ゲーデルの不完全性定理（ゲーデルのふかんぜんせいていり、）又は単に不完全性定理とは、数学基礎論における重要な定理で、クルト・ゲーデルが1930年に証明したものである。ゲーデルの定理でいう証明不能命題Gは、「Gは証明できない」という命題と同値である。Gはゲーデル文と呼ばれる。Gが証明可能であれば、Σ完全性により命題「Gは証明できる」もまた証明可能である。一方Gは命題「Gは証明できない」と同値であることが証明可能であるので、両者から矛盾が導かれる。つまりしたがって、対偶を取ればとなる。また、￢Gが証明可能であれば、Gの性質から命題「Gは証明できる」も証明可能である。この際、もしGそのものが証明不能だとすると、ω矛盾ということになる。ω無矛盾であればGも証明可能である。しかしGが証明可能であれば「Gは証明できない」も証明可能であるので、やはり両者から矛盾が導かれる。したがってω無矛盾であれば￢Gも証明できないのである。よってω無矛盾であれば、Gも￢Gも証明できない（第一不完全性定理）。なお、証明可能性の代わりに真理性を用いるならば、パラドックスが導かれる。このことから、自然数論における真理性は自然数論の中では表現できないことが示される（タルスキの定理）。ゲーデル文を構成するためには自然数論の式を自然数に変換するゲーデル数および自己言及で用いられる対角化の技法（を形式化したもの）が必要である。後者は対角化補題と呼ばれる。自然数を変数とする述語「xは…である」の対角化は、左記の述語のxに「xは…である」のゲーデル数を代入した命題である。その意味は「「xは…である」は…である」となる。ゲーデル文Gは「「xで表される述語の対角化は証明できない」で表される述語の対角化は証明できない」と表される。「xで表される述語の対角化は証明できない」の対角化は、G自身と同値になる。さて、自然数論の無矛盾性とは、「自然数論において矛盾が証明できない」ということである。そして、自然数論による自然数論の無矛盾性証明とは、「」内が、自然数論で証明できるということである。「自然数論で矛盾が証明できない」と自然数論で証明できれば、第一不完全定理での議論中の(B)より「Gが証明できない」と証明できる。しかし、「Gが証明できない」とはGと同値であるから、Gも証明されることとなり、そこから第一不完全定理での議論中の（A)により、矛盾が証明される。したがって自然数論が無矛盾、すなわち自然数論で矛盾が証明されないならば、そのこと自体も自然数論では証明できない（第二不完全性定理）。ゲーデルの定理は「自然数論を含む帰納的公理化可能な無矛盾理論」に対して示されているが、ここでは簡単の為、自然数論のみを扱う。一般の場合も同様。概要でも説明したように、ゲーデル数というテクニックを使って間接的に自己言及を可能とし、ゲーデル文を構成する。コンピュータでは全てのデータを一意な数値で表しており、特に文字列や論理式そして論理式の列も数値で表す。このように、論理式を数値で表す行為を論理式のゲーデル数化といい、命題Pに対応する数値をPのゲーデル数という。ゲーデル数化により、論理式に関する様々な性質を論理式として表すことができる。たとえば、といった論理式を作ることができる。ここで、AxiomやMPの引数が論理式自身ではなく自然数であることが重要である。前述のように自然数論は「命題に言及する命題」を取り扱うことはできないが、「命題のゲーデル数に言及する命題」なら取り扱うことができるのである。Axiom(x)やMP(x,y,z)などを組み合わせれば、という論理式も作ることができる。さらにProofを「∃」と組み合わせることで、という論理式も作ることができる（上ではPは引数を持たず、Qの引数は1つである）。論理式￢ProvableARG(x,x)のゲーデル数をmとすると、xにmを代入した論理式￢ProvableARG(m,m)がゲーデル文となる（対角化）。ゲーデル文￢ProvableARG(m,m)のゲーデル数をnpmmとする。￢ProvableARG(m,m)が証明可能とすると、Provable(npmm)は真である。このときΣ完全性よりProvable(npmm)は証明可能である。一方￢ProvableARG(m,m)は「mをゲーデル数に持つ論理式にmを代入したものは証明不能」という意味である。mをゲーデル数に持つ論理式にmを代入したものはnpmmであるから￢ProvableARG(m,m)⇔￢Provable(npmm)が証明可能である。したがって、￢Provable(npmm)は証明可能である。したがってProvable(npmm)および￢Provable(npmm)が証明され、これは矛盾であるが、これは自然数論が無矛盾であるという仮定に反する。ProvableARG(m,m)が証明可能だとすると、ProvableARG(m,m)⇔Provable(npmm)によりProvable(npmm)が証明可能である。このときω無矛盾性を前提すると、npmmをゲーデル数とする論理式￢ProvableARG(m,m)が証明可能である。それ故、矛盾が証明されるが、これは自然数論が無矛盾であるという仮定に反する。矛盾を「⊥」で表し、「⊥」のゲーデル数をbとする。すると、「自然数論の体系内で自然数論の無矛盾性を証明できる」という言説をの意味に解することができる。まずが自然数論の体系内で証明可能であると仮定する。第一不完全性定理のところで示したように、￢ProvableARG(m,m)が証明できれば矛盾が証明できる。この議論を自然数論の体系内で行うことで、が自然数論の体系内で証明可能なことがわかる。故に対偶を取ることでが自然数論の体系内で証明可能なことがわかる。したがって、仮定および￢ProvableARG(m,m)⇔￢Provable(npmm)からが自然数論の体系内で証明可能なことがわかる。第一不完全性定理の所で示したように、￢ProvableARG(m,m)が証明可能だと、矛盾が証明される。したがって矛盾が証明されないならば、￢Provable(b)は証明されない。数学と計算機科学において、「決定不能」という言葉には二つの異なった意味がある。一つ目は証明論の文脈でゲーデルの定理に関連して使われる意味であり、特定の形式的体系の下で或る命題を証明も否定の証明もできないことを言う。二つ目は（本項では詳述しないが）計算可能性理論に関連した用法であり、命題ではなく決定問題に適用される。決定問題とは入力に対して答が YES か NO のいずれかになるような問題である。ある問題を全ての入力に対して正しく解答するような計算可能関数が存在しないとき、そうした問題は決定不能であると言う。このように決定不能という言葉には二つの意味があるので、代わりにという用語をもって「証明も否定の証明もできない」という意味にあてる場合がある。ところが「独立」という用語にしても依然曖昧な部分がある。単に「証明できない」という意味を表し、「否定の証明もできない」かどうかについてはあえて含意していない場合があるからである。以下、本節では一つ目の意味で「決定不能」と書く。特定の形式的体系の下である命題が決定不能であることは、その命題の真理値がwell-definedであるかどうかや他の手段で決定可能かどうかについては明らかにしない。決定不能ということが意味するのは、あくまで使用されている特定の形式的体系の下ではその命題の真偽をいずれも証明できないということにすぎない。真理値を決して知ることができないか、または真理値の定義自体が無効となるような、いわゆる「絶対的決定不能」命題が存在するのかどうかは数理哲学における論争の的となっている。ゲーデルとポール・コーエンの仕事を合わせて、決定不能命題の確かな実例が得られた。連続体仮説はZFC（集合論における標準的な公理系）の下では証明も否定の証明もできない。また、選択公理もZF（ZFCに含まれる公理から選択公理を除いたもの）では証明も否定の証明もできない。これらの結果は不完全性定理を必要としない。1940年、ゲーデルはこれらの命題が何れも ZF または ZFC 集合論では否定を証明できないことを証明した。1960年代、コーエンはこれらがいずれも ZF から証明できず、また連続体仮説が ZFC から証明できないことを証明した。マチャセビッチによるヒルベルトの第10問題によって決定不能な命題の例が得られる。そのような例はディオファントス方程式の外側に存在量化子を幾つか並べた形として得られる。すなわち不完全性定理の前提条件を満たす形式的体系において、解の存在が証明も反証もできないようなディオファントス方程式が存在する。1973年、群論におけるが標準的な集合論では決定不能であることが示された。1977年、パリスとハーリントンは、ラムゼーの定理の一種であるが、一階算術の公理体系であるペアノ算術の下では決定不能だが、より大きな二階算術の体系では真であることを証明できることを証明した。カービーとパリスは後にグッドスタインの定理（自然数の数列に関する命題であり、パリス・ハーリントンの原理よりもいくらか易しい）がペアノ算術では決定不能であることを示した。計算機科学で応用される はペアノ算術では決定不能だが集合論では証明できる。実際、Kruskalの木定理（またはその有限版）は、と呼ばれる数学的哲学に基づいて構築されたもっと強い体系の下でも決定不能である。これに関連し、更に一般的な （2003年）は計算複雑性理論に影響する。グレゴリー・チャイティンはアルゴリズム情報理論における決定不能命題を発見し、その状況下で新たな不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能ないかなる理論においても、どのような数であっても "c" よりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 "c" が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。第1不完全性定理はロビンソン算術を含んでいれば十分である。またω無矛盾性の仮定は単なる無矛盾性の仮定に弱められる（後述）。第2不完全性定理はロビンソン算術にΣ論理式に対する数学的帰納法の公理図式を追加した体系（IΣ）を含んでいれば十分である。ペアノ算術はこれを含むから、ペアノ算術を含む理論は第2不完全性定理の適用範囲である。ゲーデルの定理は無矛盾な理論についてのみ適用できる。一階論理では、"ex falso quodlibet" () により、矛盾した理論 "T" はその言語上の如何なる式であれ証明できてしまい、その中には「"T" は無矛盾である」と主張する式も含まれる。ゲーデルの定理が成り立つのは、飽くまで定理が必要としている仮定を満足するような形式的体系に限られる。全ての公理系がこれらの仮定を満たす訳ではなく、中には自然数論の標準モデルを部分構造として持つようなモデルを持っていてもなお仮定を満たさないような公理系もある。例えば、ユークリッド幾何学の一階公理化理論、実閉体の理論、乗算が全域で可能なことを証明できないような算術理論、これらは何れもゲーデルの定理に必要な仮定を満たさない。要点は、これらの公理系では自然数の集合を定義することや自然数の基本的な性質を証明することができないことにある。三つ目の例に関して Dan E. Willard は第二不完全性定理に必要な仮定を満たさないような様々な弱い算術理論を調べた（例えば Willard 2001）。ゲーデルの定理は実効的に生成された（即ち帰納的可算な）理論についてのみ適用できる。自然数に関する真である文を全て公理とするような理論を考えれば、この理論は無矛盾かつ完全であり、かつペアノ算術を含んでいる。これはゲーデルの定理と矛盾しない。何故ならこの理論は帰納的可算ではないからである。第二不完全性定理が示すのは、ある公理系の無矛盾性はその公理系自身では証明できないということであって、他の無矛盾な公理系からも証明できないとは言っていない。例えば、ペアノ算術の無矛盾性はZFCから証明できるし、算術の理論にεまでの超限帰納法を加えて得られたもある。不完全性定理は「『自然数論を含む帰納的公理化可能な理論が、無矛盾（ω無矛盾）であれば』～」という形の定理である。したがって、自然数論を含まない公理系や、帰納的公理化可能でない理論が完全であっても、不完全性定理とは矛盾しない。真の算術やペアノ算術の無矛盾完全拡大などは無矛盾かつ完全であるが、帰納的公理化可能でない。とくに真の算術は算術的に定義不能である。この結果はタルスキの真理定義不可能性として知られる。プレスバーガー算術は帰納的公理化可能、無矛盾かつ完全である。プレスバーガー算術は加法しか含まない公理系であり、ゲーデル数によるコード化のテクニックを扱えない。そのため、不完全性定理は適用できない。また、実閉体の理論やユークリッド幾何学も完全であり、（直観に反して）算術を含まないため、不完全性定理は適用できない。したがって実閉体の理論は決定可能である。もっと精密にいうと実閉体の理論では量化記号消去が可能である。この事実は数式処理系の実装などに応用されている。なお、群や環の公理などは、「自然数論を含まない帰納的公理化可能かつ無矛盾な公理系」であり、不完全性定理は適用できないが、不完全である。例えば、可換群と非可換群がともに存在することから、健全性定理より、群の公理からは積の可換性は証明も反証もできない。ゲーデルの定理は、数学基礎論のうち、数学の無矛盾性の証明を目標としていたヒルベルト・プログラムには、深刻な影響を与えた。ヒルベルトは公理の適切な設定によって完全かつ無矛盾な体系を達成できると楽観視していたが、第二不完全性定理により、ヒルベルトの計画は頓挫した。上記のような述語論理式を自然数論の体系内に構成し、証明を形式的に進めるために、ゲーデルはゲーデル数化という操作を導入した。自由変数、論理式、証明図などを自然数でコード化し証明可能、反証可能などの概念を数論的関数として表現する。このように、論理式や証明を数学的に表現して数学内に埋め込む上記の手法は、数学そのものを分析する「メタ数学」を、分析すべきの数学の中に写像する技法の先駆けであり、その後数学基礎論や理論計算機科学でよく用いられるようになる。第一不完全性定理の拡張として、証明の定義に、命題の証明より小さな、否定命題の証明が存在しないという性質を追加した上で、前提のω無矛盾性を無矛盾性に弱めた定理がジョン・バークリー・ロッサー (1936年) によって示された。この事実はω矛盾した算術理論を考える場合などにおいて重要となる。なお算術を内包する真である体系（自然数の標準モデルで真である公理に基づく体系）はω無矛盾なので、第1不完全性定理は原型のままでも適用できる。今日ではこちらの無矛盾性のみを仮定する強い定理もゲーデルの不完全性定理と呼ばれるが、単にロッサーの定理、ゲーデル・ロッサーの定理などと呼ばれることもある。第二不完全性定理に関しては、ゲーデルによる証明の定義に代えて、ロッサーによる上記の証明の定義を用いれば、体系自身の無矛盾性が証明できることが、クライゼル (1960) によって指摘されている。2つの証明の定義の同値性は体系内では証明できないため、第2不完全性定理とは矛盾しない。レオン・ヘンキンは、対角化により「Hは証明できる」と同値となる命題H（ヘンキン文）を構成し、その証明可能性に関する問題を1952年に提起した。この問題は3年後の1955年に、マーティン・レーブによって解かれた。彼は、「Hの証明が存在すればHである」が証明可能であれば、Hもまた証明可能であることを示した（レーブの定理）。Hに矛盾を代入すれば、レーブの定理から第二不完全性定理が示せる。不完全性定理は他の論理構造と同じく抽象代数による簡易な表現が可能である。を次のように定義する。T で無条件に証明可能な文 A は，この順序で最小元となり、T で ￢A を証明できるとき、A はこの順序の最大元となる。よって最大元でも最小元でもないものは独立命題のみ。つまり不完全であるためにはリンデンバウム代数の位数は3以上であることが要請される。一方 B を，一階述語論理のリンデンバウム代数とすると、どんな理論のリンデンバウム代数 L についても，あるイデアル I ⊆ B が存在して、L= B/I と表される。よって T が生成するイデアル (T) が T が生み出す定理全体となる。このとき、理論 T のリンデンバウム代数は、剰余代数 B/(T) である。ここでロビンソン算術に対応する B の部分集合を Q とする。このとき、ゲーデルの第一不完全性定理は次のようにして表現される。他に、ザリスキ位相や素スペクトルによる表現が知られている。

出典:wikipedia