高さが無限だが \(\Sigma_1\)-健全でない理論の例

数学における証明と真理―様相論理と数学基礎論―の p.130 において，高さが無限だが \(\Sigma_1\)-健全でない理論の存在を述べたが，ここではそのような理論の例を示しておく．

Iterated consistency statements を定める．

続いて理論の高さを定める（この概念は実は理論に対してではなく，理論の証明可能性述語に対して定められる概念であるが，ここではその違いについては目をつぶることにする）．

証明.
\(T\) を \(\Sigma_1\)-健全とする． 全ての \(n\) について \(T \nvdash \neg {\rm Con}_T^n\) となることを \(n\) に関する帰納法で示す．

• まず \(T\) は無矛盾なので \(T \nvdash \neg 0 = 0\)，すなわち \(T \nvdash \neg {\rm Con}_T^0\) である．
• 続いて \(T \nvdash \neg {\rm Con}_T^n\) とする． \(T \vdash \neg {\rm Con}_T^{n+1}\) とすれば，\(\neg {\rm Con}_T^{n+1}\) は \(\Sigma_1\) 文なので \(T\) の \(\Sigma_1\)-健全性より正しい． つまり \(\neg {\rm Con}_{T + {\rm Con}_T^n}\) は正しい． これは \(T + {\rm Con}_T^n\) が矛盾することを意味するが，帰納法の仮定に反する． したがって \(T \nvdash \neg {\rm Con}_T^{n+1}\) である．

この命題の逆はいえない．

証明.
理論 \(T_0 = {\sf PA} + \{{\rm Con}_{\sf PA}^n : n \in \omega\}\) は \({\sf PA}\) の無矛盾な再帰的拡大理論なので，その \(\Pi_1\) Gödel 文 \(\varphi\) をとれば \(T_0 \nvdash \varphi\) かつ \(\mathbb{N} \models \varphi\) である． ここで \(T : = {\sf PA} + \neg \varphi\) と定めると \(T\) は偽である \(\Sigma_1\) 文 \(\neg \varphi\) を証明するので \(\Sigma_1\)-健全ではない． \(T\) の高さが無限であることを示せばよい． そのために次の主張を示す．

主張.
任意の \(n \in \omega\) について \(T\vdash \neg {\rm Con}_T^n \leftrightarrow \neg {\rm Con}_{\sf PA}^n\).

\(n\) に関する帰納法で示す．

• \(n=0\) の場合は明らか．
• \(T\vdash \neg {\rm Con}_T^n \leftrightarrow \neg {\rm Con}_{\sf PA}^n\) であると仮定する． \({\sf PA} \vdash {\rm Pr}_{T}(\ulcorner \neg {\rm Con}_T^n \urcorner) \leftrightarrow {\rm Pr}_{T}(\ulcorner \neg {\rm Con}_{\sf PA}^n \urcorner)\) である． \(\neg \varphi\) は \(\Sigma_1\) 文なので \({\sf PA} \vdash \neg \varphi \to {\rm Pr}_{\sf PA}(\ulcorner \neg \varphi \urcorner)\) であるから，\(T \vdash {\rm Pr}_{\sf PA}(\ulcorner \neg \varphi \urcorner)\) である． \begin{align*} T \vdash \neg {\rm Con}_T^{n+1} & \leftrightarrow \neg {\rm Con}_{T + {\rm Con}_T^n} \\ & \leftrightarrow {\rm Pr}_T(\ulcorner \neg {\rm Con}_T^n \urcorner)\\ & \leftrightarrow {\rm Pr}_T(\ulcorner \neg {\rm Con}_{\sf PA}^n \urcorner)\\ & \leftrightarrow {\rm Pr}_{{\sf PA} + \neg \varphi}(\ulcorner \neg {\rm Con}_{\sf PA}^n \urcorner)\\ & \leftrightarrow {\rm Pr}_{\sf PA}(\ulcorner \neg \varphi \to \neg {\rm Con}_{\sf PA}^n \urcorner) \\ & \leftrightarrow {\rm Pr}_{\sf PA}(\ulcorner \neg {\rm Con}_{\sf PA}^n \urcorner) \\ & \leftrightarrow \neg {\rm Con}_{\sf PA}^{n+1}. \end{align*}

さて，\(T \vdash \neg {\rm Con}_T^n\) となる \(n\) があったとすると，主張より \(T \vdash \neg {\rm Con}_{\sf PA}^n\)，つまり \({\sf PA} + \neg \varphi \vdash \neg {\rm Con}_{\sf PA}^n\) である． よって \({\sf PA} + {\rm Con}_{\sf PA}^n \vdash \varphi\) なので特に \(T_0 \vdash \varphi\) となり，\(\varphi\) の取り方に反する． したがって，全ての \(n \in \omega\) について \(T \nvdash \neg {\rm Con}_T^n\) である．

2019/05/27