半順序集合と全順序集合の意味と例

半順序関係、半順序集合、全順序関係、全順序集合について説明します。

半順序とは

ただし（$S$ 上の）半順序関係とは、以下の３つの条件を満たす二項関係 $\leq$ のことです。

反射律：
任意の $a\in S$ に対して、$a\leq a$

推移律：
任意の $a,b,c\in S$ に対して、$a\leq b$ かつ $b\leq c$ なら $a\leq c$

反対称律：
任意の $a,b$ に対して、$a\leq b$ かつ $b\leq a$ なら $a=b$

なお、半順序集合のことを、英語で partially ordered set というので、略して poset（ポセット）と呼ぶことがあります。

半順序の例

実際に、３つの条件を満たすことを確認してみます。

反射律：
$a$ は $a$ の倍数なので、$a\leq a$ です。

推移律：
$b$ が $a$ の倍数で、$c$ が $b$ の倍数なら、$c$ は $a$ の倍数なので、推移律も成立します。

反対称律：
$a$ が $b$ の倍数で、$b$ が $a$ の倍数なら $a=b$ なので、反対称律も成立します。

こちらも、３つの条件を満たすことは簡単に確認できます。

全順序とは

つまり、$(S,\leq)$ が、反射律、推移律、反対称律に加えて、

全順序律：
任意の $a,b\in S$ に対して、$a\leq b$ または $b\leq a$

も満たすとき、
$\leq$ を全順序関係と言い、$S$ を全順序集合と言います。

全順序の例

例えば「$2$ は $3$ の倍数でもないし、$3$ は $2$ の倍数でもない」というように、比較不可能な２つの要素があり、全順序律が満たされないからです。

任意の２つの実数は大きさの比較が可能であり、全順序律が満たされるからです。

次回は べき集合の意味と要素数 を解説します。