健全性と $\omega$-無矛盾性

参考文献

[God31] Gödel, Kurt. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. (in German). Monatshefte für Mathematik und Physik, vol. 38, no. 1, pp. 173--198.
英訳：Kurt Gödel, Collected Works, vol. 1, pp. 145--195.
[KK17] Kikuchi, Makoto and Kurahashi, Taishi. (2017). Generalizations of Gödel's incompleteness theorems for $\Sigma_n$-definable theories of arithmetic. The Review of Symbolic Logic, vol. 10, no. 4, pp. 603--616.
[Kre57] Kreisel, Georg. (1957). A refinement of $\omega$-consistency (abstract). The Journal of Symbolic Logic, vol. 22, pp. 108--109.

§1. $\Gamma$-健全性と $\Gamma$-無矛盾性の定義と基本的な性質

以降では $T$ を ${\sf PA}$ の拡大理論とし，$\Gamma$ を算術の論理式の集合とする．

定義.

理論 $T$ が $\Gamma$-健全であるとは，任意の $\Gamma$ 文 $\varphi$ に対して，$T \vdash \varphi$ ならば $\mathbb{N} \models \varphi$ となることをいう．
理論 $T$ が健全であるとは，全ての自然数 $n$ について $\Sigma_n$-健全であることをいう．

すなわち健全であるということは $\mathbb{N}$ をモデルにもつことに他ならない． $\Gamma$-健全性に関する基本的な性質を示しておく．

命題 1.

理論 $T$ は無矛盾 $\iff T$ は $\Sigma_0$-健全．

証明.
($\Rightarrow$): $T$ が無矛盾とする． $\varphi$ を $\Sigma_0$ 文とし，$T \vdash \varphi$ とする．いま $\mathbb{N} \models \neg \varphi$ ならば $T$ の $\Sigma_1$-完全性より $T \vdash \neg \varphi$ となるため $T$ の無矛盾性に反する．したがって $\mathbb{N} \models \varphi$ である．つまり $T$ は $\Sigma_0$-健全である．
($\Leftarrow$): $T$ が $\Sigma_0$-健全とする．いま $T \vdash 0 = 1$ とすると $0 = 1$ は $\Sigma_0$ 文なので $\mathbb{N} \models 0 = 1$ となるためおかしい．したがって $T \nvdash 0 = 1$ なので $T$ は無矛盾である．

□

命題 2.

理論 $T$ は $\Sigma_n$-健全 $\iff T$ は $\Pi_{n+1}$-健全．

証明.
$(\Rightarrow)$: $T$ が $\Sigma_n$-健全であるとする． $\varphi(x)$ を $\Sigma_n$ 論理式とし，$T \vdash \forall x \varphi(x)$ とする．任意の $k \in \omega$ について $T \vdash \varphi(\overline{k})$ なので，$T$ の $\Sigma_n$-健全性より，任意の $k \in \omega$ について $\mathbb{N} \models \varphi(\overline{k})$ である．つまり $\mathbb{N} \models \forall x \varphi(x)$ である．したがって $T$ は $\Pi_{n+1}$-健全である．
$(\Leftarrow)$: $\Sigma_n \subseteq \Pi_{n+1}$ なので明らか．

□

命題 3.

$T$ が $\Sigma_n$-健全で $\varphi$ を $\mathbb{N} \models \varphi$ となる $\Sigma_{n+1}$ 文とすると，$T + \varphi$ も $\Sigma_n$-健全．

証明.
$T$ と $\varphi$ は条件を満たすとする． $\psi$ を $\Sigma_n$ 文とし，$T + \varphi \vdash \psi$ とする．このとき $\neg \varphi \lor \psi$ は $T$ において証明可能な $\Pi_{n+1}$ 文である．命題 2 より $T$ は $\Pi_{n+1}$-健全なので $\mathbb{N} \models \neg \varphi \lor \psi$ である． $\mathbb{N} \models \varphi$ なので $\mathbb{N} \models \psi$ となる．したがって $T + \varphi$ が $\Sigma_n$-健全であることが示せた．

□

続いて理論の $\Gamma$-無矛盾性の概念を導入する．

定義.

理論 $T$ が $\Gamma$-無矛盾であるとは，任意の１変数 $\Gamma$ 論理式 $\varphi(x)$ に対して，もし全ての $k \in \omega$ について $T \vdash \neg \varphi(\overline{k})$ ならば，$T \nvdash \exists x \varphi(x)$ となることをいう．
理論 $T$ が $\omega$-無矛盾であるとは，全ての自然数 $n$ について $\Sigma_n$-無矛盾であることをいう．

$\omega$-無矛盾性の概念はよく知られている通り Gödel [Göd31] によって導入されたものである．ここでいう $\Pi_{n-1}$-無矛盾性の概念は"$n$-無矛盾性"という名で Kreisel [Kre57] によって導入されたものである． $\Gamma$-無矛盾性に関する基本的な性質も述べておく．

命題 4.

理論 $T$ は $\Pi_n$-無矛盾 $\iff T$ は $\Sigma_{n+1}$-無矛盾．

証明.
$(\Rightarrow)$: $T$ が $\Pi_n$-無矛盾であるとする． $\varphi(x, y)$ を $\Pi_n$ 論理式とし，全ての自然数 $k$ について $T \vdash \neg \exists y \varphi(\overline{k}, y)$ となるとする．このとき全ての $k, l$ について $T \vdash \neg \varphi(\overline{k}, \overline{l})$ となる．いま $\Pi_n$ 論理式 $\psi(z)$ を $\forall x \leq z \forall y \leq z(z = \langle x, y \rangle \to \varphi(x, y))$ とすると，任意の $m$ について，$m = \langle k, l \rangle$ となる $l \leq m$ と $k \leq m$ がとれて $T \vdash \neg \varphi(\overline{k}, \overline{l})$ となるので，$T \vdash \neg \psi(\overline{m})$ である． $T$ は $\Pi_n$-無矛盾なので $T \nvdash \exists z \psi(z)$ である． ${\sf PA} \vdash \exists x \exists y \varphi(x, y) \leftrightarrow \exists z \psi(z)$ であるから $T \nvdash \exists x \exists y \varphi(x, y)$ となる．したがって $T$ は $\Sigma_{n+1}$-無矛盾である．
$(\Leftarrow)$: $\Pi_n \subseteq \Sigma_{n+1}$ なので明らか．

□

§2. $\Gamma$-健全性と $\Gamma$-無矛盾性の関係

それでは $\Sigma_n$-健全性と $\Sigma_n$-無矛盾性の関係を調べていく．はじめに健全性から $\omega$-無矛盾性が導かれることを示しておく．

命題 5.

理論 $T$ は健全 $\Rightarrow T$ は $\omega$-無矛盾．

証明.
$T$ を健全な理論とする．任意の自然数 $n$ について $T \vdash \neg \varphi(\overline{n})$ とする． $T$ は健全なので $\mathbb{N} \models \neg \varphi(\overline{n})$ となるが，$n$ は任意だったので $\mathbb{N} \models \forall x \neg \varphi(x)$ となる．再び $T$ は健全なので $T \vdash \exists x \varphi(x)$ となることはあり得ない．したがって $T$ は $\omega$-無矛盾である．

□

この命題は次のように精密化できる．

命題 6.

理論 $T$ は $\Sigma_n$-健全 $\Rightarrow T$ は $\Sigma_n$-無矛盾．

証明.
$T$ を $\Sigma_n$-健全な理論とする． $\varphi(x)$ を任意の $\Sigma_n$ 論理式とし，任意の自然数 $k$ について $T \vdash \neg \varphi(\overline{k})$ とする． $T$ は $\Sigma_n$-健全なので，命題 2 より $T$ は $\Pi_{n+1}$-健全である．したがって $\mathbb{N} \models \neg \varphi(\overline{k})$ となるが，$k$ は任意だったので $\mathbb{N} \models \forall x \neg \varphi(x)$ となる．いま $T \vdash \exists x \varphi(x)$ とすれば $T$ の $\Sigma_n$-健全性より $\mathbb{N} \models \exists x \varphi(x)$ となりおかしい．よって $T \nvdash \exists x \varphi(x)$ である．以上より $T$ は $\Sigma_n$-無矛盾であることが示せた．

□

後に示すように，この逆は成立しない．しかし理論がある程度の強さをもっていれば逆が成立する．このことを述べるために次の概念を導入する．

定義.

理論が $\Gamma$-完全であるとは，任意の $\Gamma$ 文 $\varphi$ について，$\mathbb{N} \models \varphi$ ならば $T \vdash \varphi$ となることをいう．

例えば ${\sf PA}$ の拡大理論は $\Sigma_1$-完全である．この概念の基本的な性質を挙げておく．

命題 7.

理論 $T$ が $\Pi_n$-完全 $\iff T$ は $\Sigma_{n+1}$-完全．

証明.
$(\Rightarrow)$: $T$ が $\Pi_n$-完全であるとする． $\Pi_n$ 論理式 $\varphi(x)$ について $\mathbb{N} \models \exists x \varphi(x)$ とする．このときある自然数 $k$ について $\mathbb{N} \models \varphi(\overline{k})$ であるから，$T$ の $\Pi_n$-完全性より $T \vdash \varphi(\overline{k})$ である．したがって $T \vdash \exists x\varphi(x)$ なので $T$ は $\Sigma_{n+1}$-完全である．
$(\Leftarrow)$: $\Pi_n \subseteq \Sigma_{n+1}$ なので明らか．

□

$\Gamma$-完全性の概念は理論の完全性とは直接的には無関係であるが，間接的には次のことが成り立つ．

命題 8.

理論 $T$ が全ての $n$ について $\Sigma_n$-完全 $\Rightarrow$ $T$ は完全．

証明.
$(\Rightarrow)$: $T$ は全ての $n$ について $\Sigma_n$-完全とする． $\varphi$ を任意の文とすると $\mathbb{N} \models \varphi$ もしくは $\mathbb{N} \models \neg \varphi$ である． $\varphi$ と $\neg \varphi$ が共に $\Sigma_k$ 文であるような $k$ がとれるが，$k$ の $\Sigma_k$-完全性より $T \vdash \varphi$ または $T \vdash \neg \varphi$ となる．

□

さて，理論にある程度の強さがあれば，命題 6 の逆が成り立つことを示す．

定理 9.

理論 $T$ が $\Sigma_{n+1}$-無矛盾かつ $\Sigma_n$-完全 $\Rightarrow T$ は $\Sigma_{n+1}$-健全．

証明.
$\varphi(x)$ を $\Pi_n$ 論理式として，$T \vdash \exists x \varphi(x)$ であるとする． $T$ の $\Sigma_{n+1}$-無矛盾性より，ある自然数 $k$ が存在して $T \nvdash \neg \varphi(\overline{k})$ となる．もし $\mathbb{N} \models \neg \varphi(\overline{k})$ ならば $T$ の $\Sigma_n$-完全性より $T \vdash \neg \varphi(\overline{k})$ となるためおかしい．よって $\mathbb{N} \models \varphi(\overline{k})$ であり，$\mathbb{N} \models \exists x \varphi(x)$ である．以上より $T$ は $\Sigma_{n+1}$-健全である．

□

$T$ は $\Sigma_1$-完全なので次が成り立つ．

系 10.

$T$ は $\Sigma_1$-健全 $\iff T$ は $\Sigma_1$-無矛盾．
$T$ は $\Sigma_2$-健全 $\iff T$ は $\Sigma_2$-無矛盾．
$T$ は $\omega$-無矛盾 $\Rightarrow T$ は $\Sigma_2$-健全．

$\Sigma_{n+2}$-無矛盾性から $\Sigma_{n+2}$-健全性を導くには，実は $\Sigma_{n+1}$-完全性よりも弱い条件があれば充分である．このことを述べるために次の概念を導入する．

定義.

理論が $\Gamma$-決定的であるとは，全ての $\Gamma$ 文 $\varphi$ について $T \vdash \varphi$ もしくは $T \vdash \neg \varphi$ となることをいう．

これは理論の完全性の概念を精密化したものである．例えば Gödel-Rosser の第一不完全性定理は，理論 $T$ が無矛盾かつ $\Sigma_1$-定義可能であれば $\Sigma_1$-決定的でない，という形で述べることができる． $\Gamma$-完全性との関係は次の通りである．

命題 11.

以下は同値：

$T$ は $\Sigma_{n+1}$-完全かつ無矛盾．
$T$ は $\Sigma_n$-決定的かつ $\Sigma_n$-健全．

証明.
$(1 \Rightarrow 2)$: $T$ が $\Sigma_{n+1}$-完全かつ無矛盾とする． $\varphi$ を任意の $\Sigma_n$ 文とする．

$\mathbb{N} \models \varphi$ または $\mathbb{N} \models \neg \varphi$ であるが，$\varphi$ と $\neg \varphi$ は共に $\Sigma_{n+1}$ 文なので $T$ の $\Sigma_{n+1}$-完全性より $T \vdash \varphi$ または $T \vdash \neg \varphi$ となる．したがって $T$ は $\Sigma_n$-決定的である．
$T \vdash \varphi$ とする．いま $\mathbb{N} \models \neg \varphi$ と仮定すると $T$ の $\Sigma_{n+1}$-完全性より $T \vdash \neg \varphi$ なので $T$ の無矛盾性に反する．したがって $\mathbb{N} \models \varphi$ である．つまり $T$ は $\Sigma_n$-健全である．

$(2 \Rightarrow 1)$: $T$ が $\Sigma_n$-決定的かつ $\Sigma_n$-健全とする．命題 1 より $T$ は無矛盾である．命題 7 より $T$ が $\Pi_n$-完全であることを示せば十分である． $\varphi$ を任意の $\Pi_n$ 文とし，$\mathbb{N} \models \varphi$ とする． $T \vdash \neg \varphi$ とすると $T$ の $\Sigma_n$-健全性より $\mathbb{N} \models \neg \varphi$ となるためおかしい．したがって $T \nvdash \neg \varphi$ である． $T$ は $\Sigma_n$-決定的なので $T \vdash \varphi$ となる．以上より $T$ は $\Pi_n$-完全である．

□

命題 11 より，定理 9 における $T$ が $\Sigma_n$ であるという仮定は，$T$ が $\Sigma_{n-1}$-決定的かつ $\Sigma_{n-1}$-健全であるという仮定と同値である．この観点から定理 9 を次のように改良することができる．

定理 12.

$T$ が $\Sigma_{n+2}$-無矛盾かつ $\Sigma_n$-決定的 $\Rightarrow T$ は $\Sigma_{n+2}$-健全．

証明.
$n$ に関する帰納法で示す．

$n = 0$ の場合は既に示した．
$n$ について成り立つと仮定する． $T$ を $\Sigma_{n+3}$-無矛盾かつ $\Sigma_{n+1}$-決定的とする． $\varphi(x, y)$ を $\Sigma_{n+1}$ 論理式とし，$T \vdash \exists x \forall y \varphi(x, y)$ とする． $T$ は $\Sigma_{n+3}$-無矛盾なので，ある $k$ について $T \nvdash \neg \forall y \varphi(\overline{k}, y)$ となる．よってその $k$ と任意の $l$ について $T \nvdash \neg \varphi(\overline{k}, \overline{l})$ である． $T$ は $\Sigma_{n+1}$-決定的なので全ての $l$ について $T \vdash \varphi(\overline{k}, \overline{l})$ となる． $T$ は $\Sigma_{n+2}$-無矛盾かつ $\Sigma_n$-決定的でもあるので，帰納法の仮定より $T$ は $\Sigma_{n+2}$-健全である．したがって全ての $l$ について $\mathbb{N} \models \varphi(\overline{k}, \overline{l})$ であるから $\mathbb{N} \models \forall y \varphi(\overline{k}, y)$ である．つまり $\mathbb{N} \models \exists x \forall y \varphi(x, y)$ となる．以上より $T$ は $\Sigma_{n+3}$-健全である．

□

系 13.

以下は同値：

$T$ は $\Sigma_{n+1}$-完全かつ無矛盾．
$T$ は $\Sigma_n$-決定的かつ $\Sigma_n$-無矛盾．

証明.
定理 12 より $T$ は $\Sigma_n$-決定的かつ $\Sigma_n$-健全 $\iff T$ は $\Sigma_n$-決定的かつ $\Sigma_n$-無矛盾，となるため．

□

§3. いろいろな反例

ここでは，ある性質がある性質を導かないことを示す．まずは $\Sigma_n$-健全性が $\Sigma_{n+1}$-健全性を一般には導かないことを示す．

命題 13.

$\Sigma_n$-健全な任意の理論 $T$ に対してある $\Sigma_{n+1}$-文 $\varphi$ が存在して，$T + \varphi$ は $\Sigma_n$-健全であるが $\Sigma_{n+1}$-健全でない．

証明.
$T$ を $\Sigma_n$-健全な理論とする． ${\rm RFN}_{T + x}(\Sigma_n)$ を "$T + x$ が $\Sigma_n$-健全"であることを表す $\Pi_{n+1}$ 論理式とする．すなわち ${\rm RFN}_{T + x}(\Sigma_n)$ は \[ \forall y(\Sigma_n(y) \land {\rm Pr}_T(x \to y) \to {\sf Tr}_{\Sigma_n}(y)) \] とかける．不動点定理より，次を満たす $\Sigma_{n+1}$ 文 $\varphi$ がとれる： \[ {\sf PA} \vdash \varphi \leftrightarrow \neg {\rm RFN}_{T + \varphi}(\Sigma_n). \] ${\sf PA}$ の健全性より，この同値性は $\mathbb{N}$ においても成り立つ．

$\mathbb{N} \models \varphi$ とすると命題 3 より $T + \varphi$ も $\Sigma_n$-健全である．よって $\mathbb{N} \models {\rm RFN}_{T + \varphi}(\Sigma_n)$ なので $\mathbb{N} \models \neg \varphi$ となりおかしい．したがって $\mathbb{N} \models \neg \varphi$ である．
つまり $\mathbb{N} \models {\rm RFN}_{T + \varphi}(\Sigma_n)$ なので $T + \varphi$ は $\Sigma_n$-健全である．
一方 $\Sigma_{n+1}$ 文 $\varphi$ について $T + \varphi \vdash \varphi$ かつ $\mathbb{N} \models \neg \varphi$ なので $T + \varphi$ は $\Sigma_{n+1}$-健全でない．

□

系 10 において $\omega$-無矛盾性が $\Sigma_2$-健全性を導くことを示したが，これを $\Sigma_3$-健全性に強めることはできない．したがって命題 6 の逆は一般には成り立たない．証明の方針は命題 13 とほぼ同じである．

命題 14.

健全な任意の理論 $T$ に対してある $\Sigma_3$ 文 $\varphi$ が存在して，$T + \varphi$ は $\omega$-無矛盾であるが $\Sigma_3$-健全でない．

証明.
$\omega$-${\rm Con}_{T + x}$ を "$T + x$ が $\omega$-無矛盾"であることを表す $\Pi_3$ 論理式とする． $\omega$-${\rm Con}_{T + x}$ は雑だが \[ \forall y({\sf Fml}(y) \land \forall z{\sf Pr}_{T}(x \to \neg y(z)) \to \neg {\sf Pr}_T(x \to \exists z(y))) \] のようにかける．不動点定理より，次を満たす $\Sigma_3$ 文 $\varphi$ がとれる： \[ {\sf PA} \vdash \varphi \leftrightarrow \neg \omega\text{-}{\rm Con}(T + \varphi). \]

$\mathbb{N} \models \varphi$ であると仮定すると，$\mathbb{N} \models \neg \omega\text{-}{\rm Con}(T + \varphi)$ なので $T + \varphi$ は $\omega$-無矛盾でない．一方 $T$ の健全性より $T + \varphi$ も健全である．命題 5 より $T + \varphi$ は $\omega$-無矛盾となりおかしい．よって $\mathbb{N} \models \neg \varphi$ である．
したがって $T + \varphi$ は $\omega$-無矛盾である．
一方 $\Sigma_3$ 文 $\varphi$ について $T + \varphi \vdash \varphi$ かつ $\mathbb{N} \models \neg \varphi$ となるため，$T + \varphi$ は $\Sigma_3$-健全ではない．

□

命題 6 において $\Sigma_n$-健全性が $\Sigma_n$-無矛盾性を導くことを示したが，これを $\Sigma_{n+1}$-無矛盾性に強めることはできない．

命題 15.

$T$ を $\Sigma_n$-健全な理論とすると，$T$ の拡大理論で $\Sigma_n$-健全であるが $\Sigma_{n+1}$-無矛盾でないものが存在する．

証明.
$n = 0$ の場合は $\Sigma_1$-健全性と $\Sigma_1$-無矛盾性が同値であること（系 10）から，命題 13 より $\Sigma_0$-健全だが $\Sigma_1$-無矛盾でない理論の存在が既に示せている．したがって $n \geq 1$ としてよい．命題 13 より，$T + \varphi$ が $\Sigma_n$-健全であるが $\mathbb{N} \models \neg \varphi$ となる $\Sigma_{n+1}$ 文 $\varphi$ がとれる．また $\varphi$ は $\Sigma_{n-1}$ 論理式 $\delta(x, y)$ について $\exists x \forall y \delta(x, y)$ という形であるとしてよい． $\mathbb{N} \models \forall x \exists y \neg \delta(x, y)$ なので，各自然数 $k$ に対して $\mathbb{N} \models \neg \delta(\bar{k},\overline{m_k})$ となる自然数 $m_k$ がとれる． \[ T' := T +\varphi + \{\neg \forall y \delta(\bar{k}, y) : k \in \omega\} \] と定める．

$\forall y \delta(x, y)$ は $\Pi_n$ 論理式であり，$T' \vdash \exists x \forall y \delta(x, y)$ かつ任意の自然数 $k$ について $T' \vdash \neg \forall y \delta(\bar{k}, y)$ となるため $T'$ は $\Pi_{n+1}$-無矛盾でない．したがって $T'$ は $\Sigma_{n+1}$-無矛盾でない．
$\psi$ を $T' \vdash \psi$ となる $\Sigma_n$ 文とすると，ある自然数 $k \in \omega$ があって， \[ T + \varphi \vdash \left(\neg \forall y \delta(\bar{0}, y) \land \dots \land \neg \forall y\delta(\bar{k}, y)\right) \to \psi, \] つまり \[ T + \varphi \vdash \forall y \delta(\bar{0}, y) \lor \dots \lor \forall y\delta(\bar{k}, y) \lor \psi \] となる．特に \[ T + \varphi \vdash \delta(\bar{0}, \overline{m_0}) \lor \dots \lor \delta(\bar{k}, \overline{m_k}) \lor \psi \] である． $\delta(\bar{0}, \overline{m_0}) \lor \dots \lor \delta(\bar{k}, \overline{m_k}) \lor \psi$ は $\Sigma_n$ 文なので $T + \varphi$ の $\Sigma_n$-健全性より \[ \mathbb{N} \models \delta(\bar{0}, \overline{m_0}) \lor \dots \lor \delta(\bar{k}, \overline{m_k}) \lor \psi \] である．ここで各 $i$ について $\mathbb{N} \models \neg \delta(\bar{i}, \overline{m_i})$ なので $\mathbb{N} \models \psi$ が成り立つ．以上より $T'$ は $\Sigma_n$-健全である．

□

命題 6 と命題 15 より次の系が得られる．

系 16.

$\Sigma_n$-無矛盾であるが $\Sigma_{n+1}$-無矛盾でない理論が存在する．

2018/03/22

健全性と \(\omega\)-無矛盾性

参考文献

目次

§1. \(\Gamma\)-健全性と \(\Gamma\)-無矛盾性の定義と基本的な性質

§2. \(\Gamma\)-健全性と \(\Gamma\)-無矛盾性の関係

§3. いろいろな反例