\(\Delta_n\)-定義可能だが \(\Delta_n({\sf PA})\)-定義可能でない集合

以降，\(\Gamma\) を論理式の集合とする． 自然数の集合 \(X\) が \(\Gamma\)-定義可能であるとは，\(X\) が \(\mathbb{N}\) においてある \(\Gamma\) 論理式によって定義されること，すわなち，ある \(\Gamma\) 論理式 \(\varphi(x)\) が存在して，任意の \(k \in \omega\) について \[ k \in X \iff \mathbb{N} \models \varphi(k) \] となることとする．

論理式の集合 \(\Delta_n\) と \(\Delta_n({\sf PA})\) を次で定める．

• \(\Delta_n = \{\varphi \mid \varphi\) は \(\mathbb{N}\) 上である \(\Sigma_n\) 論理式と \(\Pi_n\) 論理式の両方と同値\(\}\)
• \(\Delta_n({\sf PA}) = \{\varphi \mid \varphi\) は \({\sf PA}\) 上である \(\Sigma_n\) 論理式と \(\Pi_n\) 論理式の両方と同値\(\}\)

証明.
\(T = {\sf PA} + {\rm Th}_{\Sigma_n}(\mathbb{N})\) とすると， \(T\) と \({\rm Th}(T)\) は \(\Sigma_n\)-定義可能である．

\(\varphi(x)\) を１変数 \(\Delta_n({\sf PA})\) 論理式とすると，ある \(\Sigma_n\) 論理式 \(\sigma(x)\) と \(\Pi_n\) 論理式 \(\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}\) においても真である．

• \(\mathbb{N} \models \varphi(k)\) ならば，\(\mathbb{N} \models \sigma(k)\) であり，\(T \vdash \sigma(k)\) を得る． 同値性より \(T \vdash \varphi(k)\) である．
• \(\mathbb{N} \models \neg \varphi(k)\) ならば， \(\mathbb{N} \models \neg \pi(k)\) であり，\(T \vdash \neg \pi(k)\) となる．したがって \(T \vdash \neg \varphi(k)\) である．

以上より，任意の１変数 \(\Delta_n({\sf PA})\) 論理式は \(T\) において決定可能である．

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

なので \(Y\) は r.e. である． したがって \(Y\) の元を全て \(\eta_0(x), \eta_1(x), \cdots, \eta_k(x), \cdots\) と effective に枚挙することができる． \[ X = \{k \in \mathbb{N} \mid T \vdash \neg \eta_k(k)\} \] とする．

\(X\) が \(\Delta_n\)-定義可能であることを示す． \(k \in \mathbb{N}\) に対して，まず \(\neg \eta_k(x)\) を計算する．

• \(k \in X \iff \neg \eta_k(k) \in {\rm Th}(T)\) なので \(X\) は \(\Sigma_n\)-定義可能である．
• \(k \notin X \iff \neg \eta_k(k) \notin {\rm Th}(T)\) であるが，\(Y\) の元は \(T\) において決定可能なので，\(T \vdash \eta_k(k)\) もしくは \(T \vdash \neg \eta_k(k)\) である． つまり \(k \notin X \iff \eta_k(k) \in {\rm Th}(T)\) なので \(X\) の補集合も \(\Sigma_n\)-定義可能である．

したがって \(X\) は \(\Delta_n\)-定義可能である．

全ての \(k\) について，\(\eta_k(x)\) は \(X\) を定義しないことを示す．

• \(k \in X\) のとき，\(X\) の定義により \(T \vdash \neg \eta_k(k)\) である． よって \(\mathbb{N} \models \neg \eta_k(k)\) となるので \(\eta_k(x)\) は \(X\) を定義しない．
• \(k \notin X\) のとき，\(X\) の定義により \(T \nvdash \neg \eta_k(k)\) なので \(\mathbb{N} \models \eta_k(k)\) である． したがって \(\eta_k(x)\) は \(X\) を定義しない．

以上より，\(X\) は \(Y\) のどんな元，つまりどんな \(\Delta_n({\sf PA})\) 論理式によっても定義されない \(\Delta_n\)-定義可能な集合である．

2017/09/18