(a)
\(\tau(x)\) を，\(\mathbb{N}-{\rm Th}(U)\) を \(U\) において numerate する論理式とする．
\( \begin{eqnarray*} {\sf Q} \vdash \varphi \leftrightarrow \tau(\varphi) \end{eqnarray*} \)
を満たす文 \(\varphi\) をとれば，\(U\) は \({\sf Q}\) の拡大なので，この同値性は \(U\) においても成り立つ． このとき，
\( \begin{align*} U \nvdash \varphi & \Leftrightarrow \varphi \notin {\rm Th}(U)\\ & \Leftrightarrow \varphi \in \mathbb{N}-{\rm Th}(U)\\ & \Leftrightarrow U \vdash \tau(\varphi)\\
& \Leftrightarrow U \vdash \varphi. \end{align*} \)
よって矛盾する． したがってそのような論理式 \(\tau(x)\) は存在しない．
(b)
\(U\) を \(U\) において binumerate する論理式を \(\nu(x)\) とする．
\( \begin{eqnarray*} U \vdash \psi \leftrightarrow \neg {\rm Pr}_\nu(\psi) \end{eqnarray*} \)
を満たす文 \(\psi\) をとる．
- \(U \vdash \psi\) と仮定する． \(U\) における \(\psi\) の証明 \(p\) をとれば，Fact 1.7(a) より \(U \vdash {\rm Prf}_\nu(\psi,p)\) なので \(U \vdash {\rm Pr}_\nu(\psi)\) である． \(\psi\) の取り方より \(U \vdash \neg \psi\)
となり矛盾．
- \(U \vdash \neg \psi\) と仮定すると，\(\psi\) の取り方より \(U \vdash {\rm Pr}_\nu(\psi)\) となる． \(U\) は true なので \(\mathbb{N} \models {\rm Pr}_\nu(\psi)\) となる． 一方 \(U\) は無矛盾なので \(U \nvdash \psi\)
であるから，任意の \(q\) について \(q\) は \(U\) における \(\psi\) の証明ではない． Fact 1.7(d) より \(U \vdash \neg {\rm Prf}_\nu(\psi, q)\) である． \(U\) は true なので \(\mathbb{N} \models \neg {\rm Prf}_\nu(\psi, q)\) となる． ここで
\(q\) は任意なので \(\mathbb{N} \models \forall y \neg {\rm Prf}_\nu(\psi, y)\) つまり \(\mathbb{N} \models \neg {\rm Pr}_\nu(\psi)\) となり矛盾する．
したがって \(U \nvdash \psi\) かつ \(U \nvdash \neg \psi\) であり，\(U\) は完全でない．
コメント
(b) における "\(U\) は true" という仮定は次のようにして単に "\(U\) は無矛盾" に落とすことができる．
\(U\) を \(U\) において binumerate する論理式を \(\nu(x)\) とする．
\( \begin{align*} U \vdash \psi \leftrightarrow \forall y({\rm Prf}_\nu(\psi,y) \rightarrow \exists z \leq y {\rm Prf}_\nu(\neg \psi,z)) \end{align*} \)
を満たす文 \(\psi\) をとる．
- \(U \vdash \psi\) と仮定すると，\(U\) は無矛盾なので \(U \nvdash \neg \psi\)． \(U\) における \(\psi\) の証明 \(p\) をとれば，Fact 1.7(a)(d) より \(U \vdash {\rm Prf}_\nu(\psi,p)\) かつ \(U \vdash \forall z \leq p \neg
{\rm Prf}_\nu(\neg \psi,z)\). よって \(U \vdash \neg \psi\) となり矛盾．
- \(U \vdash \neg \psi\) と仮定すると，\(U\) は無矛盾なので \(U \nvdash \psi\)． \(U\) における \(\neg \psi\) の証明 \(q\) をとれば，Fact 1.7(a) より \(U \vdash {\rm Prf}_\nu(\neg \psi,q)\) なので，\(U \vdash \forall y(y>q
\rightarrow \exists z \leq y{\rm Prf}_\nu(\neg \psi,z))\)． 一方 Fact 1.7(d) より \(U \vdash \forall y({\rm Prf}_\nu(\psi,y) \rightarrow y>q)\). よって \(U \vdash \forall y({\rm Prf}_\nu(\psi,y)
\rightarrow \exists z \leq y {\rm Prf}_\nu(\neg \psi,z))\) なので \(U \vdash \psi\) となり矛盾．
したがって \(U \nvdash \psi\) かつ \(U \nvdash \neg \psi\) であり，\(U\) は完全でない．