2.25

(i) \(\Rightarrow\) (ii): \(T \vdash \sigma_0 \lor \sigma_1\) とすると,\(\sigma_0 \lor \sigma_1\) は \(\Sigma_1\) なので (i) より \(\sigma_0 \lor \sigma_1\) は true である. よって \(\sigma_0\) もしくは \(\sigma_1\) の少なくとも一方は true である. \(\Sigma_1\)-完全性より \(T \vdash \sigma_0\) または \(T \vdash \sigma_1\) である.

(ii) \(\Rightarrow\) (iii): \(\Sigma_1\) 文 \(\sigma\) が \(\Delta_1^T\) である,つまり \(T \vdash \sigma \leftrightarrow \pi\) となる \(\Pi_1\) 文 \(\pi\) がとれたとする. いま \(T \vdash \sigma \lor \neg \sigma\) なので \(T \vdash \sigma \lor \neg \pi\) である. (ii) より \(T \vdash \sigma\) または \(T \vdash \neg \pi\) なので,\(T \vdash \sigma\) または \(T \vdash \neg \sigma\) となる.

(i) \(\Rightarrow\) (iv):

  • \(\varphi \in {\rm Th}(T)\) とすると \(T \vdash \varphi\) なので \(T \vdash {\rm Pr}(\varphi)\) である.
  • \(T \vdash {\rm Pr}(\varphi)\) とすると (i) より \({\rm Pr}(\varphi)\) は true なので \(T \vdash \varphi\) となる. つまり \(\varphi \in {\rm Th}(T)\) である.

[(iii) or (iv)] \(\Rightarrow\) (i): 対偶を示す. \(T\) が \(\Sigma_1\)-健全でないとする.このとき \(T \vdash \varphi\) であるが \(\neg \varphi\) が true となる \(\Sigma_1\) 文 \(\varphi\) がとれる. \(\varphi = \exists x \delta(x)\) となる PR 論理式 \(\delta(x)\) がとれるとしてよい. \[ {\sf Q} \vdash \sigma \leftrightarrow \exists x (({\rm Prf}(\neg \sigma, x) \lor \delta(x)) \land \forall y \leq x \neg {\rm Prf}(\sigma, y)) \] となる \(\Sigma_1\) 文 \(\sigma\) をとり,\(\Sigma_1\) 文 \(\chi\) を \[ \chi : = \exists y ({\rm Prf}(\sigma, y) \land \forall x < y (\neg {\rm Prf}(\neg \sigma, x) \land \neg \delta(x))) \] と定める. Lemma 1.3 より \(T \vdash \neg \sigma \lor \neg \chi\) かつ \(T \vdash \varphi \to \sigma \lor \chi\) である. \(T \vdash \varphi\) なので \(T \vdash \sigma \lor \chi\) となるため,\(T \vdash \sigma \leftrightarrow \neg \chi\) である. したがって \(\sigma\) は \(\Delta_1^T\) である.

  • \(T \vdash \sigma\) と仮定すると,\(T\) における \(\sigma\) の証明 \(p\) をとれば,\(T \vdash {\rm Prf}(\sigma, p) \land \forall y < p \neg {\rm Prf}(\neg \sigma, y)\) である. また \(T \vdash \forall y < p \neg \delta(y)\) なので \(T \vdash \chi\),つまり \(T \vdash \neg \sigma\) となるのでおかしい. したがって \(T \nvdash \sigma\) である.
  • \(T \vdash \neg \sigma\) と仮定すると,\(T\) における \(\neg \sigma\) の証明 \(q\) をとれば,\(T \nvdash \sigma\) なので \(T \vdash {\rm Prf}(\neg \sigma, q) \land \forall y \leq q \neg {\rm Prf}(\sigma, y)\) となる. したがって \(T \vdash \sigma\) となり矛盾する. つまり \(T \nvdash \neg \sigma\) である.
  • \(\chi\) の取り方より \(T \vdash \chi \to {\rm Pr}(\sigma)\) であるが,\(T \vdash \chi \leftrightarrow \neg \sigma\) なので \(T \vdash \neg \sigma \to {\rm Pr}(\sigma)\) である. \(\sigma\) は \(\Sigma_1\) なので \(T \vdash \sigma \to {\rm Pr}(\sigma)\) となる. したがって \(T \vdash {\rm Pr}(\sigma)\) である.

\(\Delta_1^T\) 文 \(\sigma\) について \(T \nvdash \sigma\) かつ \(T \nvdash \neg \sigma\) なので (iii) ではないことがいえた. また \(T \vdash {\rm Pr}(\sigma)\) かつ \(T \nvdash \sigma\) なので (iv) ではないことも示せた.