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

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

半順序とは

半順序関係が定められた集合 $S$ を半順序集合と言います。

ただし($S$ 上の)半順序関係とは、以下の3つの条件を満たす二項関係 $\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(ポセット)と呼ぶことがあります。

半順序の例

例1:
$S$ を正の整数全体の集合
$\leq$ を「$b$ が $a$ の倍数 $\iff a \leq b$」で定義
すると、$\leq$ は半順序関係になり、$S$ は半順序集合になります。

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

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

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

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

例2:
$S$ を実数全体の集合
$\leq$ をいわゆる普通の不等号(大小関係)
とすると、$\leq$ は半順序関係になり、$S$ は半順序集合になります。

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

全順序とは

半順序が「全ての2つの要素が比較可能」という性質も満たすとき、全順序と言います。

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

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

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

全順序の例

例1:
$S$ を正の整数全体の集合
$\leq$ を「$b$ が $a$ の倍数 $\iff a \leq b$」で定義
すると、$\leq$ は半順序関係でしたが、全順序関係ではありません。

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

例2:
$S$ を実数全体の集合
$\leq$ をいわゆる普通の不等号(大小関係)
とすると、$\leq$ は全順序関係になり、$S$ は全順序集合になります。

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

次:べき集合の意味と要素数
前:反射律、対称律、推移律の意味と例

スポンサーリンク

スポンサーリンク

誤植がございましたら @mathwordsnet までご連絡をお願いいたします。
ページ上部へ戻る