二階算術

同義語:second-order arithmeticsecond order arithmetic

概要

二階算術(second-order arithmetic)とは、自然数を動く数変数と自然数の集合を動く集合変数の 2 種類の変数をもつ一階の形式体系 $\mathsf Z_2$ で、算術の基本公理、集合についての帰納法の公理、任意の式で集合を作る内包公理図式からなる。内包を式の複雑さで制限すると $\mathsf{ACA}_0$ や $\Pi^1_k\text{-}\mathsf{CA}_0$ などの部分体系が得られ、逆数学の舞台になる。数の部分が標準的な $\omega$ モデルでも、集合の範囲は冪集合全体とは限らず、可算なものがある。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 一階述語論理, Peano算術, 数学的帰納法

二階算術(second-order arithmetic)とは、自然数を表す数変数と、自然数の集合を表す集合変数の 2 種類の変数をもつ形式体系 $\mathsf Z_2$ である。公理は、足し算・掛け算・大小についての算術の基本公理、集合についての帰納法の公理 1 本、そして「どんな式 $\varphi(n)$ についても集合 $\{n\mid\varphi(n)\}$ がある」という内包公理図式からなる。
実数は有理数の列で、有理数は自然数の対で表せるので、実数・連続関数・可算な距離空間などは自然数の集合で符号化できる。そのため、解析学や代数学の可算な部分の多くは $\mathsf Z_2$ の中で展開できる。内包公理を式の複雑さで制限すると、強さの違う部分体系の列が得られ、ある定理を証明するのにどの部分体系が必要かを測る研究が 逆数学 である。
名前に「二階」とあるが、$\mathsf Z_2$ は 2 種類の変数をもつ通常の一階の理論である。集合変数が冪集合全体を動くとは限らないので、二階論理 の標準意味論で読む二階の Peano 算術とは区別する(rem-soa-first-order)。この記事では、体系の定義、内包公理から帰納法の図式が出ること、部分体系の定義、$\omega$ モデルと $\beta$ モデル、標準でないモデルの存在を扱う。

定義

言語と構造

二階算術の言語と構造

二階算術の言語 $L_2$ は、数変数 $i,j,k,m,n,\dots$、集合変数 $X,Y,Z,\dots$、定数記号 $0,1$、2 項演算記号 $+,\cdot$、2 項関係記号 $<$ をもつ。数の項は数変数・$0$・$1$ から $+,\cdot$ で作り、原子式は $t_1=t_2$、$t_1< t_2$、$t_1\in X$($t_1,t_2$ は数の項)である。式は原子式から論理結合子、数の量化 $\forall n,\exists n$、集合の量化 $\forall X,\exists X$ で作る。
$L_2$ 構造は、組
$$ M=(\lvert M\rvert,\ \mathcal S_M,\ +_M,\ \cdot_M,\ 0_M,\ 1_M,\ <_M) $$
で、$\lvert M\rvert$ は空でない集合(数変数が動く範囲)、$\mathcal S_M$ は $\lvert M\rvert$ の部分集合からなる空でない集合(集合変数が動く範囲)、$+_M,\cdot_M$ は $\lvert M\rvert$ 上の 2 項演算、$0_M,1_M\in\lvert M\rvert$、$<_M$ は $\lvert M\rvert$ 上の 2 項関係である。$t\in X$ は所属関係で解釈する。
意図されたモデルは $(\omega,\mathcal P(\omega),+,\cdot,0,1,<)$ である。$\mathcal S\subseteq\mathcal P(\omega)$ について、$(\omega,\mathcal S,+,\cdot,0,1,<)$ の形の構造を $\omega$ モデルといい、単に $\mathcal S$ で表す。

$\omega$ モデルは、数の部分は本物の自然数で、集合の範囲だけが小さいかもしれない構造である(Sim06 Definitions I.2.1–I.2.3, pp. 3–4)。

公理

二階算術 Z₂

二階算術 $\mathsf Z_2$ は、次の (i)〜(iii) の全称閉包を公理とする $L_2$ の体系である。
(i) 基本公理:
$$ \begin{gathered} n+1\neq0,\qquad m+1=n+1\to m=n,\qquad m+0=m,\qquad m+(n+1)=(m+n)+1,\\ m\cdot0=0,\qquad m\cdot(n+1)=(m\cdot n)+m,\qquad \lnot\,m<0,\qquad m< n+1\leftrightarrow(m< n\lor m=n). \end{gathered} $$
(ii) 帰納法の公理:$\bigl(0\in X\land\forall n\,(n\in X\to n+1\in X)\bigr)\to\forall n\,(n\in X)$。
(iii) 内包公理図式:$L_2$ の式 $\varphi(n)$ で $X$ を自由変数にもたないものごとに、$\exists X\,\forall n\,\bigl(n\in X\leftrightarrow\varphi(n)\bigr)$。
$\varphi(n)$ は $n$ 以外の自由変数(数でも集合でもよい)を含んでよく、それらを母数という。$L_2$ の式で、公理がすべて $\mathsf Z_2$ の定理であるものからなる体系を $\mathsf Z_2$ の部分体系という。

これは Sim06 Definition I.2.4(p. 4)の形である。帰納法は式の図式ではなく、集合についての公理 1 本である。式についての帰納法は (ii) と (iii) を組み合わせて得る(prop-soa-induction-scheme)。この体系は Hilbert と Bernays が同値な形で導入した(Sim06 p. 6 の注)。

一階の理論として読むこと

$\mathsf Z_2$ は 2 種類の変数をもつ一階の理論なので、Gödelの完全性定理 がそのまま使える。すなわち $L_2$ の文 $\sigma$ が $\mathsf Z_2$ の定理であることと、$\mathsf Z_2$ のすべての $L_2$ 構造で $\sigma$ が成り立つことは同値である(Sim06 pp. 5–6)。
二階論理 の標準意味論では、集合の量化は必ず冪集合全体を動き、二階の Peano 算術のモデルは自然数と同型なものだけになる(範疇性)。$\mathsf Z_2$ の $L_2$ 構造はむしろ 二階論理 の Henkin 意味論の構造にあたり、集合の範囲 $\mathcal S_M$ は内包公理を満たす範囲で自由に小さくなりうる。実際、thm-soa-nonstandard のとおり、$\mathsf Z_2$ には標準でないモデルも、集合の範囲が可算な $\omega$ モデルもある。

直観

数変数だけの Peano算術 では「自然数の任意の集合」について語れないので、実数や関数を 1 つずつ式で書かなければならない。$\mathsf Z_2$ は集合変数を加え、内包公理で「式で定義できる集合はある」と言い切ることで、実数の全体や関数の空間について量化できるようにした体系である。どの式で集合を作ってよいかを制限するのが部分体系であり、制限の強さが数学的な定理の強さの物差しになる。

帰納法の図式

帰納法の図式

$L_2$ の任意の式 $\varphi(n)$(母数を含んでよい)について、$\mathsf Z_2$ は
$$ \bigl(\varphi(0)\land\forall n\,(\varphi(n)\to\varphi(n+1))\bigr)\to\forall n\,\varphi(n) $$
を証明する。より正確には、基本公理・帰納法の公理と、$\varphi$ についての内包公理の事例 1 つから、この文の全称閉包が証明できる。

母数を固定し、$\varphi(0)$ と $\forall n\,(\varphi(n)\to\varphi(n+1))$ を仮定する。$X$ が $\varphi$ に現れない集合変数となるように選び、内包公理の事例により $\forall n\,(n\in X\leftrightarrow\varphi(n))$ を満たす $X$ をとる。すると $0\in X$ であり、$n\in X$ なら $\varphi(n)$、したがって $\varphi(n+1)$、すなわち $n+1\in X$ である。帰納法の公理により $\forall n\,(n\in X)$、ゆえに $\forall n\,\varphi(n)$ が成り立つ。$\square$

証明から分かるとおり、内包を $\Gamma$ という式のクラスに制限した部分体系は、$\Gamma$ の式についての帰納法の図式を証明する。たとえば算術的な式(集合の量化を含まない式)の内包をもつ $\mathsf{ACA}_0$ は算術的な帰納法を証明する(Sim06 p. 7)。逆に内包がなければ、帰納法の公理だけでは式の帰納法は出ない。

反例:内包のない構造で帰納法の図式が成り立たない

$\lvert M\rvert=\{0,1\}\times\mathbb N$ とし、$a_k:=(0,k)$、$b_k:=(1,k)$ と書く。$0_M:=a_0$、$1_M:=a_1$ とし、
$$ x+a_l:=x\text{ の第 2 成分に }l\text{ を足したもの},\qquad x+b_l:=b_l, $$
$x\cdot a_l$ と $x\cdot b_l$ はどちらも $x$ を $l$ 回足したもの($l=0$ なら $a_0$)とし、$(i,k)<_M(j,l)$ を「$i< j$、または $i=j$ かつ $k< l$」で定める。$\mathcal S_M:=\{\emptyset,\lvert M\rvert\}$ とする。
基本公理を満たす。 $x+1=x+a_1$ は第 2 成分を 1 増やすので単射で、値は $a_0$ にならない。$m+0=m$ は定義から明らか。$m+(n+1)=(m+n)+1$ は、$n=a_l$ なら両辺とも第 2 成分に $l+1$ を足したもの、$n=b_l$ なら $n+1=b_{l+1}$ で両辺とも $b_{l+1}$ である。掛け算の 2 式は「$l+1$ 回の和は $l$ 回の和に $x$ を足したもの」から従う。$a_0$ より小さい元はなく、$n+1$ より小さい元は $n$ より小さい元と $n$ 自身である($n=a_l$ でも $b_l$ でも辞書式の順序で確かめられる)。
帰納法の公理を満たす。 $X=\emptyset$ なら $0\in X$ が偽で仮定が成り立たず、$X=\lvert M\rvert$ なら結論が成り立つ。
帰納法の図式は成り立たない。 $\varphi(n):\equiv n=0\lor\exists m\,(m+1=n)$ とおく。$\varphi(0)$ は真で、どの $n$ でも $\varphi(n+1)$ は $m=n$ で真である。ところが $b_0$ は $a_0$ ではなく、$m+1$ は第 2 成分が $1$ 以上なので $b_0$ にならないから、$\varphi(b_0)$ は偽である。
したがってこの構造は (i)・(ii) を満たすが、prop-soa-induction-scheme の結論を満たさない。成り立たないのは $\varphi$ の内包公理の事例で、$\{n\mid\varphi(n)\}=\lvert M\rvert\setminus\{b_0\}$ は $\mathcal S_M$ にない。

部分体系

集合の量化の個数で式を分ける。数の量化だけをもつ式を算術的という。

解析的な式と内包の部分体系

$k\geq0$ とする。$\theta$ を算術的な式として、$\forall X_1\exists X_2\forall X_3\cdots X_k\,\theta$ の形の式を $\Pi^1_k$ 式、$\exists X_1\forall X_2\exists X_3\cdots X_k\,\theta$ の形の式を $\Sigma^1_k$ 式という($k=0$ ではどちらも算術的な式)。
$\Pi^1_k$ 内包の体系 $\Pi^1_k\text{-}\mathsf{CA}_0$ は、基本公理、帰納法の公理、内包公理図式を $\Pi^1_k$ 式 $\varphi(n)$ に制限したものからなる。$\Sigma^1_k\text{-}\mathsf{CA}_0$ も同様に定める。$\Pi^1_0\text{-}\mathsf{CA}_0$ を $\mathsf{ACA}_0$(算術的内包の体系)と書く。

どの式も $\mathsf{ACA}_0$ の中でどれかの $\Pi^1_k$ 式と同値になる(数の量化を 1 元集合を動く集合の量化に替えてから冠頭形に直し、続けて並ぶ同じ向きの集合の量化を対の符号で 1 つにまとめ、ダミーの量化を足す。集合の量化を数の量化の外へ出すのは論理だけではできない)ので、$\mathsf Z_2$ の定理の全体は $\Pi^1_k\text{-}\mathsf{CA}_0$($k=0,1,2,\dots$)の定理の全体の和集合と一致する。このため $\mathsf Z_2$ を $\Pi^1_\infty\text{-}\mathsf{CA}_0$ とも書く(Sim06 Definitions I.5.1–I.5.2, pp. 16–17)。式のクラスの階層そのものは 解析的階層 と同じ形である。

Σ¹ₖ 内包と Π¹ₖ 内包は同じ強さ

各 $k\geq0$ について、$\Sigma^1_k\text{-}\mathsf{CA}_0$ と $\Pi^1_k\text{-}\mathsf{CA}_0$ は同じ定理をもつ。

否定をとって補集合をとる

$k=0$ では両者は同じ体系である。$k\geq1$ とする。$\Sigma^1_k\text{-}\mathsf{CA}_0$ の公理が $\Pi^1_k\text{-}\mathsf{CA}_0$ で証明できることを示す(逆も同じ議論で示せる)。
$\varphi(n)$ を $\Sigma^1_k$ 式とする。$\lnot\exists X\,\psi\leftrightarrow\forall X\,\lnot\psi$、$\lnot\forall X\,\psi\leftrightarrow\exists X\,\lnot\psi$ を量化の外側から順に使うと、$\lnot\varphi(n)$ は、算術的な式 $\lnot\theta$ を母体とする $\Pi^1_k$ 式 $\psi(n)$ と論理的に同値になる。$\Pi^1_k$ 内包で $Y$ を $\forall n\,(n\in Y\leftrightarrow\psi(n))$ となるようにとる。次に、算術的な式 $n\notin Y$ は、集合の量化をダミーで $k$ 個足せば $\Pi^1_k$ 式と論理的に同値なので、$\Pi^1_k$ 内包($Y$ を母数とする)で $X$ を $\forall n\,(n\in X\leftrightarrow n\notin Y)$ となるようにとれる。このとき
$$ n\in X\iff n\notin Y\iff\lnot\psi(n)\iff\varphi(n) $$
であり、$X$ は $\varphi$ の内包公理の事例を満たす。基本公理と帰納法の公理は共通なので、$\Sigma^1_k\text{-}\mathsf{CA}_0$ の公理はすべて $\Pi^1_k\text{-}\mathsf{CA}_0$ の定理である。$\square$

これは Sim06 pp. 17–18 の議論である。したがって部分体系を名付けるときは $\Pi^1_k$ の側だけを使えばよい。内包をさらに弱めた $\mathsf{RCA}_0$($\Delta^0_1$ 内包と $\Sigma^0_1$ 帰納法)や、内包とは別の形の公理を加えた $\mathsf{WKL}_0$・$\mathsf{ATR}_0$ を含む 5 つの体系の定義と比較は、逆数学 で扱う。

体系集合を作る公理典型的に必要になる定理の例
$\mathsf{ACA}_0$算術的な式の内包有界な実数列の収束部分列の存在
$\Pi^1_1\text{-}\mathsf{CA}_0$$\Pi^1_1$ 式の内包可算 Abel 群が可除群と被約群の直和に分かれること
$\Pi^1_k\text{-}\mathsf{CA}_0$$\Pi^1_k$ 式の内包($k$ とともに真に強くなる)
$\mathsf Z_2$すべての式の内包

表の 3 列目の例はどれも $\mathsf{RCA}_0$ 上の同値として知られている(Sim06 Theorems I.9.3–I.9.4, p. 35)。3 行目の「真に強くなる」は $\beta$ モデルを使って示される(rem-soa-beta-minimum)。

モデル

ω モデルと内包公理

ω モデルが満たす公理

$\mathcal S\subseteq\mathcal P(\omega)$ を空でない集合とし、$\omega$ モデル $(\omega,\mathcal S,+,\cdot,0,1,<)$ を考える。
(a) このモデルは基本公理と帰納法の公理をつねに満たす。
(b) $\Gamma$ を式のクラスとする。このモデルが $\Gamma$ の式についての内包公理図式を満たすことと、$\mathcal S$ が「$\Gamma$ の式で、$\omega$ と $\mathcal S$ の元を母数として、$(\omega,\mathcal S)$ の上で定義できる $\omega$ の部分集合」をすべて含むことは同値である。
(c) とくに意図されたモデル $\mathcal P(\omega)$ は $\mathsf Z_2$ のモデルである。

(a) 基本公理は数の部分だけについての主張で、$\omega$ で成り立つ。$X\in\mathcal S$ が $0\in X$ と「$n\in X\Rightarrow n+1\in X$」を満たせば、自然数についての通常の帰納法で $X=\omega$ である。
(b) 母数を $\mathcal S$ と $\omega$ の元に固定したとき、内包公理の事例 $\exists X\,\forall n\,(n\in X\leftrightarrow\varphi(n))$ がこのモデルで真であることは、集合 $\{n\in\omega\mid(\omega,\mathcal S)\models\varphi(n)\}$ が $\mathcal S$ の元であることそのものである($X$ は $\mathcal S$ を動き、所属は本物の所属なので)。
(c) $\mathcal S=\mathcal P(\omega)$ はすべての部分集合を含むので、(a)・(b) から $\mathsf Z_2$ の公理をすべて満たす。$\square$

(b) は Sim06 p. 5 の注意の言い換えである。集合の範囲を小さくするほど内包公理は成り立ちにくくなり、どの式の内包まで成り立つかで $\omega$ モデルが部分体系に振り分けられる。たとえば計算可能集合の全体 $\mathrm{REC}$ は $\mathsf{RCA}_0$ の $\omega$ モデルだが $\mathsf{ACA}_0$ のモデルではない(逆数学)。

標準でないモデル

二階算術のモデルは一意でない

次の 2 つが成り立つ。
(a) 意図されたモデルで真な $L_2$ の文をすべて満たし(とくに $\mathsf Z_2$ のモデルであり)、数の部分が $\omega$ と同型でない $L_2$ 構造がある。
(b) 意図されたモデルで真な $L_2$ の文をすべて満たす $\omega$ モデル $\mathcal S$ で、$\mathcal S$ が可算なもの(とくに $\mathcal S\neq\mathcal P(\omega)$)がある。

コンパクト性と Löwenheim–Skolem の定理

2 種類の変数をもつ言語は、数の元と集合の元を見分ける 1 変数の述語 $N,S$ を加えた 1 種類の変数の言語に直せる。量化 $\forall n$ を $\forall x\,(N(x)\to\cdots)$、$\forall X$ を $\forall x\,(S(x)\to\cdots)$ に替え、$\in$ を 2 項関係記号にすればよい。この翻訳で $L_2$ 構造と、$N,S$ が領域を分ける構造とが対応し、文の真偽も対応する。したがって一階の言語の コンパクト性定理(一階論理) と Löwenheim–Skolemの定理 が $L_2$ にも使える。$T$ を意図されたモデルで真な $L_2$ の文全体とする。
(a) 新しい数の定数 $c$ を加え、$T$ に文 $\underline k< c$($k=0,1,2,\dots$。$\underline k$ は $1+1+\cdots+1$ で $k$ を表す項)を加えた理論 $T'$ を考える。$T'$ の有限部分はある $K$ 未満の $\underline k$ についての文しか含まないので、意図されたモデルで $c$ を $K$ と解釈すれば満たされる。コンパクト性により $T'$ にはモデル $M$ がある。$M\models T$ である。もし数の部分 $(\lvert M\rvert,+_M,\cdot_M,0_M,1_M,<_M)$ が $(\omega,+,\cdot,0,1,<)$ と同型なら、$c_M$ はある自然数 $K$ に写るが、$M\models\underline K< c$ が同型で $K< K$ に写り矛盾する。
(b) 意図されたモデルを 1 種類の変数の構造とみて、その部分集合 $\omega$ を含む初等部分構造 $M'$ を Löwenheim–Skolemの定理(下方の形)でとり、$M'$ の濃度を $\lvert\omega\rvert=\aleph_0$ とする。$M'$ の数の部分は $\omega\subseteq M'$ かつ意図されたモデルの数の部分 $\omega$ に含まれるので $\omega$ そのもので、演算と順序は制限である。集合の部分 $\mathcal S:=M'\cap\mathcal P(\omega)$ は可算で、所属関係は本物の所属の制限である。したがって $M'$ は $\omega$ モデル $\mathcal S$ であり、初等部分構造なので $T$ の文をすべて満たす。$\mathcal P(\omega)$ は Cantor の定理により非可算なので $\mathcal S\neq\mathcal P(\omega)$ である。$\square$

(b) の $\mathcal S$ は意図されたモデルと同じ文を満たすので、$L_2$ の文では「集合の範囲が冪集合全体であること」を表せない。これが rem-soa-first-order で述べた、標準意味論の二階の Peano 算術(範疇的)との違いである。

β モデル

$\omega$ モデル $\mathcal S$ が $\beta$ モデルであるとは、$\mathcal S$ の元を母数とする任意の $\Sigma^1_1$ 文 $\sigma$ について、$\mathcal S\models\sigma$ と $\mathcal P(\omega)\models\sigma$ が同値であることをいう。

$\Pi^1_1$ 文は $\Sigma^1_1$ 文の否定と同値なので、$\Pi^1_1$ 文の真偽も一致する(Sim06 Definition I.5.3, p. 18 は $\Sigma^1_1$ と $\Pi^1_1$ の両方で定義している)。$\omega$ モデルはつねに算術的な文の真偽を意図されたモデルと共有するが、$\beta$ モデルは「集合が 1 つ存在するか」という一段上の問いでも嘘をつかないモデルである。

反例:β モデルでない ω モデル

計算可能集合全体の $\omega$ モデル $\mathrm{REC}$ は $\beta$ モデルでない。
0 と 1 の有限列を自然数で符号化し、弱Kőnigの補題 の定理「計算可能な道をもたない計算可能な木」により、計算可能な無限 2 分木 $T\subseteq2^{<\omega}$ で、計算可能な無限の道をもたないものをとる。$T$ は計算可能なので $T\in\mathrm{REC}$ である。集合 $X\subseteq\omega$ を特性関数 $\chi_X\colon\omega\to\{0,1\}$ と同一視し、
$$ \sigma:\equiv\exists X\,\forall n\,\bigl(\chi_X\restriction n\in T\bigr) $$
とおく。括弧の中は「長さ $n$ の列 $s$ で、すべての $i< n$ について $s(i)=1\leftrightarrow i\in X$ となるものの符号は $T$ に属する」と数の量化だけで書けるので、$\sigma$ は $T$ を母数とする $\Sigma^1_1$ 文である。
意図されたモデルでは、$T$ が無限の 2 分木なので 弱Kőnigの補題 により無限の道 $x\in2^\omega$ があり、$X:=\{i\mid x(i)=1\}$ が $\sigma$ を満たす。一方 $\mathrm{REC}$ で $\sigma$ が真なら、計算可能な $X$ で $\chi_X$ が $T$ の道になるものがあり、$T$ の選び方に反する。よって $\sigma$ は $\mathcal P(\omega)$ で真、$\mathrm{REC}$ で偽であり、$\mathrm{REC}$ は $\beta$ モデルの条件を満たさない。

β モデルと部分体系の強さ

各 $k\geq1$ について $\Pi^1_k\text{-}\mathsf{CA}_0$ には $\omega$ モデルとしての最小のものはないが、最小の $\beta$ モデルはある。$k=1$ では超算術的な還元と超ジャンプで書け、一般の $k$ では Gödel の構成可能階層の段階 $L_\alpha$ を使い、ある可算順序数 $\alpha_k$ について $L_{\alpha_k}\cap\mathcal P(\omega)$ の形になる。$\alpha_1<\alpha_2<\cdots$ でこれらは互いに異なり、ここから $\Pi^1_{k+1}\text{-}\mathsf{CA}_0$ が $\Pi^1_k\text{-}\mathsf{CA}_0$ より真に強いことが分かる(Sim06 Remarks I.5.4–I.5.5, pp. 18–19。この記事では証明しない)。$L_\alpha$ の定義は構成可能宇宙の記事で扱う。

二階算術の中の数学

$\mathsf Z_2$ の集合は自然数の集合だけだが、符号化によって多くの数学的対象を扱える(逆数学 の節「数学的対象のコード化」)。整数・有理数は自然数の対で、実数は収束の速さを指定した有理数の Cauchy 列で、完備可分距離空間はその可算稠密部分集合と距離の値で、連続関数は開球の像の情報を並べた集合で表す(Sim06 Definitions I.4.2–I.4.7, pp. 12–15)。$\mathsf Z_2$ の中で数学の一部を展開する道筋は Hilbert と Bernays がすでに描いており、その展開に実際にどれだけの内包が要るかを測るのが逆数学の計画である(Sim06 p. 6 の注)。
部分体系の強さは、数だけについての文で比べることもできる。$\mathsf{ACA}_0$ の定理のうち集合変数を含まない文は、ちょうど Peano算術 の定理である(保存拡大。Sim06 Remark I.3.3, p. 8。この記事では証明しない)。prop-soa-induction-scheme の証明で見たとおり、$\mathsf{ACA}_0$ は Peano 算術の帰納法の図式をすべて証明するので、片方の包含は易しい。一方 $\mathsf Z_2$ 自身は計算可能に公理化され Peano 算術を含むので、無矛盾なら Gödelの不完全性定理 により完全でない。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する