第一不完全性定理の概略
「ゲーデルに挑む」田中一之(東京大学出版会)から抜粋、要約します。
1
自然数の変数xを持つすべての論理式を並べあげる。
𝝋1(x),𝝋2(x)・・𝝋n(x)・・
2
「𝝋x(x)は証明不可能である*」という論理式をK(x)とする。すなわちあるkが存在して、
K(x)=𝝋k(x)=(𝝋x(x)≠T’)
(*「𝝋x(x)≠T’」はキンシャチ独自の記法である。Tは「真」T’は「証明可能」)
3
論理式K(x)変数xにkを代入して、G=K(k)とする。
G=K(k)=(𝝋k(k)≠T’)
ここでGは「Gは証明不可能である(G≠T’)」を意味している。
4
真の文のみを証明する健全な形式体系を考えている、と仮定する。つまり任意の自然数yに対して下が成り立つものとする。
(𝝋y(x)=T’)→(𝝋y(x)=T)
このとき
(G=T’)→(G=T)→(G≠T’)→矛盾
(¬G=T’)→(¬G=T)→(G=T’)→形式体系が矛盾
つまり、形式体系が矛盾していない限り、Gと¬Gはどちらも証明不可能である。
否定の文の扱いや、証明がなにを意味するのかなど、あいまいな点もあるけど、わかりやすい。