全順序関係

以前の記事で二項関係を定義したが、その中でも特別な性質を満たすものを全順序関係とよぶ。自然数の大小関係もこの全順序関係となるので、自然数の大小関係を例として全順序関係について述べる。

全順序関係

全順序関係とは二項関係の一種である。その中でも「一方はある意味でもう一方以下であると言える」という関係となるものが全順序関係である。この説明だけでは大ざっぱすぎて定義にならないので、定義としては以下を与える。

定義$R\subset x\times x$ を二項関係とする。$x$ に属する任意の $a$, $b$, $c$ について

  • (反射律) $aRa$
  • (推移律) $aRb$, $bRc$ であれば $aRc$
  • (反対称律) $aRb$, $bRa$ であれば $a=b$
  • (全順序律) $aRb$ か $bRa$ の少なくとも一方が成立する
のいずれも成立するとき、$R$ は $x$ 上の全順序関係である。

ここでは全順序関係のみを説明するが、上の4つのルールのうち反射律と推移律を満たしていれば前順序関係といい、加えて反対称律を満たしていれば半順序関係という。

自然数の大小関係

具体例として最もわかりやすいのは自然数の大小関係であろう。以前の記事で二項関係の例として自然数の大小関係を挙げたが、それとほぼ同じものである。

定義二項関係 $R$ が\[R=\{\langle x,y\rangle\in \omega\times\omega \mid x\in y \lor x=y\}\]を満たすとする。この関係を自然数の大小関係と呼び、$xRy$ であること (つまり $\langle x,y\rangle\in R$ であること) を $x\leq y$ もしくは $y\geq x$ と書き、それぞれを「$x$ は $y$ 以下である」もしくは「$y$ は $x$ 以上である」と表現する。

つまり、2つの自然数 $x$, $y$ について、$x\in y$ か $x=y$ のいずれかが成立すれば $x\leq y$ であり、いずれも成立しないなら $x\leq y$ ではない。以前は $\lt$ の定義をしたが、これでは全順序にならないので新たに $\leq$ を定義した。

この大小関係が全順序関係であることを確かめる。

定理上で定義した関係 $R$ は全順序関係である。

(証明) 全順序関係の定義に則って確かめる。まず $a\leq a$ を示す。$a=a$ より、$a\leq a$。

次に $a\leq b$, $b\leq c$ から $a\leq c$ を導く。$a\leq b$ より $a\in b$ と $a=b$ のいずれかが成立し、$b\leq c$ より $c\in d$ と $c=d$ のいずれかが成立する。もし $a=b$, $b=c$ であれば $a=c$ であるので $a\leq c$。もし $a=b$, $b\in c$ であれば $a\in c$ であるので $a\leq c$。もし $a\in b$, $b=c$ であれば $a\in c$ であるので $a\leq c$。もし $a\in b$, $b\in c$ であれば自然数の推移性より $a\in c$ であるので $a\leq c$。

次に $a\leq b$, $b\leq a$ から $a=b$ を背理法で導く。$a\neq b$ とすると $a\leq b$, $b\leq a$ より $a\in b$, $b\in a$ (注: この時点で正則性の公理に矛盾しているがこの記事シリーズでは正則性の公理を詳しく説明していないので、正則性の公理に依存する別の定理を使う)。 このとき自然数の推移性より $a\in a$ であるが、これは自然数の正則性に矛盾する。したがって $a= b$。

最後に $a\leq b$, $b\leq a$ のいずれかが成立することを $a$ についての数学的帰納法で示す。まず命題より $0\in b$ と $0=b$ のいずれかが成立するので $0\leq b$。次に固定された $a$ について $a\leq b$, $b\leq a$ のいずれかが成立すると仮定する。このとき $a= b$, $b\in a$, $a\in b$ のいずれかが成立している。もし $a=b$ なら $a\in a\cup\{a\}$ より $b\in a\cup\{a\}$ であるので $b\leq a\cup\{a\}$。もし $b\in a$ なら $a\in a\cup\{a\}$ と自然数の推移性より $b\in a\cup\{a\}$ であるので $b\leq a\cup\{a\}$。もし $a\in b$ であるなら、命題より $a\cup\{a\} \leq b$。以上よりいずれにしても $a\cup\{a\} \leq b$, $b\leq a\cup\{a\}$ のいずれかが成立する。

自然数の大小関係の性質

今回と以前の記事で自然数の演算と大小関係を定義した。それらの性質について、自然数の大小関係として期待される以下のことが成り立つ。

定理

  1. $a+x=b$ であるとき $a\leq b$
  2. $a+x=b$ を満たす自然数 $x$ が存在しないとき $a\leq b$ ではない

(証明) 1 を $x$ についての数学的帰納法で示す。$a+0=b$ であれば $a=b$ であるので $a\leq b$。

固定された $x$ について、任意の自然数 $b'$ に対して $a+x=b'$ ならば $a\leq b'$ であるとする。ここで $a+(x\text{の次の数})=b$ であれば $(a+x)\text{の次の数}=b$ であるので、命題よりある $c$ が存在して\[(a+x)\text{の次の数}=c\text{の次の数}=b\]であり、後者関数の単射性より\[a+x=c\]であるので数学的帰納法の仮定より $a\leq c$。つまり $a\in c$ か $a=c$ が成立し、さらに $c\in b$ であるので自然数の推移性より $a\in b$ であり $a\leq b$。

2 の対偶を $b$ についての数学的帰納法で示す。$a\leq 0$ とすると $a\in0$ はあり得ないので $a=0$ であり、よって $a+0=0$。

固定された $b$ について、$a\leq b$ ならば 自然数 $x'$ が存在して $a+x'=b$ とする。ここで $a\leq b\cup\{b\}$ であれば $a=b\cup\{b\}$ か $a=b$ か $a\in b$ のいずれかである。$a=b\cup\{b\}$ であれば $a+0=b\cup\{b\}$。$a=b$ か $a\in b$ であれば $a\leq b$ なので $a+x'=b$ となり、したがって\begin{eqnarray}a+(x'\text{の次の数})&=&(a+x')\text{の次の数}\\&=& b\text{の次の数}\\ &=&b\cup\{b\}\end{eqnarray}であるので、いずれにしてもある自然数 $x$ が $a+x=b\cup\{b\}$ を満たす。

いま確認した性質は、自然数の論理として知られるペアノ算術などで大小関係の定義として採用されている性質で、これらを満たすことから、ここで定義した大小関係はペアノ算術のそれと一致するといえる。そのため、ペアノ算術の結論として、ここでは証明しないが以下の結論を得ることができる。

  • 加法は大小関係を保存し、つまり $a\leq b$, $c\leq d$ ならば $a+c\leq b+d$
  • 乗法は大小関係を保存し、つまり $a\leq b$, $c\leq d$ ならば $ac\leq bd$