証明論,順序数解析,Kreiselの反例2446通報$$$$Gentzenは順序数$\varepsilon_0$を順序型として持つ順序数表記に対する超限帰納法からPeano算術の無矛盾性を示した。現代的に言えばGentzenの示したことは以下のように表すことができる。Gentzenによる無矛盾性証明ある$\varepsilon_0$を順序型に持つ整列順序$\prec$が存在し$$\mathsf{PRA}+\mathsf{PR}\text{-}\mathsf{TI}(\prec)\vdash\mathsf{Con}(\mathsf{PA})$$であり、かつ$\prec$の任意の始切片$\prec\restriction$に対して、$$\mathsf{PRA}+\mathsf{PR}\text{-}\mathsf{TI}(\prec\restriction)\nvdash\mathsf{Con}(\mathsf{PA})$$である。このことから理論$T$の強さを表現するための不変量として以下のようなものを以下のように定義したくなる。証明論的順序数??理論$T$に対して順序数$\|T\|_{\mathsf{Con}}$を、順序数$\alpha$を標準モデルにて順序型に持つ整列順序$\prec$が存在して$$\mathsf{PRA}+\mathsf{PR}\text{-}\mathsf{TI}(\prec)\vdash\mathsf{Con}(\mathsf{T})$$となるような最小の$\alpha$とする。この定義とGentzenの定理から$\|\mathsf{PA}\|_{\mathsf{Con}}=\varepsilon_0$であることが期待されるだろう。Kreiselは任意の再帰的可算で無矛盾な理論$T$に対して$\|T\|_{\mathsf{Con}}\leq\omega$であることを示した。以下ではそのKreiselの反例を算術的階層に一般化して示す。有界論理式全体の集合とする。表せる論理式の集合とする。y$、論理式の集合$\Gamma$に対して$\Gamma\text{-}\mathsf{TI}(\prec)$を以下のような図式とする。集合$\Gamma$に対して$\mathsf{B}\Gamma$を以下のような図式とする。v)\varphi(x,\vec{y})]$、ここで$\varphi\in\Gamma$とする。1$に対して$\Sigma^0_n,\Pi^0_n$のいずれかとする。$\Gamma$から有界量化に関して閉じた論理式のクラスを$\mathcal{BQ}(\Gamma)$とする。任意の$\varphi\in\mathcal{BQ}(\Gamma)$に対してある$\psi\in\Gamma$が存在し$\mathsf{EA}+\mathsf{B}\Gamma\vdash\varphi\leftrightarrow\psi$である。任意の標準モデルで真な$\Pi^0_{n+1}$-論理式$\varphi$に対しある初等再帰的で標準モデルに於いて$\omega$を順序型として持つ整列順序$\prec^\mathrm{K}_{\varphi}$が存在し$$\mathsf{EA}+\mathsf{B}\Sigma^0_n+\Sigma^0_n\text{-}\mathsf{TI}(\prec^\mathrm{K}_{\varphi})\vdash\varphi$$であり、また$$\mathsf{EA}+\Pi^0_{n+1}\text{-}\mathsf{TI}(\prec^\mathrm{K}_{\varphi})\vdash\varphi$$である。x\varphi_0(x)$とし、$\prec^\mathrm{K}_{\varphi}$を以下のように定める。y$であり初等再帰的であることと順序型が$\omega$であることが分かる。x)\varphi_0(i)$とすれば$\mathsf{B}\Sigma^0_n$から$\varphi'$は適当な$\Sigma^0_n$-論理式と同一視できる。x)\varphi'(y)\to\varphi'(x)$$が成り立つ。これを背理法で示そう。x)\varphi'(y)$から$\varphi'(x+1)$である。明らかに$\varphi'(x+1)\to\varphi'(x)$なので$\varphi'(x)$が成り立ち矛盾する。x)\psi(y)\to\psi(x)$$となる。x)\varphi_0(i)$$となる。x\varphi_0(x)$すなわち$\varphi$と同値になる。$$\mathsf{EA}+\Pi^0_{n+1}\text{-}\mathsf{TI}(\prec^\mathrm{K}_{\varphi})\vdash\varphi$$の方は$\varphi'$が$\Pi^0_{n+1}$-論理式になることから$\Sigma^0_n$に落とさなくても良くなることによる。以上にて証明を終える。再帰的可算かつ無矛盾な理論$T$に対し$\omega$を順序型として持つ整列順序$\prec^\mathrm{K}_T$が存在し$$\mathsf{EA}+\Sigma^0_0\text{-}\mathsf{TI}(\prec^\mathrm{K}_T)\vdash\mathsf{Con}(T)$$が成り立つ。$\mathsf{EA}\vdash\mathsf{B}\Sigma^0_0$である。\prec^\mathrm{K}_{\mathsf{Con}(T)}$とし一般化されたKreiselの反例による。高評価したユーザはいませんこの記事に送られたバッジバッジはありません。バッチを贈って投稿者を応援しようバッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。バッチを贈るコメントAlwe@ptykesKreiselの。