Peano算術

同義語：Peano arithmeticペアノ算術一階Peano算術

概要

前提知識: 一階述語論理, 自然数, 数学的帰納法

Peano算術（$\mathsf{PA}$）は、自然数の足し算・掛け算・大小についての基本的な公理に、数学的帰納法を論理式ごとの公理として加えた一階の理論である。整数論の初等的な議論の多くは $\mathsf{PA}$ の中で行えるので、「自然数についての証明」を形式的に扱うときの標準的な出発点になっている。
自然数の記事で扱う Peano 構造では、帰納法の条件が「すべての部分集合」について課され、そのような構造は同型を除いてただ一つに決まる。$\mathsf{PA}$ の帰納法は、一階の論理式で書ける性質についてだけ課される。この違いのために、$\mathsf{PA}$ は自然数全体 $\mathbb N$ 以外のモデル、すなわち $\mathbb N$ のどの元よりも大きい「非標準的な数」を含むモデルをもつ。しかも $\mathsf{PA}$ は、そうしたモデルの形をかなり強く縛っている。
この記事では、$\mathsf{PA}$ を定義し、足し算・掛け算・順序の基本法則が実際に $\mathsf{PA}$ から証明できることを確かめる。次に帰納法と最小数原理が同じ強さであることを示し、最後に $\mathsf{PA}$ のどの超準モデルも「$\mathbb N$ の後ろに $\mathbb Z$ の形のかたまりが稠密に並ぶ」形をしていることを証明する。

定義

算術の言語を $L_A=\{0,S,+,\cdot,<\}$ とする（$0$ は定数記号、$S$ は 1 変数の関数記号、$+$ と $\cdot$ は 2 変数の関数記号、$<$ は 2 変数の関係記号）。自然数 $n$ に対し、$S$ を $n$ 個並べた項 $S\cdots S0$ を $n$ の数項といい、$\underline n$ と書く。$\mathbb N$ に $0$、$n\mapsto n+1$、通常の和・積・大小を入れた構造を 標準モデル といい、$\mathfrak N$ と書く。

Peano算術

次の 8 個の文からなる理論を $\mathsf Q$（Robinson算術）という。

$\forall x\forall y\,(Sx=Sy\to x=y)$
$\forall x\,\lnot(0=Sx)$
$\forall x\,(\lnot x=0\to\exists y\,x=Sy)$
$\forall x\,(x+0=x)$
$\forall x\forall y\,(x+Sy=S(x+y))$
$\forall x\,(x\cdot0=0)$
$\forall x\forall y\,(x\cdot Sy=x\cdot y+x)$
$\forall x\forall y\,\bigl(x< y\leftrightarrow\exists z\,(Sz+x=y)\bigr)$
$L_A$ の各論理式 $\varphi(x,\vec u)$ に対する文
$$ \forall\vec u\,\Bigl(\bigl(\varphi(0,\vec u)\land\forall x\,(\varphi(x,\vec u)\to\varphi(Sx,\vec u))\bigr)\to\forall x\,\varphi(x,\vec u)\Bigr) $$
を 帰納法の公理、その全体を 帰納法の公理図式 という。$\mathsf Q$ に帰納法の公理図式を加えた理論を Peano算術（Peano arithmetic）といい、$\mathsf{PA}$ と書く。

公理 1〜3 は後者関数 $S$ が単射で $0$ を値にとらず、$0$ 以外はすべて後者であることを、4〜7 は和と積の再帰的な定義を、8 は大小関係を和で定義することを述べている。$\mathsf{PA}$ の公理はすべて $\mathfrak N$ で真なので、$\mathfrak N$ は $\mathsf{PA}$ のモデルであり、$\mathsf{PA}$ は無矛盾である（無矛盾性の例「Peano 算術」）。この定義は Gödelの不完全性定理の定義「Robinson の算術と Peano 算術」と同じものである。
帰納法の公理は論理式ごとに一つずつあるので、$\mathsf{PA}$ の公理は無限個ある。

基本法則の証明

以下、「$\mathsf{PA}$ で証明する」とは、自由変数を全称量化した文を $\mathsf{PA}$ から一階述語論理で導くことをいう。「$\varphi(x)$ についての帰納法」とは、論理式 $\varphi(x,\vec u)$ に対する帰納法の公理を使い、$\varphi(0)$ と $\varphi(x)\to\varphi(Sx)$ を示して $\forall x\,\varphi(x)$ を得ることをいう。$1:=S0$ とおき、$x\le y$ は $x< y\lor x=y$ の略記とする。

$\mathsf{PA}$ が証明する基本法則

次の文はすべて $\mathsf{PA}$ で証明できる（自由変数は全称量化されているとする）。
和　(A1) $0+x=x$　(A2) $Sx+y=S(x+y)$　(A3) $(x+y)+z=x+(y+z)$　(A4) $x+y=y+x$　(A5) $x+z=y+z\to x=y$　(A6) $x+Sz\neq x$、特に $Sx\neq x$
順序　(O1) $x< y\leftrightarrow\exists z\,(x+Sz=y)$　(O2) $\lnot\,x< x$　(O3) $x< y\land y< w\to x< w$　(O4) $x< y\lor x=y\lor y< x$　(O5) $\lnot\,x< 0$　(O6) $x< Sy\leftrightarrow x\le y$　(O7) $x\le y\leftrightarrow\exists d\,(x+d=y)$ で、その $d$ はただ一つ　(O8) $x+u< x+v\leftrightarrow u< v$
積　(M1) $0\cdot x=0$　(M2) $Sx\cdot y=x\cdot y+y$　(M3) $x\cdot y=y\cdot x$　(M4) $x\cdot(y+z)=x\cdot y+x\cdot z$　(M5) $(x\cdot y)\cdot z=x\cdot(y\cdot z)$
偶奇　(P) $\exists y\,(x=y+y\lor x=S(y+y))$

(A1)〜(A4) と (M1)〜(M5) は、和と積が可換半環をなすことを述べる（$1\cdot x=x$ は (M2) と (M1)・(A1) から従う）。(O2)〜(O4) は $<$ が線形順序であること、(O5)・(O6) は $0$ が最小元で $Sy$ が $y$ の直後の元であること（その間に元がないこと）を述べる。

一つずつ帰納法を使う

どの法則も、公理と先に示した法則だけを使い、帰納法を使うとしても一つの論理式についての帰納法を一回使うだけで示せる。和の法則 (A1)〜(A6) を先に示し、それを使って順序 (O1)〜(O8)、積 (M1)〜(M5)、偶奇 (P) の順に示す。

詳細

(A1) $x$ についての帰納法。$0+0=0$ は公理 4。$0+x=x$ なら $0+Sx=S(0+x)=Sx$（公理 5）。

(A2) $y$ についての帰納法。$Sx+0=Sx=S(x+0)$（公理 4）。$Sx+y=S(x+y)$ なら $Sx+Sy=S(Sx+y)=S(S(x+y))=S(x+Sy)$（公理 5 を 2 回）。

(A3) $z$ についての帰納法。$z=0$ では両辺とも $x+y$（公理 4）。$(x+y)+z=x+(y+z)$ なら $(x+y)+Sz=S((x+y)+z)=S(x+(y+z))=x+S(y+z)=x+(y+Sz)$（公理 5）。

(A4) $y$ についての帰納法。$x+0=x=0+x$（公理 4 と (A1)）。$x+y=y+x$ なら $x+Sy=S(x+y)=S(y+x)=Sy+x$（公理 5 と (A2)）。

(A5) 論理式 $\forall x\forall y\,(x+z=y+z\to x=y)$ についての $z$ の帰納法。$z=0$ は公理 4 から明らか。$x+Sz=y+Sz$ なら $S(x+z)=S(y+z)$ なので、公理 1 から $x+z=y+z$、帰納法の仮定から $x=y$。

(A6) 論理式 $\forall z\,(x+Sz\neq x)$ についての $x$ の帰納法。$0+Sz=Sz\neq0$（(A1) と公理 2）。$x+Sz\neq x$ とし、$Sx+Sz=Sx$ と仮定すると、(A2) から $S(x+Sz)=Sx$、公理 1 から $x+Sz=x$ となり矛盾する。$z=0$ とすると $x+S0=S(x+0)=Sx$ なので $Sx\neq x$。

(O1) 公理 8 と (A4) による。

(O2) $x< x$ なら (O1) から $x+Sz=x$ となり (A6) に反する。

(O3) $x+Sz=y$、$y+Sv=w$ なら (A3) と公理 5 から $x+S(Sz+v)=x+(Sz+Sv)=w$。

(O4) $y$ を固定し、$x$ についての帰納法。$x=0$ のとき、$y=0$ なら $x=y$、そうでなければ公理 3 で $y=Sv$ と書けて $0+Sv=y$、すなわち $0< y$。次に $x$ で成り立つとする。$y< x$ なら $y< Sx$（$y+Sz=x$ から $y+SSz=Sx$）。$x=y$ なら $y+S0=Sy=Sx$ なので $y< Sx$。$x< y$、すなわち $x+Sz=y$ のとき、$z=0$ なら $Sx=y$、$z=Sv$ なら $Sx+Sv=S(x+Sv)=x+Sz=y$（(A2)、公理 5）なので $Sx< y$。

(O5) $x< 0$ なら $x+Sz=S(x+z)=0$ となり公理 2 に反する。

(O6) $x< y$、$x+Sz=y$ なら $x+SSz=Sy$ なので $x< Sy$。$x=y$ なら $x+S0=Sy$。逆に $x+Sz=Sy$ なら $S(x+z)=Sy$、公理 1 から $x+z=y$。$z=0$ なら $x=y$、そうでなければ公理 3 で $z=Sv$ となり $x< y$。

(O7) $x< y$ なら (O1) の $Sz$、$x=y$ なら $0$ が $d$ になる。逆に $x+d=y$ で $d\neq0$ なら $d=Sz$ として $x< y$。一意性は (A4) と (A5) による。

(O8) (A3)・(A4)・(A5) により $x+u+Sz=x+v\iff u+Sz=v$ なので、(O1) から従う。

(M1) $x$ についての帰納法。$0\cdot0=0$（公理 6）。$0\cdot x=0$ なら $0\cdot Sx=0\cdot x+0=0$（公理 7、4）。

(M2) $y$ についての帰納法。$y=0$ では両辺とも $0$（公理 6、4）。$Sx\cdot y=x\cdot y+y$ なら $Sx\cdot Sy=Sx\cdot y+Sx=(x\cdot y+y)+Sx$、$x\cdot Sy+Sy=(x\cdot y+x)+Sy$ であり、公理 5 と (A4) から $y+Sx=S(y+x)=S(x+y)=x+Sy$ なので、(A3) により両者は等しい。

(M3) $y$ についての帰納法。$x\cdot0=0=0\cdot x$（(M1)）。$x\cdot y=y\cdot x$ なら $x\cdot Sy=x\cdot y+x=y\cdot x+x=Sy\cdot x$（(M2)）。

(M4) $z$ についての帰納法。$z=0$ は公理 4、6 から。成り立てば $x\cdot(y+Sz)=x\cdot S(y+z)=x\cdot(y+z)+x=(x\cdot y+x\cdot z)+x=x\cdot y+x\cdot Sz$（公理 5、7、(A3)）。

(M5) $z$ についての帰納法。$z=0$ では両辺とも $0$。成り立てば $(x\cdot y)\cdot Sz=(x\cdot y)\cdot z+x\cdot y=x\cdot(y\cdot z)+x\cdot y=x\cdot(y\cdot z+y)=x\cdot(y\cdot Sz)$（公理 7、(M4)）。

(P) $x$ についての帰納法。$0=0+0$。$x=y+y$ なら $Sx=S(y+y)$。$x=S(y+y)$ なら、(A2) と公理 5 から $Sy+Sy=S(Sy+y)=S(S(y+y))=Sx$。$\square$

これらの証明は、どれも帰納法を高々一回使う短いものだが、$\mathsf Q$ だけでは証明できないものがある。たとえば $\mathsf Q$ は $x+y=y+x$ を証明しない（OLT26 Example 26.9、Robinson算術の例「和が可換でない $\mathsf Q$ のモデル」）。帰納法の公理図式が $\mathsf{PA}$ の強さの源である。

帰納法と最小数原理

数学的帰納法の記事では、自然数について帰納法の原理と整列原理（空でない部分集合は最小元をもつ）が同値であることを示している。$\mathsf{PA}$ でも、論理式ごとに同じことが成り立つ。論理式 $\varphi(x,\vec u)$ に対する 最小数原理 とは、文
$$ \forall\vec u\,\Bigl(\exists x\,\varphi(x,\vec u)\to\exists x\,\bigl(\varphi(x,\vec u)\land\forall y\,(y< x\to\lnot\varphi(y,\vec u))\bigr)\Bigr) $$
のことである。比べるための土台として、$\mathsf Q$ に (O6) の文 $\forall x\forall y\,(x< Sy\leftrightarrow x\le y)$ を加えた理論を $\mathsf B$ とおく。

最小数原理との同値

各論理式 $\varphi$ について、$\mathsf B$ と論理式 $\psi(x,\vec u):=\forall y\,(y< x\to\lnot\varphi(y,\vec u))$ に対する帰納法の公理から、$\varphi$ に対する最小数原理が証明できる。
各論理式 $\varphi$ について、$\mathsf B$ と $\lnot\varphi$ に対する最小数原理から、$\varphi$ に対する帰納法の公理が証明できる。
したがって $\mathsf{PA}$ と、$\mathsf B$ にすべての最小数原理を加えた理論とは、証明できる文が同じである。

最小元のない性質は下から否定される

パラメータ $\vec u$ は省略する。まず $\mathsf Q\vdash\lnot\,x< 0$ に注意する。$x< 0$ なら公理 8 から $Sz+x=0$ となる $z$ があるが、公理 3 により $x=0$ なら $Sz+0=Sz$、$x=Sw$ なら $Sz+Sw=S(Sz+w)$ で、どちらも公理 2 により $0$ でない。

$\exists x\,\varphi(x)$ を仮定し、$\varphi$ を満たす最小の元がないと仮定する。$\psi(0)$ は $\lnot\,y< 0$ から成り立つ。$\psi(x)$ を仮定し、$y< Sx$ とすると $\mathsf B$ の公理から $y< x$ または $y=x$ である。$y< x$ なら $\psi(x)$ から $\lnot\varphi(y)$。$y=x$ のとき、$\varphi(x)$ なら $\psi(x)$ と合わせて $x$ が $\varphi$ を満たす最小の元になるので、仮定から $\lnot\varphi(x)$。よって $\psi(Sx)$。帰納法の公理から $\forall x\,\psi(x)$ である。任意の $a$ について、$\mathsf B$ の公理（$x=y$ の場合）から $a< Sa$ であり、$\psi(Sa)$ から $\lnot\varphi(a)$ となる。これは $\exists x\,\varphi(x)$ に反する。
$\varphi(0)$ と $\forall x\,(\varphi(x)\to\varphi(Sx))$ を仮定し、$\lnot\varphi(a)$ となる $a$ があるとする。$\lnot\varphi$ に対する最小数原理から、$\lnot\varphi(b)$ かつ $y< b$ ならつねに $\varphi(y)$ となる $b$ がとれる。$\varphi(0)$ なので $b\neq0$、公理 3 で $b=Sc$ と書ける。$\mathsf B$ の公理から $c< Sc=b$ なので $\varphi(c)$、仮定から $\varphi(Sc)=\varphi(b)$ となり矛盾する。よって $\forall x\,\varphi(x)$。
$\mathsf{PA}$ は (O6) により $\mathsf B$ の公理を証明し、1 によりすべての最小数原理を証明する。逆に、$\mathsf B$ にすべての最小数原理を加えた理論は、2 によりすべての帰納法の公理を証明し、$\mathsf Q\subset\mathsf B$ なので $\mathsf{PA}$ の公理をすべて証明する。$\square$

1 の証明は、$\varphi$ そのものではなく別の論理式 $\psi$ に帰納法を使っている。

$\mathsf{PA}$ のモデル

$\mathsf{PA}$ の公理をすべて満たす $L_A$-構造を $\mathsf{PA}$ のモデルという。モデル $\mathcal M$ の元のうち、ある数項の値 $\underline n^{\mathcal M}$ になっているものを 標準元、そうでないものを 非標準元 といい、非標準元をもつモデルを 超準モデル という（超準モデル）。以下、モデルの中の演算も $S,+,\cdot,<$ と書き、$\underline n^{\mathcal M}$ を単に $\underline n$ と書く。

数項の計算

自然数 $m,n$ について次が成り立つ。

$\mathsf Q\vdash\underline m+\underline n=\underline{m+n}$、$\mathsf Q\vdash\underline m\cdot\underline n=\underline{mn}$。
$m\neq n$ なら $\mathsf Q\vdash\underline m\neq\underline n$。
$\mathsf{PA}\vdash\forall x\,\bigl(x<\underline n\to x=\underline0\lor x=\underline1\lor\cdots\lor x=\underline{n-1}\bigr)$（$n=0$ では右辺を偽とする）。

1・2 は自然数 $n$（または $m$）についての理論の外での帰納法で、公理 1〜7 を繰り返し使う。3 は (O5)・(O6) からの帰納法である。

詳細

1. 和は $n$ についての（理論の外での）帰納法による。$n=0$ は公理 4。$\underline m+\underline{n+1}=\underline m+S\underline n=S(\underline m+\underline n)=S\underline{m+n}=\underline{m+n+1}$（公理 5）。積も同様に、公理 6 と、公理 7 から $\underline m\cdot S\underline n=\underline m\cdot\underline n+\underline m=\underline{mn}+\underline m=\underline{mn+m}$（和の場合を使う）。

2. $m< n$ としてよく、$m$ についての帰納法による。$m=0$ なら $\underline n=S\underline{n-1}\neq0$（公理 2）。$m>0$ なら $\underline m=S\underline{m-1}$、$\underline n=S\underline{n-1}$ で、公理 1 により $\underline m=\underline n$ から $\underline{m-1}=\underline{n-1}$ が出るので、帰納法の仮定に帰着する。

3. $n$ についての帰納法による。$n=0$ は (O5)。$x< S\underline n$ なら (O6) から $x<\underline n$ または $x=\underline n$ で、前者には帰納法の仮定を使う。$\square$

1・2 から、$n\mapsto\underline n^{\mathcal M}$ は $\mathfrak N$ から $\mathcal M$ への単射で $S,+,\cdot$ を保ち、(O1) により $<$ も保つ。したがって標準元全体は $\mathcal M$ の中の $\mathfrak N$ の写しである。すべての元が標準元なら、この写像は同型 $\mathfrak N\cong\mathcal M$ になる。

超準モデルの存在

$\mathsf{PA}$ の可算な超準モデルが存在する。

どの数項よりも大きい新しい定数を加えた理論にコンパクト性定理を使う。

詳細

新しい定数記号 $c$ を加え、$T:=\mathsf{PA}\cup\{\underline n< c\mid n\in\mathbb N\}$ とおく。$T$ の有限部分集合は、$c$ を十分大きな自然数と解釈した $\mathfrak N$ で満たされる。コンパクト性定理(一階論理)の定理「一階論理のコンパクト性定理」により $T$ はモデル $\mathcal M$ をもち、言語は可算なので Löwenheim–Skolemの定理により $\mathcal M$ は可算としてよい。$c^{\mathcal M}=\underline m$ なら $\underline m<\underline m$ となって (O2) に反するので、$c^{\mathcal M}$ は非標準元である。$\square$

超準モデルの順序の形

$\mathcal M$ を $\mathsf{PA}$ のモデルとする。$a,b\in\mathcal M$ について、ある自然数 $n$ で $b=a+\underline n$ または $a=b+\underline n$ となるとき $a\sim b$ と書く。$a$ の同値類（下で同値関係であることを示す）を $a$ の ブロック といい、$[a]$ と書く。$a$ から後者と「前者」を有限回たどって行ける元の全体である。

$\mathsf{PA}$ の超準モデルの順序

$\mathcal M$ を $\mathsf{PA}$ のモデルとする。

標準元はすべての非標準元より小さい。
$\sim$ は同値関係である。$a$ が非標準元なら、$k\mapsto a+\underline k$（$k\ge0$）、$-k\mapsto$「$d+\underline k=a$ となるただ一つの $d$」（$k>0$）は $\mathbb Z$ から $[a]$ への順序同型である。
$a< b$ かつ $a\not\sim b$ なら、$[a]$ のすべての元は $[b]$ のすべての元より小さい。したがってブロックの全体は線形順序をなす。
非標準元のブロックのうちに最小のもの・最大のものはなく、$a< b$ が異なるブロックにあれば、その間にどちらとも異なるブロック $[c]$ がある。

半分にして間を見つける

1。 $a$ を非標準元、$n\in\mathbb N$ とする。(O4) から $a<\underline n$、$a=\underline n$、$\underline n< a$ のいずれかである。$a<\underline n$ なら prop-pa-numerals の 3 により $a$ はある $\underline k$ に等しく、$a=\underline n$ と同様に非標準であることに反する。よって $\underline n< a$。
2。反射律は公理 4、対称律は定義から明らか。推移律：$a\sim b$、$b\sim c$ とする。$b=a+\underline m$ かつ $c=b+\underline n$ なら (A3) と prop-pa-numerals の 1 から $c=a+\underline{m+n}$。$a=b+\underline m$ かつ $b=c+\underline n$ も同様。$b=a+\underline m=c+\underline n$ なら、$m\ge n$ のとき $\underline m=\underline{m-n}+\underline n$ なので (A5) から $c=a+\underline{m-n}$、$m< n$ のとき $a=c+\underline{n-m}$。$a=b+\underline m$ かつ $c=b+\underline n$ も同様に $a\sim c$ となる。
次に $a$ を非標準元とする。1 により各 $k$ で $\underline k< a$ なので、(O7) により $d+\underline k=a$ となる $d$ がただ一つあり、これを $a-\underline k$ と書く。$\iota(k):=a+\underline k$（$k\ge0$）、$\iota(-k):=a-\underline k$ とおくと、ブロックの定義から $\iota$ は $\mathbb Z$ から $[a]$ への全射である。$k< l$ のとき $\iota(l)=\iota(k)+\underline{l-k}$ であることを示せば、$l-k\ge1$ と (O1) から $\iota(k)<\iota(l)$ となり、$\iota$ は順序同型である。$0\le k$ なら $a+\underline l=(a+\underline k)+\underline{l-k}$。$k<0\le l$ なら $(a-\underline{-k})+\underline{l-k}=(a-\underline{-k})+\underline{-k}+\underline l=a+\underline l$。$k< l<0$ なら $\iota(k)+\underline{l-k}+\underline{-l}=\iota(k)+\underline{-k}=a=\iota(l)+\underline{-l}$ なので (A5) から従う。
3。まず、$a< b$、$a\not\sim b$ なら、すべての $n$ で $a+\underline n< b$ であることを示す。(O7) から $b=a+e$ と書ける。$e$ が標準元 $\underline k$ なら $a\sim b$ となるので、$e$ は非標準元であり、1 から $\underline n< e$、(O8) から $a+\underline n< a+e=b$。
$u\in[a]$、$v\in[b]$ とする。$a\not\sim b$ なので $u\neq v$ である。$v< u$ と仮定すると $v\not\sim u$ なので、いま示したことから、すべての $k$ で $v+\underline k< u$。一方、$u\sim a$ から $u\le a+\underline n$ となる $n$ があり（$u=a+\underline n$ の場合と、$a=u+\underline n$ から (O7) で $u\le a$ となる場合）、同様に $b\le v+\underline m$ となる $m$ がある。すると $b\le v+\underline m< u\le a+\underline n$ となり、$a+\underline n< b$ と (O2)・(O3) に反する。よって $u< v$。
4。準備として、$x$ が非標準元なら、$x=y+y$ または $x=S(y+y)$ となる $y$（(P)）も非標準元であることに注意する。$y=\underline k$ なら prop-pa-numerals の 1 から $x=\underline{2k}$ または $\underline{2k+1}$ となるからである。また、$x$ が非標準元なら $Sx$ も非標準元である（$Sx=\underline n$ なら $n\ge1$ で、公理 1 から $x=\underline{n-1}$）。
最小のブロックはない。 $a$ を非標準元とし、$a=d+e$（$e=d$ または $e=Sd$）と書く（(P) と (A2)・公理 5 による）。$d,e$ は非標準元で、特に $e\neq0$ なので $d< a$。$d\sim a$ なら $a=d+\underline n$ となり（$d+\underline n=a$ の向きしかない）、(A5) から $e=\underline n$ となって矛盾する。よって $[d]$ は $[a]$ より前の非標準のブロックである。
最大のブロックはない。 $a$ を非標準元とすると $a\neq0$ なので $a< a+a$。$a\sim a+a$ なら $a+a=a+\underline n$、(A5) から $a=\underline n$ となり矛盾する。
ブロックは稠密に並ぶ。 $a< b$、$a\not\sim b$ とする。3 の証明のとおり $b=a+e$ で $e$ は非標準元である。$e=f+f$ または $e=S(f+f)$ とし、$c:=a+f$ とおく。$f$ は非標準元なので $a< c$ で、$c\sim a$ なら $c=a+\underline n$、(A5) から $f=\underline n$ となって矛盾する。また (A3)・公理 5 から $b=c+f$ または $b=c+Sf$ であり、$f$ と $Sf$ はどちらも非標準元なので、同じ議論で $c< b$ かつ $c\not\sim b$。3 により $[a]$、$[c]$、$[b]$ はこの順に並ぶ相異なるブロックである。$\square$

標準元は 1 によりすべて先頭に並び、prop-pa-numerals によって $\mathbb N$ と同じ形をしている。したがって $\mathcal M$ の順序は、「$\mathbb N$ のあとに、$\mathbb Z$ の形のブロックが、最小も最大もなく稠密に並ぶ」形をしている。

可算な超準モデルの順序型

$\mathcal M$ が $\mathsf{PA}$ の可算な超準モデルなら、$(\mathcal M,<)$ は、$\mathbb N$ のあとに $\mathbb Q\times\mathbb Z$ を辞書式順序で並べた順序と同型である。

非標準元のブロックの全体は空でなく可算で、thm-pa-order の 3・4 により最小元も最大元もない稠密な線形順序である。可算で端点のない稠密な線形順序はすべて $(\mathbb Q,<)$ と同型である（Cantor の定理。OLT26 Theorem 25.26。この記事では証明しない）。この同型と、各ブロックの $\mathbb Z$ との順序同型（thm-pa-order の 2）、標準元と $\mathbb N$ の対応（thm-pa-order の 1 と prop-pa-numerals）を合わせればよい。$\square$

超準モデルの定理「超準モデルの順序型」は、$\mathbb N$ で真な文をすべて満たすモデルについて同じ形を示している。thm-pa-order は、それを $\mathsf{PA}$ の公理だけから導いたものである。

標準元は論理式で切り出せない

オーバースピル

$\mathcal M$ を $\mathsf{PA}$ の超準モデル、$\varphi(x,\vec p)$ を $\mathcal M$ の元をパラメータにもつ論理式とする。すべての $n\in\mathbb N$ について $\mathcal M\models\varphi(\underline n,\vec p)$ なら、$\mathcal M\models\varphi(a,\vec p)$ となる非標準元 $a$ がある。特に、標準元全体はどの論理式でも定義できない。

$\varphi$ を満たす元がちょうど標準元だけだと仮定する。$\underline0$ は標準元なので $\varphi(0)$。$\varphi(x)$ なら $x=\underline n$ と書けて $Sx=\underline{n+1}$ も標準元なので $\varphi(Sx)$。帰納法の公理から $\mathcal M\models\forall x\,\varphi(x)$ となり、非標準元も $\varphi$ を満たして仮定に反する。後半は、定義する論理式があれば前半に反することによる。$\square$

「$x$ は標準的な数である」という性質は、$\mathcal M$ の外から見れば明確だが、$\mathsf{PA}$ の言葉では書けない。帰納法の公理図式が「論理式で定まる性質」にしか効かないことの現れである。

例

偽の文が成り立つ超準モデル

Gödelの不完全性定理の系「算術への帰結」により、$\mathfrak N$ で真だが $\mathsf{PA}$ から証明できない文 $G_{\mathsf{PA}}$ がある。$\mathsf{PA}\nvdash G_{\mathsf{PA}}$ なので理論 $\mathsf{PA}\cup\{\lnot G_{\mathsf{PA}}\}$ は無矛盾であり、Gödelの完全性定理によりモデル $\mathcal M$ をもつ。$\mathcal M$ のすべての元が標準元なら、prop-pa-numerals のあとの注意により $\mathcal M\cong\mathfrak N$ となり $\mathcal M\models G_{\mathsf{PA}}$ となるので、$\mathcal M$ は超準モデルである。このように、$\mathsf{PA}$ の超準モデルには、$\mathfrak N$ と同じ文を満たすもの（超準モデルの定理「算術の超準モデルの存在」）と、$\mathfrak N$ で偽の文を満たすものがある。

$\mathsf Q$ のモデルで $\mathsf{PA}$ のモデルでないもの

$\mathbb N$ に一つの元 $a$ を付け加え、$S(a)=a$、$a$ が関わる和は $a$、積は一方が $0$ なら $0$ でそれ以外は $a$、順序は $\mathbb N$ の上で通常どおりに加えてすべての $x$ について $x< a$ とした構造 $K$ は、$\mathsf Q$ のモデルである（OLT26 Example 26.8、超準モデルの例「非標準元が一つだけの Q のモデル」）。$K$ では $S(a)=a$ なので (A6) が偽であり、$K$ は $\mathsf{PA}$ のモデルでない。$a$ のブロックは $\{a\}$ だけで、thm-pa-order の 2 も成り立たない。(A6) の特別な場合 $\forall x\,\lnot(x=Sx)$ が $\mathsf Q$ から独立で $\mathsf{PA}$ から証明できることは、Gödelの不完全性定理の例「「$x=Sx$ となる $x$ はない」という文」でも扱われている。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
帰納法の公理図式	ex-pa-q-model の $K$	(A6) $Sx\neq x$、ブロックが $\mathbb Z$ の形であること
公理 1（$S$ は単射）	$\{0,1\}$ で $S(0)=S(1)=1$、和は $\min(x+y,1)$、積は通常の積	(O2) $\lnot\,x< x$（$1< 1$ が成り立つ）
公理 2（$0$ は後者でない）	$\mathbb Z/n\mathbb Z$（$n\ge1$）で $S(x)=x+1$、和と積は剰余で計算	(O2) $\lnot\,x< x$、モデルが無限であること
帰納法を一階の論理式で書ける性質に限らない	$\mathsf{PA}$ の超準モデル（prop-pa-nonstandard-exists）	$\mathfrak N$ との同型（二階の Peano 構造の範疇性）

反例の確かめ

2 行目と 3 行目の構造では、$<$ を公理 8 の右辺 $\exists z\,(Sz+x=y)$ で解釈する。どちらの構造でもすべての元がある数項の値なので、$\varphi(0)$ と $\forall x\,(\varphi(x)\to\varphi(Sx))$ が成り立てばすべての元が $\varphi$ を満たし、帰納法の公理はすべて成り立つ。
各行の確かめ。

詳細

2 行目：公理 2（$S(x)=1\neq0$）、公理 3（$0$ でない元は $1=S(0)$）、公理 4、6 は明らかである。公理 5：$x+S(y)=x+1=1$、$S(x+y)=1$。公理 7：$x\cdot S(y)=x$ で、$x\cdot y+x$ は $x=0$ なら $0$、$x=1$ なら $\min(y+1,1)=1$。公理 8 の右辺は $1+x=y$、すなわち $y=1$ と同値で、これが $<$ の解釈である。$S(0)=S(1)$ なので公理 1 だけが成り立たず、$1< 1$ が成り立つ。

3 行目：$S$ は全単射なので公理 1・3 が成り立ち、公理 4〜7 は剰余環の等式である。公理 8 の右辺は $z=y-x-1$ でいつも満たされるので、$<$ はすべての組で成り立つ。$S(n-1)=0$ なので公理 2 だけが成り立たず、$x< x$ が成り立ち、モデルは $n$ 個の元しかない。

4 行目：二階の Peano 構造は同型を除いてただ一つで $\mathfrak N$ と同型になる（自然数の定理「Peano構造の範疇性」）。一階の $\mathsf{PA}$ の超準モデルは、非標準元が $\mathbb N$ のどの元の像にもならないので $\mathfrak N$ と同型でない。$\mathcal M$ の標準元全体は $0$ を含み $S$ で閉じた部分集合だが、prop-pa-overspill によりどの論理式でも定義できないので、帰納法の公理が適用されない。

補足

二階の Peano 構造との関係

自然数の記事の Peano 構造は、帰納法を「すべての部分集合」について課すので、同型を除いて一つに決まる。$\mathsf{PA}$ は同じ発想を一階の論理式で書ける範囲に制限したもので、その代わりに証明や証明可能性を有限の記号列として扱える。両者の違いは自然数の「一階と二階で量化範囲が違う」節でも説明されている。

不完全性定理との関係

$\mathsf{PA}$ は $\mathsf Q$ を含み、公理の集合が機械的に判定でき、$\mathfrak N$ をモデルにもつ。したがって Gödelの不完全性定理がそのまま当てはまり、$\mathsf{PA}$ から独立な文がある。$\mathsf{PA}$ の無矛盾性は $\mathfrak N$ がモデルであることから分かるが（無矛盾性の例「Peano 算術」）、この議論は $\mathbb N$ を集合として扱える $\mathsf{PA}$ より強い体系の中で行われる。

参照箇所

OLT26 Definition 33.5（p. 524、$\mathsf Q$）、Definition 33.6（p. 525、帰納法の公理図式と $\mathsf{PA}$）。Example 26.8（pp. 397–398、$\mathsf Q$ のモデル $K$）、Example 26.9（p. 398、和が可換でない $\mathsf Q$ のモデル）。Propositions 26.10–26.19（pp. 399–401、$\mathsf{PA}$ のモデルの順序とブロック。同書では $\mathsf{PA}$ で証明できる事実の導出を省いている）。Theorem 25.26（p. 390、可算な稠密線形順序の一意性）。