13/10/19 19:02:39.88
不完全性定理って対角線論法じゃなくても証明できるよ
ＺＦＣのモデルの集合の連鎖から背理法でやるＷｏｏｄｉｎの第二不完全性定理証明とか
そこから完全性定理で第一を証明したりＰＡとかもっと弱い理論の不完全性も証明できる
また計算論で再帰的分離不能定理から系として証明されたり、
ブーロスの関数だけで証明するものとか（証明が簡単になるってわけじゃないけど）
一方限定算術で理論で理論を解釈してＰＡより弱い理論の不完全性を示すとか
このスレでも以前話題になったけど不完全性が成り立つにはその論理式Ａについて
Ａのゲーデル数＜2＾(Ａの論理式の長さ)
が成り立たなければならないとかx^(logy)オーダーの関数が入ってる必要があるとか
それに四則演算が入っててもウィラードの算術体系みたいな不完全性が証明できないものがある
無矛盾の話はもし的外れなら無視してもらっていいけど
言語はL＝｛∧、∨、→、￢、Ｒ｝のような集合で
記号列がその組み合わせ列でP(L)＝｛φ、∧、∧→、R￢、R∨R、・・・｝
ここで論理式を再帰的に定義して
論理式はその部分集合でF＝｛A∈P(L)｜Aは論理式｝
そしてある証明体系Hを設定したら
Th＝｛A∈F｜AはHで証明可能｝
このとき
あるB∈Fについて、
B∈Thかつ￢B∈Thが成り立つ ⇔ Hは矛盾
みたいなことが集合論とか計算論の本で出てくる典型的な導入だけど非常に簡潔だと思う