今回は、ゲーデル の不完全性定理を概説する。

　
1. ω-完全と ω-無矛盾

　形式的言語 L のなかで自然数 n を考え、Sⁿ0は、記号 0 の前に S を n 個、置いた記述である、とする。

（1） ω-完全

　「ω-完全」 とは、L の式 A (x) があれば、タイプ N において、以下が成立することをいう。

　　　　　　任意の自然数 n について、A (Sⁿ0） は、N において トートロジー ならば、
　　　　　　∀_{x ∈ N} A (x) は、N において トートロジー である。

（2） ω-無矛盾

　「ω-無矛盾」 とは、形式的言語 L の式 A (x) において、以下が成立することをいう。

　　　　　　任意の自然数 n について、A (Sⁿ0） は、N において証明可能ならば、
　　　　　　¬∀_{y ∈ N} A (y) は、N において証明可能ではない。

　
2. 不完全性定理

　不完全性定理 （1931年） の正式名称は、「『プリンシピア・マセマティカ』 や、その関連体系の形式的に決定不可能な命題について」 という。不完全性定理は、以下のように 2つの 「解釈 （意味論および構文論）」 が成立する。

（1） 意味論

　形式的言語 L が無矛盾であれば、L のなかの式について、どのような ω-完全な モデル においても真であるのに、L のなかでは証明できない式がある。

（2） 構文論

　L が ω-無矛盾であれば、L のなかの式 G について、G も ¬G も L のなかでは証明できない。

　
3. 決定不能

　G も ¬G も証明できないなら、L において 「決定不能」 である、という。

　
4. 不完全性定理の証明概観

　以下に記述する手順は、ゲーデル の論文のなかで、論文の最初に記述されている 「証明の概観」 を、若干、変更している。なお、ゲーデル の原文は、以下の文献を参照した。
　Kurt Godel, "Some metamathematical results on completeness and consistency, On formally undecidable propositions of Principia mathematica and related system I, and On completeness and consistency (1930b, 1931 and 1931a)", edited by Jean van Heijenoort, UMI, 1970.

（1） 形式的体系は原始記号の有限列である。証明も、形式的な見かたをすれば、論理式の有限列である。

（2） 原始記号に対して自然数を対応する。
　　ゲーデル の論文では、体系 P （PM の公理系に対して ペアノ の公理系を付加して得られる公理系） の原始記号に対して、自然数 13 よりも小さな素数 （1, 3, 5, 7, 9, 11, 13） を 1対1 に対応させて、タイプ N の変数として、pⁿ（p は 13 よりも大きな素数） という自然数を対応させている。
　　このように、素数を使って割り当てられた数を ゲーデル 数という。
　　（以後、ゲーデル 数を自然数として記述する。）

（3） 論理式は自然数の有限列になる。証明は 「『自然数の有限列』 の有限列」 になる。

（4） PM のなかに、1つの自由変数 v をもつ論理式 F (v) を作る。
　　F (v) は「v は証明可能な論理式である」 ことを意味する。

（5） PM のなかに、A も ¬A も証明できない命題 A を作る。
　　（5）-1 単項述語記号を導入する。
　　　単項述語記号とは、変数が自然数の タイプ であるような 1つの自由変数をもつ論理式のことをいう。
　　（5）-2 単項述語記号を、すべて、一列に並べる。n 番目を R (n) とする。

（6） a を任意の単項述語記号とする。

（7） [ a; n ] を考える。
　　つまり、単項述語記号 a の自由変数を ゲーデル 数で置換した論理式である。

（8） 自然数の集合 K を定義する。
　　（8）-1 n ∈ K ⇒ ¬Bew [ R (n); n ].
　　（8）-2 ¬Bew [ R (n); n ] ⇒ n ∈ K.
　（ Bew (x) は、「x は証明可能な論理式である」 ことを意味する。）

（9） K も PM のなかに作ることができる。

（10） 論理式 [ S; n ] を考える。
　　すなわち、自然数 n が K に属しているような単項述語記号 S が存在する。
　　S は単項述語記号であるから、どれかの R (q) と同じである [ S ＝ R (q) ]。

　さて、以上の前提を整えたならば--以上の 「着想」 は、到底、われわれ凡人には思い浮かぶことができないし、ゲーデル が、以上の 「着想」 を整えることができたから、天才といわれる所以である（！）--、証明自体は、以下のように単純明快である。

（11） [ R (q); q ] が証明可能なら 「真」 となる。
　　しかし、q は K に属していて、¬Bew [ R (q); q ] が成立することになって、証明不能となる （前提に反する）。

（12） ¬[ R (q); q ] が証明可能なら-- 「¬(q ∈ K) 」 となるから--、Bew[ R (q); q ] が成立する （前提に反する）。

　したがって、[ R (q); q ] は PM において決定不能である。

　
5. 不完全定理の他の証明法 （ゲーデル 以後）

　ゲーデル の不完全性定理が公にされたのは 1931年である。
　70年ほど前の証明であるから、ゲーデル が証明した以後、ほかの証明法も提示されている （そして、以後のやりかたは、当然、エレガント な証明になっている。）

　小生 （佐藤正美） は数学の門外漢なので、ゲーデル 以後の証明を、すべて、知っている訳ではない。
　小生は、たまたま、他の証明法として知り得たやりかたとして、「タルスキー の定理」 が好きである。
　タルスキー の定理：

　　　　　　　代入関数をもつ整合的な理論では、真理関数は存在しない。

　さて、タルスキー の証明については、「読書案内」 のなかで紹介した文献を読んでください。

　小生は、ゲーデル の （不完全性定理の） 論文を読み返すたびに、天才の 「着想」 に対して敬意を抱き、ただただ、（天才の ゲーデル に対する） 驚嘆と （振り返って、凡夫の我が身に対する） 溜息が出るばかりである、、、。□