自然数に加法と乗法を定義しましたが、加法を用いて順序を定義することが出来ます。
ここで定義する順序は通常の自然数の大小関係に一致します。
以下では \((\mathbf{N},0,\sigma)\) が自然数の公理を満たすものとします。
自然数の順序
自然数 \(m, n\in\mathbf{N}\) 対して, 関係 \(\leq\) をある自然数 \(l\in\mathbf{N}\) が存在して \(n=m+l\) となるとき \[m\leq n\] と定義する.
\(m\leq n\) かつ \(m\neq n\) のとき, つまり \(n=m+l\) となる \(l\neq0\) があるとき \[m<n\] と書く. また \(m\leq n\) のとき \(n\geq m\), \(m<n\) のとき \(n>m\) と書く.
最小の元
任意の自然数 \(n\in\mathbf{N}\) 対して \(0\leq n\) である.
つまり \(0\) は \(\mathbf{N}\) の最小元である.
証明
\(n=0+n\) なので良い.
\(\mathbf{N}\) はこの \(\leq\) によって全順序集合となりますが、
それを証明するためにいくつか補題を用意します。
補題１
自然数 \(m\in\mathbf{N}\) が \(m\neq0\) ならば, 任意の自然数 \(n\in\mathbf{N}\) に対して \(m+n\neq n\) かつ \(m+n\neq 0\) である.
この主張の対偶を考えると
ある自然数 \(n\in\mathbf{N}\) が存在して \(m+n=n\) または \(m+n=0\) ならば \(m=0\) である.
証明
\(n\) に関する帰納法で示す.
\(n=0\) のとき, \(m+0=m\neq0\) となるので成立する.
\(m+n\neq n\) かつ \(m+n\neq 0\) とすると
\(\sigma\) は単射なので \(m+\sigma(n)=\sigma(m+n)\neq\sigma(n)\).
\(0\notin\sigma(\mathbf{N})\) なので \(m+\sigma(n)=\sigma(m+n)\neq0\).
帰納法により全ての自然数 \(n\in\mathbf{N}\) に対して成立する.
補題２
自然数 \(m, n\in\mathbf{N}\) に対して, \(m\leq n\) ならば \(m\leq \sigma(n)\).
証明
\(m\leq n\) ならば, ある自然数 \(l\in\mathbf{N}\) を用いて \(n=m+l\) と書ける.
\(\sigma(n)=\sigma(m+l)=m+\sigma(l)\) なので \(m\leq \sigma(n)\).
補題３
自然数 \(m, n\in\mathbf{N}\) に対して, \(n\leq m\) かつ \(m\neq n\) ならば \(\sigma(n)\leq m\).
証明
\(n\leq m\) より, ある自然数 \(l\in\mathbf{N}\) を用いて \(m=n+l\) と書けるが,
\(m\neq n\) より \(l\neq0\) となるので \(l=\sigma(k)\) となる \(k\in\mathbf{N}\) が存在する.
よって \(m=n+\sigma(k)=\sigma(n+k)=\sigma(n)+k\) となり \(\sigma(n)\leq m\) が分かる.
全順序性
自然数 \(l, m, n\in\mathbf{N}\) と関係 \(\leq\) 対して, 以下が成り立つ :
- 反射律 : \(n\leq n\)
- 推移律 : \(l\leq m\) かつ \(m\leq n\) ならば \(l\leq n\)
- 反対称律 : \(m\leq n\) かつ \(n\leq m\) ならば \(m=n\)
- 完全律 : \(m\leq n\) または \(n\leq m\)
証明
１．
\(n=n+0\) なので \(n\leq n\).
２．
\(l\leq m\) かつ \(m\leq n\) ならば \(m=l+k, n=m+j\) となる \(k,j\in\mathbf{N}\) が存在し, \(n=(l+k)+j=l+(k+j)\) であり \(k+j\in\mathbf{N}\) なので \(l\leq n\).
３．
\(m\leq n\) かつ \(n\leq m\) ならば \(m=n+k, n=m+j\) となる \(k,j\in\mathbf{N}\) が存在し, \(m=m+(k+j)\) となるが, 補題１より \(k+j=0\). さらに補題１を適用して \(k=j=0\).
ゆえに \(m=n\).
４．
\(n\) に関する帰納法で示す.
\(n=0\) のとき, 任意の自然数 \(m\in\mathbf{N}\) 対して \(0\leq m\) なので成立する.
\(n\) が任意の自然数 \(m\in\mathbf{N}\) 対して\(m\leq n\) または \(n\leq m\) であるとする.
\(m\leq n\) ならば, 補題２より \(m\leq \sigma(n)\) となる.
\(n\leq m\) かつ \(m\neq n\) ならば 補題３より \(\sigma(n)\leq m\) となる.
よって, 任意の自然数 \(m\in\mathbf{N}\) 対して\(m\leq \sigma(n)\) または \(\sigma(n)\leq m\) である.
帰納法により全ての自然数 \(n\in\mathbf{N}\) に対して成立する.
以上で自然数が全順序であることが示されました。
系
２つの自然数 \(m, n\in\mathbf{N}\) 対して, 次のうち１つだけ成り立つ:
- \(m<n\)
- \(m=n\)
- \(m>n\)
次に自然数と順序を考える上で重要な性質である整列性について紹介します。
自然数の整列性
\(\mathbf{N}\) の任意の空でない部分集合 \(S\) は最小元を持つ.
つまり, 任意の \(n\in S\) に対して \(m\leq n\) を満たす元 \(m\in S\) が存在する.
証明
\(T\) を \(\mathbf{N}\) の部分集合で任意の \(n\in S\) に対して \(t\leq n\) を満たす自然数 \(t\) 全体の集合とする.
明らかに \(0\in T\) である.
また \(n\in S\) とすると \(n\leq\sigma(n)\) かつ \(n\neq\sigma(n)\) なので \(\sigma(n)\notin T\).
よって \(T\neq \mathbf{N}\) である.
帰納法の公理より \(m\in T,\ \sigma(m)\notin T\) となる自然数 \(m\) が存在する.
\(m\notin S\) とすると, 任意の \(n\in S\) に対して \(m\leq n\) かつ \(m\neq n\) なので
補題３より \(\sigma(m)\leq n\) となり \(\sigma(m)\notin T\) に矛盾.
ゆえに \(m\in S\) となり \(m\in T\) でもあるから, 任意の \(n\in S\) に対して \(m\leq n\) を満たす.
最後に演算と順序の関係について紹介します。
自然数の演算と順序
自然数 \(l, m, n\in\mathbf{N}\) に対して, 以下が成り立つ :
- \(m\leq n\) ならば \(m+l\leq n+l\).
- \(m\leq n\) ならば \(ml\leq nl\).
- \(m< n\) ならば \(m+l< n+l\).
- \(m< n\) かつ \(l\neq 0\) ならば \(ml< nl\).
- \(m+l\leq n+l\) ならば \(m\leq n\).
- \(ml\leq nl\) かつ \(l\neq 0\) ならば \(m\leq n\).
証明
１．
\(m\leq n\) ならば, 自然数 \(k\) を用いて \(n=m+k\) と書けるが
\(n+l=(m+k)+l=(m+l)+k\) なので \(m+l\leq n+l\).
２．
\(m\leq n\) ならば, 自然数 \(k\) を用いて \(n=m+k\) と書けるが
\(nl=(m+k)l=ml+kl\) なので \(ml\leq nl\).
３．
\(m<n\) ならば, 自然数 \(k\neq0\) を用いて \(n=m+k\) と書けるが
\(n+l=(m+k)+l=(m+l)+k\) なので \(m+l<n+l\).
４．
\(m< n\) ならば, 自然数 \(k\neq0\) を用いて \(n=m+k\) と書けるが
\(nl=(m+k)l=ml+kl\) かつ \(kl\neq0\) なので \(ml\leq nl\).
５．
３の対偶.
６．
\(ml\leq nl\) なので, ４の対偶より \(m\leq n\) または \(l=0\).
\(l\neq 0\) であったから \(m\leq n\).
コメント