§E16.15Robinson 算術 Q と Peano 算術 PA

証明. 任意の$m,n\in\mathbb N$を取る。通常の自然数では後続者$m+1$は$0$ではないので (Q1) が成り立つ。$m+1=n+1$なら$m=n$なので (Q2) が成り立つ。$m=0$であるか、$m>0$なら$m=(m-1)+1$であるから、 (Q3) も成り立つ。

通常の加法の定義から$m+0=m$および$m+(n+1)=(m+n)+1$であり、(Q4) と (Q5) が成り立つ。通常の乗法の定義から$m\times0=0$および$m\times(n+1)=(m\times n)+m$であり、(Q6) と (Q7) が成り立つ。各確認は任意の$m,n$について成り立つので、七式の全称閉包を$\mathbb N$がすべて満たす。したがって$\mathbb N\models Q$である。▨

証明.定理 2.2により$\mathbb N$は$Q$の七公理を満たす。任意の$L_A$論理式$\varphi(x,\vec z)$と、パラメータ$\vec z$への任意の割当て$\vec a$を固定する。対応する帰納法公理の前件が$\mathbb N$で真であると仮定する。すなわち、

とする。メタ理論における自然数$n$に関する帰納法を用いる。基底$n=0$では第1の仮定から$\mathbb N\models\varphi(\overline0,\vec a)$である。$\mathbb N\models\varphi(\overline n,\vec a)$と仮定すると、第2の仮定を$n$に適用して$\mathbb N\models\varphi(\overline{n+1},\vec a)$を得る。したがってすべての$n\in\mathbb N$について$\mathbb N\models\varphi(\overline n,\vec a)$である。$\mathbb N$の各要素はただ一つの標準自然数$n$なので、$\mathbb N\models\forall x\,\varphi(x,\vec a)$となる。

よって帰納法公理の前件が真なら結論も真である。$\varphi$と$\vec a$は任意だったので、$\mathbb N$は帰納法公理スキーマのすべての例を満たす。したがって$\mathbb N\models PA$である。▨

証明.$n$を固定した有限回の書換えを行う。加法では (Q4) により$Q\vdash\overline m+\overline0=\overline m$である。 (Q5) を$n$回適用すると

を得る。これは対象理論内の帰納法ではなく、固定した$n$に応じて作る有限導出である。乗法も (Q6) から始め、(Q7) を$n$回適用し、既に得た加法の計算を各段で用いれば$Q\vdash\overline m\times\overline n=\overline{mn}$を得る。

$m<n$なら$n=m+(d+1)$を満たす標準自然数$d$が存在する。加法の計算により$Q\vdash\overline n=\overline m+S\overline d$なので、$<$の定義へ存在導入して$Q\vdash\overline m<\overline n$を得る。

$m\ne n$とする。一般性を失わず$m<n$としてよい。$\overline m=\overline n$を仮定し、両辺から共通する$m$個の$S$を (Q2) で順に除くと$0=S^{n-m}0$を得る。最後の式は (Q1) に反する。したがって$Q\vdash\overline m\ne\overline n$である。$m>n$の場合も左右を交換した同じ有限導出による。▨