ゲーデルの第1不完全性定理を証明する際、多くの教科書では「かくかくしかじかな体系がω無矛盾である(したがって無矛盾でもある)」ということを仮定して、「そのとき、こういう文Gについて、\(\vdash G\)でも\(\vdash \neg G\)でもない」ということを導いている。
このこと自体になんの問題もないのだが、オブジェクトの体系が矛盾やω矛盾をはらむことは、メタレベルから見れば「コップの中の嵐」に過ぎないわけで、あまり当然のように「体系が無矛盾ならば」といった仮定を置くと、メタレベルでの矛盾と混同したり、その仮定そのものを忘れそうになったりして、私は混乱した。
まず基本的なこととして、
「『\(\vdash G\)』であり、しかも『\(\vdash \neg G\)』でもある」(体系が矛盾する)とか、
「『\(\vdash G\)』でなく、しかも『\(\vdash \neg G\)』でもない」(Gが決定不能)ということはありうるが、
「『\(\vdash G\)』であり、しかも『\(\vdash G\)』でない」とか、
「『\(\vdash G\)』であるともないとも、どちらでもない」いうことはありえない。どちらなのか(僕らには)分からない、ということはあっても、どちらか一方のはずである……いや、もちろん「そういうこともありうる」という世界で考えるのは自由かもしれないが、いまはそうではない世界で考えている。以下では「『\(\vdash G\)』でない」を「\(\nvdash G\)」と書く。
ゲーデル文Gに対して考慮すべきケースは、
\(G\)についての「\(\vdash G\)か\(\nvdash G\)か」と
\(\neg G\)についての「「\(\vdash \neg G\)か\(\nvdash \neg G\)か」という、
2×2=4通りの場合だけである。
そこで、これらの各々の場合にどんなことが起こるのか、体系に対して余計な仮定を置かずに淡々と場合分けして調べてゆくほうが分かりやすいのではないか、と感じた。
\(\vdash\neg G\) | \(\nvdash\neg G\) | |
\(\vdash G\) | (1)体系が矛盾 | (2) |
\(\nvdash G\) | (3) | (4)Gが決定不能 |
第1不完全性定理の証明は、(2)の場合が起こりえない――つまり、\(\vdash G\)と\(\nvdash\neg G\)とがメタレベルで矛盾する――ということと、
(3)の場合には体系がω矛盾をきたす、ということの証明の2本立てである。
\(\vdash\neg G\) | \(\nvdash\neg G\) | |
\(\vdash G\) | (1)体系が矛盾 | (2)起こり得ない |
\(\nvdash G\) | (3)体系がω矛盾 | (4)Gが決定不能 |
この表を完成させたうえで、結論を好きなように言い換えればよい。例えば体系がω無矛盾なら無矛盾でもあるので、(4)の場合しか残らず、Gが決定不能となる。