人気ブログランキング | 話題のタグを見る

第一不完全性定理の概略

「ゲーデルに挑む」田中一之(東京大学出版会)から抜粋、要約します。


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はどちらも証明不可能である。


否定の文の扱いや、証明がなにを意味するのかなど、あいまいな点もあるけど、わかりやすい。


by tomoarrow | 2019-07-15 07:00 | モチーフについて | Comments(0)