複雑さが有限の拡大の不完全性

---

このページは神戸大学の酒井さんより 2019 年 3 月に受けた次の質問に対する回答をメモしたものです．

• \({\sf PA} + X\) が無矛盾かつ完全な理論となるような \(\Sigma_n\) 文の集合 \(X\) がとれる \(n\) はあるか？

直観的には明らかに存在しなさそうだが，すぐに答えることができなかった． このページにあるものより簡単な回答を見つけた方がいれば教えてもらえると嬉しいです．

---

この問題に答えるには次の事実を用いればよい．

事実. (Lindström - Aspects of Incompleteness, 初版 p.71, Exersice 5.9(a); 第二版 p.91, Exercise 5.6(a))

\(T\) を \({\sf PA}\) の無矛盾かつ再帰的な拡大理論とすると，ある \(\Delta_{n+1}\) 文 \(\varphi\) が存在して，\(\varphi\) も \(\neg \varphi\) も \(T\) 上で \(\Pi_n\)-保存的となる．

　

定理.

\(T\) を \({\sf PA}\) の無矛盾な再帰的拡大理論とし，\(X\) をある \(n\) に対する \(\Sigma_n\) 文の集合とする． このとき \(T + X\) は無矛盾ならば不完全．

　

証明.
条件を満たす \(T\) と \(X\) について，\(T + X\) が完全であると仮定して \(T + X\) が矛盾することを示す． 事実より，\(\varphi\) と \(\neg \varphi\) がともに \(T\) 上 \(\Pi_n\)-保存的であるような \(\Delta_{n+1}\) 文 \(\varphi\) がとれる． 完全性より \(T + X \vdash \varphi\) または \(T + X \vdash \neg \varphi\) である．

• \(T + X \vdash \varphi\) のとき，\(\psi_0, \ldots, \psi_{k-1} \in X\) があって，\(T \vdash \bigwedge_{i < k} \psi_i \to \varphi\) となる． つまり \(T + \neg \varphi \vdash \neg \bigwedge_{i < k} \psi_i\) である． \(X\) の取り方より \(\neg \bigwedge_{i < k} \psi_i\) は \(\Pi_n\) 文なので，\(\varphi\) のとり方より \(T \vdash \neg \bigwedge_{i < k} \psi_i\) である． したがって \(T + X\) は矛盾する．
• \(T + X \vdash \neg \varphi\) のときも同様に \(\varphi\) が \(T\) 上 \(\Pi_n\)-保存的なので \(T + X\) が矛盾する．

次の系が得られる．

系.

\(T\) を \({\sf PA}\) の無矛盾な再帰的拡大理論とすると，\(T\) の任意のモデル \(M\) について，\(T + {\rm Th}_{\Sigma_n}(M)\) は不完全．

次の系は Gödel-Rosser の不完全性定理の一般化（\(\Sigma_{n+1}\)-定義可能かつ \(\Sigma_n\)-健全ならば不完全）からも得られるが，今回の定理を用いて示すこともできる．

系.

\(T\) を \({\sf PA}\) の \(\Sigma_n\)-健全な再帰的拡大理論とすると，\(T + {\rm Th}_{\Sigma_{n+1}}(\mathbb{N})\) は無矛盾かつ不完全．

　

証明.
\(T\) を \(\Sigma_n\)-健全とする． このとき \(T + {\rm Th}_{\Sigma_{n+1}}(\mathbb{N})\) が矛盾すれば，ある \(\Sigma_{n+1}\) 文 \(\sigma\) があって，\(T \vdash \neg \sigma\) かつ \(\mathbb{N} \models \sigma\) となる． ここで \({\sf PA} \vdash \neg \sigma \leftrightarrow \forall x \delta(x)\) となる \(\Sigma_n\) 論理式 \(\delta(x)\) をとれば，任意の \(n \in \omega\) について \(T \vdash \delta(\overline{n})\) となる． \(T\) の \(\Sigma_n\)-健全性より \(\mathbb{N} \models \delta(\overline{n})\) であり，\(n\) は任意なので \(\mathbb{N} \models \forall x \delta(x)\)，つまり \(\mathbb{N} \models \neg \sigma\) となるためおかしい． したがって \(T + {\rm Th}_{\Sigma_{n+1}}(\mathbb{N})\) は無矛盾である． \({\rm Th}_{\Sigma_{n+1}}(\mathbb{N})\) は \(\Sigma_{n+1}\) 文の集合なので，定理より \(T + {\rm Th}_{\Sigma_{n+1}}(\mathbb{N})\) は不完全である．