４． 不完全性定理（第１定理）の証明
神は、”言葉の神”であり、語った言葉を必ず成し遂げられる（イザ５５：１１）。 また、ヒトの大脳皮質の前頭葉には、”意志”と共に”言語”の中枢があり、これらは共同的に作用するので、このことも、ヒトが神様に似せて造られた被造物であることをあかししている。
さて、この言葉というものを形式的に分析すると、理性的に表現される一般的な言葉は論理学的形式に表現でき、様相論理（～と信じる、～するだろう、～しなければならない、など）も含めて、数理論理学的に記号化されすべて表現できるようになる。そして、単純な、命題論理、述語論理は、人間理性から見ても完全である。
一方、数学的思索や階層構造を持つ述語論理においては、自己言及を含まない、たとえば将棋やチェスなどのゲームでは、その規則がいくら複雑でも不完全性は現れないが、無限性や自己言及を含む程度に複雑なシステム（自然数論を含むすべての数学理論はもちろん）においては、永遠に決定不能なパラドックスが容易に発生しうるのである。 言語は記号になり、記号はゲーデル数によって自然数論に還元することができるから、数学のみならず 階層構造（メタ言語）を持つ述語論理にあっても、その不完全性を”自然数論的な方法”によって証明することができる。
（１） 形式的自然数論の構造：
第１階の述語論理とは、個体についてのみ限量を許す論理学である。
この上に構成された形式的数学は、第１階の理論と呼ばれ、（述語）論理学の公理に 数学の公理を追加してつくられる。 「不完全性定理」は、この”第１階の自然数論”で記述するのが普通である。それは、この第１階の理論は、実数論や集合論の概念を全く含まないで構成されているからである。
これらは、次のような手順で行われる。
理論 → 形式化（述語論理） → 述語論理の「完全性」の証明
理論 → 形式化（述語論理）＋数学的公理系 → 帰納的述語と帰納的関数の設定
→ 形式的自然数論（メタ数学）・ゲーデル数の定義 → 自己言及の導入・ゲーデル命題の作成
→ 数学の「不完全性」の証明
１） 数学的帰納法の公理；
有名な ペアノ算術の公理系（1894）は次のようである。
公理１： ０ は自然数である
公理２： ｘ が自然数であれば、ｘ の後続数 ｘ’ も自然数である
公理３： ０ は いかなる自然数の後続数ではない
公理４： 自然数 ｘ の後続数 ｘ’ と自然数 ｙ の後続数 ｙ’が等しいならば、ｘ と ｙ も等しい
公理５： ０ がある性質をもち、かつ、任意の自然数 ｘ がその性質をもつならば ｘ の後続数もその性質をもつ、このことが言えるとき、すべての自然数はその性質をもつ
以上は、日常言語を用いて表現したもので、”０”、”自然数”、”後続数”は ”未定義用語”と呼ばれ、どのように解釈するかは 意味論上の問題となる。（現代数学では、ｘ の後続数を ｘ ＋ １ と解釈するのが普通である。）
公理 ５ は、数学的帰納法の公理を表し、公理１から４までから生み出される対象だけが自然数であり、それ以外は自然数でないと限定するものでもある。
人工言語（タイプ理論）で 公理 ５ を記述すると、
∀Ｐ（Ｐ（０）∧∀ｘ（Ｐ（ｘ）→Ｐ（ｘ’））→∀ｘＰ（ｘ））
ただし、Ｐ： 自然数の性質をあらわす変項
一方、第１階の理論として構成された 自然数論の形式的体系 Ｎ については、
Ｎ の言語は、ただ一つの個体記号 ０ と、 ３つの関数記号 ’ 、＋ 、 ・ と、ただ一つの述語記号 ＝ をもつ。
Ｎ の数学的公理は、次のように記述される。
Ｎ１： ｘ’ ≠ ０ Ｎ２： ｘ’ ＝ ｙ’ → ｘ ＝ ｙ Ｎ３： ｘ ＋ ０ ＝ ｘ
Ｎ４： ｘ ＋ ｙ’ ＝ （ｘ ＋ ｙ）’ Ｎ５： ｘ ・ ０ ＝ ０ Ｎ６： ｘ ・ ｙ’ ＝ ｘ ・ ｙ ＋ ｘ
Ｎ７： Ａ〔０〕 ∧ ∀ｘ （Ａ〔ｘ〕 → Ａ〔ｘ’〕） → ∀ｘ Ａ〔ｘ〕
ただし、Ａ： 任意の式を表す構文論的変項
Ｎ７ が、数学的帰納法の公理になっている。
ペアノの公理５ が単独の式で表されているのに対し、Ｎ７ は図式になっている。
第１階の自然数論（これを、単に、自然数論と呼ぶ）は、実数概念や集合概念を含まない、最も初等的な自然数論の体系であり、ペアノの自然数論よりも弱い体系である。
２） ゲーデル数の定義；
次のような規則によって、あらゆる述語記号をそれぞれ異なる独立した自然数に数値化することができる。したがって、逆に、この数値化によって、あらゆる言語や数学を自然数論の”帰納的な論法”に変換することができる。（これは、（２）の証明で効果的に用いられる）
１． Ｎ の記号 ｅ のゲーデル数；
（～ は否定、∀ は全称、 ’ は 後者の意） Ｎ番目の個体変項のゲーデル数は ２３＋２・（ｎ－１）
２． Ｎ の記号列 Ｅ ＝ ｅ１ ｅ２ ・・・・・ ｅｎ のゲーデル数；
ただし、Ｐｉ は ２、３、５、７、１１、・・・・ （素数）記号のゲーデル数を 素数列の冪に入れ すべて掛合せる。
たとえば、式 ｘ ≠ ｙ すなわち、 ～＝（ｘ、ｙ） のゲーデル数は、
項 ｘ ＋ ｚ すなわち、 ＋（ｘ、ｚ） のゲーデル数は、
など。３． Ｎ の記号列の列 Ｅ１、Ｅ２、・・・・・、Ｅｎ のゲーデル数；
さらに、記号列のゲーデル数を素数列の冪に入れ掛合せる。
素因数分解の一意性から、すべての記号、記号列、記号列の列に、それぞれ異なるゲーデル数が １：１ に対応するので、数字だけですべての記述を区別して認識することができる。 少なくとも原理的には、ゲーデル数が与えられると、もとの記号論理に解読できることになる。素数暗号の原理。ただし、ゲーデル数は非常に大きい数になる。たとえば、”証明のゲーデル数”は ある証明の長い記号列をゲーデル数化するから おそろしく大きい数になるが、確かに一つの”存在する”自然数である。
３） 不完全性が現れるしくみ：
自然数論は上下方向に、”無限”の概念を含む。この無限性を、有限の方法で矛盾なく公理系に収めるために、ペアノの第５公理や第１階の自然数論の Ｎ７ のような 帰納的な定義や帰納法による証明を導入しなければならなかった。
その上で、たとえば 命題自身のゲーデル数を その命題の変数に代入するといった、”自己言及”（あるいは、相互言及）を含むように命題を設定する。すると、”うそつきのパラドックス”、”抜き打ちテストのパラドックス”と同様に、証明も反証もできない決定不能な命題（ゲーデル命題）が構成されるのである。つまり、その数学理論は「不完全」ということになる。
（２） 不完全性定理の証明：
では、実際にゲーデルが行った不完全性定理の証明を詳しく見てみよう。（多少、記号を簡略化しています）
次のような命題が成立する。
Ｗ（ｘ、ｙ）： 「 ｘ は、一つの自由変項をもつ述語 Ｗｘ（ｔ） のゲーデル数であり、 ｙ は、閉述語 Ｗｘ（ｘ） の証明のゲーデル数である。」
（この命題が数論の形式的述語ですべて記述することができることを示す長い証明は省略する。この自然数論の命題 Ｗ は、原始帰納的（＝再帰的述語の一つ）である。）
ここで、 Ｇ（ｔ） ＝ ～∃ｙ Ｗ（ｔ、ｙ） （（注） ～∃ｙ Ｗ は、∀ｙ ～Ｗ と同じ）
： 「一つの自由変項をもつ述語 Ｗｔ（ｚ） のゲーデル数を ｔ とすると、いかなる数 ｙ も 閉述語 Ｗｔ（ｔ） の証明のゲーデル数とはならない。」
という命題をつくる。
この Ｇ（ｔ） 自身も、１変項 ｔ のみを自由変項としてもつ命題だから、なんらかのゲーデル数 ｑ をもつ。（すなわち、Ｇ（ｔ） ＝ Ｗｑ（ｔ） ）
この特定の定数 ｑ を代入して得られる閉述語、（＊ ここに、”自己言及”を含ませていることに注意！）
Ｇ（ｑ） ＝ ～∃ｙ Ｗ（ｑ、ｙ）
が、①証明も、②反証もできない決定不能の”ゲーデル命題”になっていることを示す。（①、②とも、背理法で証明する）
① Ｇ（ｑ） が証明できないことについて；
もし、Ｇ（ｑ） の証明が存在するならば、
Ｇ（ｑ）自身の証明のゲーデル数 ｒ が存在して、Ｗ（ｘ、ｙ） の定義より、命題 Ｗ（ｑ、ｒ）が成立する。
よって、Ｗ（ｑ、ｙ） を成立させる ｙ が存在することになる。
このことは、 Ｇ（ｑ） ＝ ～∃ｙ Ｗ（ｑ、ｙ） 、すなわち、いかなる数 ｙ も Ｗ の証明のゲーデル数にならないという、この命題自身の主張と矛盾する。
② Ｇ（ｑ） が反証できないこと（＝ ～Ｇ（ｑ） が証明できないこと）について；
～Ｇ（ｑ） ＝ ∃ｙ Ｗ（ｑ、ｙ） が 真であると仮定するならば、
①より、 Ｇ（ｑ） が証明不能であることは 真 であるから、ここで、
ω無矛盾： ～Ｑ（０）、～Ｑ（１）、～Ｑ（２）、・・・ という命題全体と、∃ｙ Ｑ（ｙ） という命題が、同時に 真 となることはない、 を仮定すると、
Ｗ（ｑ、０）、Ｗ（ｑ、１）、Ｗ（ｑ、２）、・・・ は すべて 偽 となって、どのような自然数も その証明のゲーデル数にはなり得ないということになる。
したがって、 ∃ｙ Ｗ（ｑ、ｙ） は 偽 となって、これが 真 であるという仮定に反する。
（証明終）
①、②をまとめると、 Ｎ： 自然数論の公理系 （可付番で無限性をもち（＝ 帰納的で）、自己言及・相互言及を含みうる程度に複雑な理論・システムならば何でもよい）として、
① Ｎ が無矛盾であれば、Ｇ は Ｎ で証明可能ではない
② Ｎ が ω無矛盾であれば、～Ｇ は Ｎ で証明可能ではない
・・・・・・ ゲーデルの第１不完全性定理（1931）
この 公理系の ω無矛盾の仮定は、Ｊ．Ｂ．ロッサーによって、
単純無矛盾： ∃ｙ Ｑ（ｙ） と ～∃ｙ Ｑ（ｙ） とは、同時に真とはなり得ない、に拡張され（1936）、現在、単に”不完全性定理”と呼ばれるものはこれを指す。
したがって、ある数学理論の公理系が無矛盾ならば、その公理系は不完全、すなわち、その閉じた理論内部では証明も反証もできないゲーデル命題が存在することになる。
また、第２不完全性定理より、公理系が無矛盾ならば、その公理系自身の無矛盾性をその公理系から証明できない。
・ 第１不完全性定理：
① Ｎ が無矛盾であるならば、 Ｒ は Ｎ で証明可能ではない
② Ｎ が無矛盾であるならば、 ～Ｒ は Ｎ で証明可能ではない
ここで、
数論的述語 Ｗ、Ｗ* ： Ｗ（ａ、ｂ） ⇔ Ｐｆ （ｂ、Ｓｕｂ（ａ、２３、Ｎｕｍ（ａ）））
Ｗ*（ａ、ｂ） ⇔ Ｐｆ （ｂ、Ｓｕｂ（２17*ａ、２３、Ｎｕｍ（ａ）））
Ｓｕｂ（ａ、ｂ、ｃ）： ゲーデル数 ａ の記号列の中に自由変項として現れるゲーデル数 ｂ の
個体変項に、ゲーデル数 ｃ の項を代入して得られる記号列のゲーデル数
Num（ａ）： 数記号ａ-のゲーデル数
Ｗ、Ｗ* を表現する式 Ｗ、Ｗ* の自由変項はそれぞれ ｘ、ｙ とする
・ 第２不完全性定理：
Ｎ が無矛盾であるならば、 Ｃｏｎｓｉｓ はＮで証明可能ではない
ここで、
※ 第２不完全性定理から、その逆もまた成立する。すなわち、公理系に矛盾が含まれるならば、１） その公理系からどんな命題でも証明でき、さらに、２） 公理系自体も無矛盾であるという主張も証明できる、という皮肉なことが知られている！ （ → ６．（１）、 ７．（２） ）
第１定理、第２定理の対偶をとると、
１． Ａ → ～Ｂ ：無矛盾ならば不完全 ⇔ Ｂ → ～Ａ ：もし結果が完全であるならば、公理系は矛盾している
２． Ａ → ～Ｃ ：無矛盾ならば、その無矛盾性を証明できない
⇔ Ｃ → ～Ａ ：無矛盾であることを証明できたならば、公理系は矛盾を含む
・・・ 完全（証明できないことが無い）かつ無矛盾な結果をもたらす神は、その内部が論理的に矛盾していて当然（三位一体、１＋１＋１＝１）