自然数の演算

帰納的定義の \((X,x_0,\varphi)\) を \((\mathbf{N},m,\sigma)\) で考えれば良い.

１・２は定義から明らか.
３は \(1=\sigma(0)\) なので１・２から分かる.

４．
\(\mathrm{id}_\mathbf{N}\) は \(\mathrm{id}_\mathbf{N}(0)=0,\ \mathrm{id}_\mathbf{N}\circ\sigma=\sigma\circ\mathrm{id}_\mathbf{N}\) を満たすので \(f_0=\mathrm{id}_\mathbf{N}\).

５．
\(\sigma\circ f_m\) は \((\sigma\circ f_m)(0)=\sigma(m),\ (\sigma\circ f_m)\circ\sigma=\sigma\circ(f_m\circ\sigma)=\sigma\circ(\sigma\circ f_m)\) を満たすので \(f_{\sigma(m)}=\sigma\circ f_m\).

１．
任意の自然数 \(m, n\in\mathbf{N}\) に対して \((l+m)+n=l+(m+n)\) が成立する \(l\) 全体の集合を \(S\) とおく.
\((0+m)+n=m+n=0+(m+n)\) より, \(0\in S\).
また, \(l\in S\) のとき, \((l+m)+n=l+(m+n)\) なので
\((\sigma(l)+m)+n=\sigma(l+m)+n=\sigma((l+m)+n)=\sigma(l+(m+n))=\sigma(l)+(m+n)\)
であるから \(\sigma(l)\in S\) となり, 数学的帰納法の公理より \(S=\mathbf{N}\) が分かる.

２．
任意の自然数 \(n\in\mathbf{N}\) に対して \(m+n=n+m\) が成立する \(m\) 全体の集合を \(S\) とおく.
\(0+n=n=0+n\) より, \(0\in S\).
また, \(m\in S\) のとき, \(m+n=n+m\) なので
\(\sigma(m)+n=\sigma(m+n)=\sigma(n+m)=n+\sigma(m)\)
であるから \(\sigma(m)\in S\) となり, 数学的帰納法の公理より \(S=\mathbf{N}\) が分かる.

３．
任意の自然数 \(m, n\in\mathbf{N}\) に対して \(m+l=n+l\) ならば \(m=n\) が成立する \(l\) 全体の集合を \(S\) とおく.
\(m+0=n+0\) ならば \(m=m+0=n+0+n\) なので \(0\in S\).
\(l\in S\) ならば \(m+l=n+l\) ならば \(m=n\) であるが
\(m+\sigma(l)=n+\sigma(l)\) とすると \(m+\sigma(l)=\sigma(m+l),\ n+\sigma(l)=\sigma(n+l)\) なので \(\sigma(m+l)=\sigma(n+l)\).
\(\sigma\) は単射なので \(m+l=n+l\) となり仮定より \(m=n\).
ゆえに \(\sigma(l)\in S\) なので, 数学的帰納法の公理より \(S=\mathbf{N}\) が分かる.

帰納的定義の \((X,x_0,\varphi)\) を \((\mathbf{N},0,f_m)\) で考えれば良い.

１・２は定義から明らか.
３は \(1=\sigma(0)\) なので１・２と加法の性質から分かる.

４．
全ての元を \(0\) に移す定値写像 \(\mathbf{0}\) は \(\mathbf{0}(0)=0,\ \mathbf{0}\circ\sigma=f_0\circ\mathbf{0}\) を満たすので \(g_0=\mathbf{0}\).

５．
\(h(n)=mn+n\) とすると, \(h(0)=m0+0=0\) であって
\(h(\sigma(n))=m\cdot\sigma(n)+\sigma(n)\) であるが, 加法の性質を駆使すると \[
\begin{align*}
f_{\sigma(m)}(h(n))=f_{\sigma(m)}(mn+n)&=\sigma(m)+(mn+n)\\
&=(m+1)+(mn+n)\\
&=mn+m+n+1\\
&=m(n+1)+(n+1)\\
&=m\cdot\sigma(n)+\sigma(n)
\end{align*}\] となるので \(g_{\sigma(m)}=h\).

６．
\(m\neq0\) なので \(m=\sigma(m^\prime)=m^\prime+1\)
\(n\neq0\) なので \(n=\sigma(n^\prime)=n^\prime+1\) と書けるが
\(mn=(m^\prime+1)(n^\prime+1)=m^\prime n^\prime+m^\prime+n^\prime+1=\sigma(m^\prime n^\prime+m^\prime+n^\prime)\)
なので \(mn\neq0\).

証明のしやすさから２→３→１の順に証明する.

２．
任意の自然数 \(n\in\mathbf{N}\) に対して \(mn=nm\) が成立する \(m\) 全体の集合を \(S\) とおく.
\(0n=0=n0\) より, \(0\in S\).
また, \(m\in S\) のとき, \(mn=nm\) なので
\(\sigma(m)\cdot n=mn+n=nm+n=n\cdot\sigma(m)\)
であるから \(\sigma(m)\in S\) となり, 数学的帰納法の公理より \(S=\mathbf{N}\) が分かる.

３．
任意の自然数 \(l,m\in\mathbf{N}\) に対して \(l(m+n)=lm+ln\) が成立する \(n\) 全体の集合を \(S\) とおく.
\(0(m+n)=0=0m+0n\) より, \(0\in S\).
また, \(n\in S\) のとき,
\(l(m+\sigma(n))=l(m+(n+1))=l((m+1)+n)\)
であるが, 任意の自然数 \(l,m\in\mathbf{N}\) に対して \(l(m+n)=lm+ln\) なので
\(m\) を \(m+1\) に変えて
\(l((m+1)+n)=l(m+1)+ln=lm+l+ln=lm+(ln+l)=lm+l\cdot\sigma(n)\)
であるから, 結局 \(l(m+\sigma(n))=lm+l\cdot\sigma(n)\) より \(\sigma(n)\in S\) となり,
数学的帰納法の公理より \(S=\mathbf{N}\) が分かる.

１．
任意の自然数 \(m, n\in\mathbf{N}\) に対して \((lm)n=l(mn)\) が成立する \(l\) 全体の集合を \(S\) とおく.
\((0m)n=0n=0=0(mn)\) より, \(0\in S\).
また, \(l\in S\) のとき \((lm)n=l(mn)\) であるが
\((\sigma(l)m)n=((l+1)m)n=(lm+m)n=(lm)n+mn\)
\(\sigma(l)(mn)=(l+1)(mn)=l(mn)+mn\)
なので \((\sigma(l)m)n=\sigma(l)(mn)\) が成り立ち \(\sigma(l)\in S\) が分かる.
数学的帰納法の公理より \(S=\mathbf{N}\) が分かる.

４．
自然数の順序を使うと簡単に示せる.
(ここで使う順序の性質の証明に積の簡約律は使用しないので循環論法にはならない)
\(ml=nl\) かつ \(l\neq0\) のとき, \(m<n\) とすると \(n=m+k\) を満たす自然数 \(k\neq0\) が存在するが,
\(ml+0=ml=nl=(m+k)l=ml+kl\) なので, 加法の簡約律より \(kl=0\).
\(l\neq0\) なので \(k=0\) となるがこれは矛盾.
\(m>n\) の時も同様に矛盾するので, \(m=n\) が分かる.

モノイドや半環の定義と, 加法・乗法の性質から明らか.