09/02/05 20:50:03
「証明できることが証明できる」のは
「証明できる」ことのとほぼ同じだよね。
ただ「証明できることの証明」は証明よりも弱いよね。
「φの証明が存在する」をコード化した算術の命題をProv(φ)とする。
定理 T |- Prov(Prov(φ)) ⇔ T |- Prov(φ)
証明 （←）derivability conditionの一番
D1:T |- φ → T |- Prov(φ)
より従う。
（→）Löbの定理から T |- φ⇔ T |- Prov(φ)→φ
このφにProv(φ)を代入すれば良い。
なおLöbの定理から、
T |- Prov(Prov(φ))→Prov(φ) は一般に言えないことが分かる。
T から証明できない命題G_Tや￢Prov(0≠0)が反例になっている。