2.5

(a)
\(Y\) は r.e. なので，\(Y\) の元を全て \(\eta_0(x), \eta_1(x), \cdots, \eta_n(x), \cdots\) と effective に枚挙することができる．

\(X: = \{n \in \mathbb{N} : T \vdash \neg \eta_n(n)\}\)

とする．

\(X\) が再帰的集合であることを示す． \(n \in \mathbb{N}\) に対して，まず \(\eta_n(x)\) を求める． \(Y\) の元は \(T\) において decidable なので，\(T \vdash \eta_n(n)\) もしくは \(T \vdash \neg \eta_n(n)\) である．したがって，\(T\) における証明をゲーデル数の小さい順に調べていけば，\(\eta_n(n)\) の証明か \(\neg \eta_n(n)\) の証明のどちらかに有限回でたどり着く． \(T \vdash \eta_n(n)\) のとき \(n \notin X\) であり，\(T \vdash \neg \eta_n(n)\) のとき \(n \in X\) であるから，\(n \in X\) かどうかは effective に判定できる．したがって \(X\) は再帰的集合である．
全ての \(n\) について，\(\eta_n(x)\) は \(T\) において \(X\) を binumerate しないことを示す．
- \(n \in X\) のとき，\(X\) の定義により \(T \vdash \neg \eta_n(n)\) であるから，\(T \nvdash \eta_n(n)\) となり，\(\eta_n(x)\) は \(T\) において \(X\) を binumerate しない．
- \(n \notin X\) のとき，\(X\) の定義により \(T \nvdash \neg \eta_n(n)\) なので \(\eta_n(x)\) は \(T\) において \(X\) を binumerate しない．

以上より，\(X\) は \(Y\) のどんな元によっても \(T\) において binumerate されない再帰的集合である．

(b)
\(\varphi(x)\) を \(\Delta_1\) 論理式とすると，ある \(\Sigma_1\) 論理式 \(\sigma(x)\) と \(\Pi_1\) 論理式 \(\pi(x)\) が存在して，\({\sf PA} \vdash \forall x(\varphi(x) \leftrightarrow \sigma(x))\) かつ \({\sf PA} \vdash \forall x(\varphi(x) \leftrightarrow \pi(x))\) となる． \({\sf PA}\) の健全性より，これらの同値性は \(\mathbb{N}\) においても真である．

\(\varphi(n)\) が真ならば， \(\sigma(n)\) も真であり，\(\Sigma_1\)-完全性より \({\sf PA} \vdash \sigma(n)\) を得る．同値性より \({\sf PA} \vdash \varphi(n)\) つまり \(T \vdash \varphi(n)\) である．
\(\varphi(n)\) が偽ならば， \(\neg \pi(n)\) は真であり，\(\Sigma_1\)-完全性より \({\sf PA} \vdash \neg \pi(n)\) となる．したがって \({\sf PA} \vdash \neg \varphi(n)\) つまり \(T \vdash \neg \varphi(n)\) である．

以上より，任意の \(\Delta_1\) 論理式は \(T\) において decidable である．

\(Y\) を１変数 \(\Delta_1\) 論理式全体の集合とする．このとき任意の論理式 \(\varphi(x)\) に対して，

\(\varphi(x) \in Y \Leftrightarrow \exists \eta(x)\): \(\Sigma_1\) 論理式 \(\exists \pi(x)\): \(\Pi_1\) 論理式 s.t. \({\sf PA} \vdash \forall x(\varphi(x) \leftrightarrow \sigma(x))\) かつ \({\sf PA} \vdash \forall x(\varphi(x) \leftrightarrow \pi(x))\)

なので \(Y\) は r.e. である．したがって \(Y\) は decidable な論理式の r.e. 集合なので，2.5(a) より \(Y\) のどの論理式にも \(T\) において binumerate されない再帰的集合 \(X\) が存在する．つまり \(X\) はどんな \(\Delta_1\) によっても \(T\) において binumerate されない．

(c)
\(\xi(x)\) を \(T\) において provably decidable な論理式とする．各 \(n \in \mathbb{N}\) に対して \(T \vdash {\rm Pr}(\xi(n)) \lor {\rm Pr}(\neg \xi(n))\) であり，\(T\) は \(\Sigma_1\)-健全なので，\({\rm Pr}(\xi(n))\) もしくは \({\rm Pr}(\neg \xi(n))\) は true である．つまり \(T \vdash \xi(n)\) または \(T \vdash \neg \xi(n)\) が成り立つ．したがって \(T\) において provably decidable な論理式は \(T\) において decidable である．

\(Z\) を \(T\) において provably decidable な \(1\) 変数論理式全体の集合とする．

\(\xi(x) \in Z \iff T \vdash \forall x ({\rm Pr}(\xi(\dot{x})) \lor {\rm Pr}(\neg \xi(\dot{x})))\)

なので \(Z\) は r.e. である．

つまり 2.5(a) より \(Z\) の元によって binumerate されない再帰的集合 \(X\) がとれる．すなわち \(X\) は \(T\) における provably decidable な論理式によって binumerate できない再帰的集合である．

\(X\) を \({\sf Q}\) において binumerate する \(\Sigma_1\) 論理式 \(\psi(x)\) をとれば，\(X\) の取り方より \(\psi(x)\) は \(T\) において provably decidable ではない．

\(\varphi(x)\) が \(\Delta_1\) ならば，\(T \vdash \forall x(\varphi(x) \leftrightarrow \sigma(x))\) かつ \(T \vdash \forall x(\varphi(x) \leftrightarrow \pi(x))\) となる \(\Sigma_1\) 論理式 \(\sigma(x)\) と \(\Pi_1\) 論理式 \(\pi(x)\) がとれる．

\(\begin{align*} T \vdash \neg {\rm Pr}(\varphi(\dot{x})) & \to \neg {\rm Pr}(\sigma(\dot{x})) \\ & \to \neg \sigma(x) \tag{形式化された \(\Sigma_1\)-完全性}\\ & \to \neg \pi(x) \\ & \to {\rm Pr}(\neg \pi(\dot{x})) \tag{形式化された \(\Sigma_1\)-完全性}\\ & \to {\rm Pr}(\neg \varphi(\dot{x})) \end{align*}\)

なので \(\varphi(x)\) は \(T\) において provably decidable である（つまり 2.5(c) は 2.5(b) より強い）．

2.5

コメント