自然数
概要
自然数（natural number）とは、0から始めて後者を繰り返すことで得られる数である。本記事では0を含め、自然数全体を $\mathbb N=\{0,1,2,\dots\}$ と書く。二階のPeano構造は、0が後者でなく、後者写像が単射で、0を含み後者で閉じた部分集合が全体に限るという条件で特徴づけられ、同型を除いて一意である。von Neumann自然数などの実現、基本性質、0を含める流儀、一階Peano算術との違い、範疇性の逆数学も説明する。
定義
本記事では $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構造という。
- $0_N\notin s(N)$ である。
- $s$ は単射である。
- $0_N\in A\subseteq N$ かつ $s(A)\subseteq A$ ならば $A=N$ である。
第3条件は、$N$ のすべての部分集合を量化する二階の帰納法条件である。Peano構造の元を自然数（natural number）と呼び、$s(n)$ を $n$ の後者という。
第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$」と定めれば得られる。このため、始点と後者だけの構造から通常の自然数算術が回収できる。
0を含める流儀
本記事の $\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^*$ 上で、次が成り立つ。
- 「すべての Peano システムが標準系にほとんど同型である」は $\mathsf{WKL}_0^*$ と同値である。
- 「標準系にほとんど同型な Peano システムは標準系に同型である」は $\mathsf{RCA}_0$ と同値である。
- 「すべての Peano システムが標準系に同型である」は $\mathsf{WKL}_0$ と同値である。
1 は SY13 Lemma 3.3、2 は同論文 Lemma 3.2、3 は同論文 Theorem 3.4 である。本記事では逆数学の証明を再現しない。通常の集合論における thm-natural-categoricity と矛盾する結果ではなく、どの集合存在・帰納法原理が範疇性の形式化に必要かを測っている。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
