Gödelの第1不完全性定理の使い方
目的と手段が入れ替わってあんまり使うという意識が無い.
理論$ TがRobinson算術$ \mathsf{Q}の$ \Sigma_1健全な(無矛盾な)計算可能拡大理論であるとき,ある文$ Gが存在して$ T \not\vdash Gかつ$ T \not\vdash \lnot G,すなわち$ Tは不完全である. 計算可能拡大から更に,計算的枚挙可能拡大にまで条件を緩めることも出来る.
逆に言えば,ある理論$ Uが完全であるときは,$ Uは$ \mathsf{Q}の$ \Sigma_1健全な計算可能拡大理論ではない.
$ Uは$ \mathsf{Q}の拡大ですらない.
$ Uは$ \mathsf{Q}の$ \Sigma_1健全な拡大であるが,計算可能拡大ではない.
$ Uは$ \mathsf{Q}の$ \Sigma_1健全な拡大であるが,計算可能拡大ではない.パターン
真の算術$ \mathsf{TA} \coloneqq \{ \varphi \in \mathrm{Sent} \mid \N \models \varphi \}とする 自明に$ \mathsf{TA}は$ \mathsf{Q}の無矛盾な拡大理論であって完全である.
よって$ \mathsf{TA}は計算可能拡大ではない.
$ \models \varphiかどうかは計算可能ではない.
より緩めれば,$ \mathsf{TA}は計算的枚挙可能拡大ですらない.
$ \models \varphiとなる$ \varphiを列挙することでも出来ない.
$ Uは$ \mathsf{Q}の拡大ですらない.