自然数(natural number)とは、$0$ から始めて後者を繰り返すことで得られる数であり、$0$ を含める流儀では自然数全体を $\mathbb{N}=\{0,1,2,\dots\}$ と書く。二階のPeano構造は、$0$ が後者でなく、後者写像が単射で、$0$ を含み後者で閉じた部分集合が全体に限るという条件で特徴づけられ、同型を除いて一意である。集合論では $0=\emptyset$、$n+1=n\cup\{n\}$ とする von Neumann 自然数がその実現であり、一階Peano算術は超準モデルをもつ点で二階の特徴づけと異なる。
おおまかには、自然数とは $0$ から出発して「次の数」を取る操作を繰り返すと得られる数 $0,1,2,\dots$ のことである。この記事では、この見方を始点と後者という二つのデータとそれに課す三条件(Peano構造)として定式化する。個数を数える、数学的帰納法で議論する、といった場面の土台になる。たとえば非負偶数 $0,2,4,\dots$ も、始点 $0$ と「$2$ を足す」操作でこの構造をなす。
本記事では $0$ を自然数に含め、自然数全体を $\mathbb N=\{0,1,2,\dots\}$ と書く。分野や文献によっては $1,2,\dots$ だけを自然数と呼ぶので、流儀が重要な場面では「非負整数」「正整数」と明記するのが安全である。
集合 $N$、元 $0_N\in N$、写像 $s\colon N\to N$ の組 $(N,0_N,s)$ が次を満たすとき、Peano構造という。
第3条件は「$0_N$ を含み、後者を取る操作で閉じた部分集合は $N$ 全体しかない」と述べる。したがって余分な元を付け加えることはできない。ここで定めた二階の構造条件と、一階述語論理の公理系である Peano 算術 $\mathsf{PA}$ は区別しなければならない。二階の Peano 構造は同型を除いて一意だが、一階理論 $\mathsf{PA}$ には標準的な $\mathbb N$ と同型でないモデルが存在する。
$0$ から始めて後者を繰り返すと
$$
0_N,\ s(0_N),\ s^2(0_N),\dots
$$
が得られる。第1条件は列が $0_N$ へ戻らないこと、第2条件は異なる位置が後者を取った途端に合流しないこと、第3条件はこの列の外に元が残らないことを表す。自然数は特定の記号や集合としてではなく、この「始点と後者」の構造によって特徴づけられる。
$0:=\emptyset$ とし、$s(n):=n\cup\{n\}$ と置く。$0$ を含み $s$ で閉じる最小の帰納的集合を $\omega$ と書けば、
$$
0=\emptyset,\quad 1=\{0\},\quad 2=\{0,1\},\quad 3=\{0,1,2\},\dots
$$
となる。通常の集合論では $(\omega,0,s)$ を自然数の標準的実現として用いる。この実現では各自然数 $n$ は、それより小さい自然数全体の集合でもある。
記号 $z$ から始め、$u$ が記号列なら $Su$ も記号列とする。こうして得られる有限列
$$
z,\ Sz,\ SSz,\dots
$$
の集合に、基点 $z$ と後者写像 $u\mapsto Su$ を入れると Peano 構造になる。これは自然数を集合として実装せず、形式記号として実装した例である。
非負偶数全体 $E=\{0,2,4,\dots\}$ に基点 $0$ と後者 $s_E(m)=m+2$ を入れると Peano 構造になる。写像
$$
\varphi\colon\mathbb N\longrightarrow E,\qquad \varphi(n)=2n
$$
は $\varphi(0)=0$ と $\varphi(n+1)=s_E(\varphi(n))$ を満たす同型である。元の名前が異なっても、始点と後者の構造は同じである。
$\mathbb Z$ に基点 $0$ と写像 $s(m)=m+1$ を入れても Peano 構造にはならない。実際、$s(-1)=0$ なので $0\in s(\mathbb Z)$ となり、第1条件を満たさない。さらに $\mathbb Z$ には $0$ から後者を有限回取って到達できない負の整数がある。
Peano構造 $(N,0_N,s)$ では
$$
N=\{0_N\}\sqcup s(N)
$$
である。したがって $0_N$ でない各元 $n\in N$ には、$s(m)=n$ を満たす元 $m$ がただ一つ存在する。
$A:=\{0_N\}\cup s(N)$ と置く。$0_N\in A$ であり、任意の $a\in A$ に対して $s(a)\in s(N)\subseteq A$ だから $s(A)\subseteq A$ である。帰納法条件より $A=N$ を得る。第1条件により $\{0_N\}\cap s(N)=\emptyset$ である。また $s(m)=s(m')$ なら第2条件から $m=m'$ なので、前者は一意である。$\square$
Peano構造 $(N,0_N,s)$ の任意の $n\in N$ と任意の正整数 $k$ に対し、$s^k(n)\ne n$ である。特に $s$ は不動点をもたない。
$k\ge1$ を固定し、$A:=\{n\in N\mid s^k(n)\ne n\}$ と置く。もし $s^k(0_N)=0_N$ なら $0_N=s(s^{k-1}(0_N))\in s(N)$ となり第1条件に反するので、$0_N\in A$ である。$n\in A$ とし、$s^k(s(n))=s(n)$ と仮定すると、$s$ の単射性から $s^k(n)=n$ となって矛盾する。よって $s(A)\subseteq A$ であり、帰納法条件から $A=N$ である。$\square$
二つの Peano 構造 $(N,0_N,s)$ と $(M,0_M,t)$ の間には、
$$
F(0_N)=0_M,\qquad F(s(n))=t(F(n))
$$
を満たす同型 $F\colon N\to M$ がただ一つ存在する。
通常の集合論では再帰定理により $F(s^n(0_N)):=t^n(0_M)$ と定め、両構造の帰納法条件を使って全射性・単射性・一意性を示す。通常の集合論での具体的な構成は後節で証明する。弱い公理系での分析は SY13 §§1–3 を参照。ここでいう範疇性は、すべての部分集合を量化する帰納法条件についての主張であり、一階理論 $\mathsf{PA}$ の範疇性を主張するものではない。
後者を使う再帰により、加法と乗法を
$$
m+0=m,\qquad m+s(n)=s(m+n),
$$
$$
m\cdot0=0,\qquad m\cdot s(n)=m\cdot n+m
$$
で定められる。順序も $m\le n$ を「ある $k$ が存在して $m+k=n$」と定めれば得られる。このため、始点と後者だけの構造から通常の自然数算術が回収できる。
本記事の $\mathbb N$ は $0$ を含む。この流儀では $(\mathbb N,+)$ が単位元 $0$ をもつ可換モノイドになり、有限集合の濃度や列の添字に使いやすい。一方、初等整数論などでは自然数を $\{1,2,3,\dots\}$ とすることもある。どちらが数学的に正しいという違いではなく、記号を使う際に宣言すべき規約の違いである。
弱い二階算術(二階算術 の部分体系)の内部では、必要な集合や再帰関数が自動的に存在するとは限らない。そのため、通常の集合論では同じに見える範疇性の諸形式が異なる強さをもつ。
Peano システム $(A,i,f)$ が標準系 $(\mathbb N,0,S)$ にほとんど同型であるとは、任意の $a\in A$ に対し、ある $n\in\mathbb N$ が存在して $f^n(i)=a$ となることをいう。
$\mathsf{RCA}_0^*$ の内部では反復写像 $n\mapsto f^n(i)$ の存在をあらかじめ仮定できないため、この条件は「$a_0=i$、$a_n=a$、$a_{m+1}=f(a_m)$ を満たす有限列 $\langle a_0,\dots,a_n\rangle$ が存在する」と形式化する。
基礎体系 $\mathsf{RCA}_0^*$ 上で、次が成り立つ。
1 は SY13 Lemma 3.3、2 は同論文 Lemma 3.2、3 は同論文 Theorem 3.4 である。本記事では逆数学の証明を再現しない。通常の集合論における thm-natural-categoricity と矛盾する結果ではなく、どの集合存在・帰納法原理が範疇性の形式化に必要かを測っている。
Peano構造の帰納法条件は、自然数の性質を証明するための規則であると同時に、構造に余分な元がないことを要求する条件でもある。通常の集合論では、この二つの働きを直接結びつけられる。以下では通常の標準自然数 $\mathbb N$ を添字として有限反復を作れることを基礎とし、任意に与えられた Peano構造がこの標準系と対応することを示す。この議論を弱い二階算術の内部に移す場合には、反復の存在自体が追加の問題になる。
通常の集合論において、Peano構造 $(N,0_N,s)$ の各元は $s^k(0_N)$ の形にただ一通り書ける。ただし $k\in\mathbb N$、$s^0$ は恒等写像である。
$R=\{s^k(0_N)\mid k\in\mathbb N\}$ とする。$s^0(0_N)=0_N$ なので $0_N\in R$。$s(s^k(0_N))=s^{k+1}(0_N)$ なので $s(R)\subseteq R$。Peano構造の帰納法条件により $R=N$ となり、表示の存在が得られる。
一意性のため $s^k(0_N)=s^l(0_N)$、$k< l$ と仮定する。$s$ の単射性を $k$ 回使って両辺から後者を消すと $0_N=s^{l-k}(0_N)$ となる。$l-k\ge1$ だから右辺は後者像に属し、$0_N\notin s(N)$ に反する。$l< k$ の場合も同じである。よって $k=l$。$\square$
この表示を使うと、thm-natural-categoricity の同型を明示できる。二つの Peano構造 $(N,0_N,s)$、$(M,0_M,t)$ に対して
$$
F(s^k(0_N))=t^k(0_M)
$$
と定める。表示の一意性によりこれは写像としてよく定まる。$M$ の各元も $t^k(0_M)$ と表示されるので全射であり、像の表示の一意性から単射でもある。始点と後者を保つ式は定義から従う。さらに、その式を満たす写像 $G$ は $G(s^k(0_N))=t^k(0_M)$ を $k$ に関する帰納法で満たすため $G=F$ である。したがって普通の集合論では、始点と後者を保つ同型は存在するだけでなく一意である。
ここで一意なのは、始点と後者の構造を保つ写像である。自然数全体という集合だけを見ると、$0$ と $1$ を交換し、それ以外を固定する全単射も作れるが、この写像は始点を保たない。集合の全単射と Peano構造の同型を区別すると、自然数の「同型を除いて一意」という文の意味がはっきりする。記号列による実現と偶数による実現にも、同じ表示を使った写像が定まる。
三つの Peano条件を同時に置いたとき、始点から分岐も合流も循環もしない一つの列が得られる。それぞれの条件がどの問題を除いているかは、他の二つを満たす反例を作ると分かる。
一点集合 $N=\{z\}$ に $0_N=z$、$s(z)=z$ を入れる。$s$ は単射であり、$z$ を含む部分集合は全体だけなので帰納法条件も満たす。しかし $z=s(z)$ であるため、始点が後者でない条件を満たさない。これは有限の閉じた循環を除くために第1条件が必要なことを示す。
$N=\{z,a\}$ に $0_N=z$、$s(z)=a$、$s(a)=a$ を入れる。始点 $z$ は後者像にない。$z$ を含み後者で閉じた集合は $a$ も含むので全体であり、帰納法条件も満たす。しかし $s(z)=s(a)$ で $z\ne a$ なので後者は単射でない。始点から進む列が途中で同じ元へ合流してしまう。
$N=(\mathbb N\times\{0\})\sqcup(\mathbb Z\times\{1\})$ とし、始点を $(0,0)$、後者を各成分で $(n,i)\mapsto(n+1,i)$ とする。後者は単射であり、$(0,0)$ は後者像にない。しかし $A=\mathbb N\times\{0\}$ は始点を含み後者で閉じる真部分集合である。したがって帰納法条件を満たさない。もう一方の整数列には、始点から有限回進んでも到達できない。
三番目の例で、余分な列の各元にも一意な前者がある。このため「$0$ でない元には前者がある」という条件だけでは余分な列を排除できない。Peano構造の分割性質は帰納法から導かれるが、その分割性質を帰納法の代わりに置くことはできない。局所的な前後関係と、全体が始点から生成されることは異なる条件である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 始点が後者像にないこと | 一点の循環 | 始点へ戻らないこと |
| 後者の単射性 | 二点で途中から固定する後者 | 反復の表示の一意性 |
| すべての部分集合への帰納法 | 自然数列と整数列の非交和 | 始点からの有限反復による全体の生成 |
Peano構造に順序を入れるには、有限反復の表示を用いて
$$
s^k(0_N)\le s^l(0_N)\quad\Longleftrightarrow\quad k\le l
$$
と定められる。表示は一意なので、これはよく定まる全順序である。始点が最小元となり、後者は各元の直後の元となる。さらに $s^k(0_N)$ 以下の元はちょうど $0_N,s(0_N),\ldots,s^k(0_N)$ の $k+1$ 個である。後者によって一つずつ増やす操作と、有限集合の個数を表す用途がこの順序を通じて結びつく。
無限であることと、各初期区間が有限であることは両立する。自然数全体には最後の元がない。実際、どの $s^k(0_N)$ を取っても $s^{k+1}(0_N)$ はそれより大きいので最大元にならない。一方、空でない部分集合 $A\subseteq N$ には最小元がある。ある $s^k(0_N)\in A$ を取り、その元以下の有限集合の中で $A$ に入る添字の最小のものを選べば、それより小さい自然数はどれも $A$ に入らない。したがって得た元は $A$ 全体の最小元でもある。
このように、始点と後者から得た順序は整列順序である。しかし、一般の整列順序集合が Peano構造になるわけではない。たとえば $\mathbb N$ の上に最大元 $\infty$ を加えた順序には、$\infty$ の直前の元がない。また $\infty$ からさらに後者へ進む先を同じ集合内に作ることもできない。整列性だけでは自然数列の構造を指定できず、始点と後者と帰納法を合わせる必要がある。
二階の帰納法条件では、$0_N$ を含み後者で閉じる「すべての部分集合」を対象にする。一階の Peano算術では、各一階式が定義する性質について帰納法公理を置く。式で定義される性質をすべて扱っても、モデルのすべての部分集合を量化したことにはならない。この差が、二階の範疇性と一階の超準モデルの共存を可能にしている。
通常の集合論で上に作った $R=\{s^k(0_N)\mid k\in\mathbb N\}$ は、外側の標準自然数を使った反復の集合である。二階の完全な意味論では $R$ も帰納法条件の対象に入るため、$R=N$ と結論できる。しかし、一階のモデルの内部では「外側の標準的な回数だけ反復した元の集合」を一つの一階式で定義できるとは限らない。したがって同じ議論をそのまま一階モデルへ移すことはできない。
逆数学ではさらに、二階の体系であっても存在する集合が制限される。有限反復をまとめる関数を作れるか、無限の集合から十分に多くの有限部分集合を取れるかが公理の強さに関係する。SY13 の Lemmas 3.2–3.3 と Theorem 3.4 は、この違いを三つの範疇性の形として分けている。通常の集合論での具体的な同型構成と、弱い体系での構成可能性を区別することが、その結果を読むための前提である。
Peano構造は有限集合には作れない。有限集合の自己写像が単射なら全射でもあるため、後者 $s$ が単射であれば始点もその像に入ってしまう。これは帰納法条件を使う前に、最初の二条件だけから分かる。有限構造で自然数の一部を模倣するとき、最後の点で後者を止めると自己写像でなくなり、最後の点を自身へ送ると単射でなくなり、始点へ戻すと始点が像にない条件が満たされない。
一方、有限な初期区間を観察することはできる。$0_N$ から $s^k(0_N)$ までの区間にはちょうど $k+1$ 個の元があるが、後者をその区間に制限すると最後の元の像は区間外へ出る。したがって、この有限区間自体を後者で閉じたPeano構造と見なすことはできない。自然数列のどの有限部分まで見ても、さらに一歩進む元があるという点が、全体の無限性を支えている。
始点と後者を指定しないまま「空でない整列集合」という条件だけで自然数を特徴づけることもできない。一点集合や有限鎖も整列集合であり、無限の整列集合にも自然数列より長いものがある。自然数の特徴づけに帰納法条件を含めるのは、単なる整列性から、その後者を有限回繰り返して到達する範囲へ対象を絞るためである。有限集合の個数として使う自然数と、自然数全体の集合の大きさとは、このように異なる役割をもつ。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する