【離散数学】半順序と全順序を分かりやすく解説!

半順序・全順序

今回は「半順序と全順序」について解説していきます。

先生
先生
くるる
くるる

全然分かんないんっすよね…

半順序と全順序って難しいですよね。僕も習いたての頃は2つの違いが全然分からなくて、混乱しまくりました。

その経験を基に、簡単な例を使いながら、「半順序と全順序」を分かりやすく解説したので、ぜひ最後までご覧ください!

そもそも順序とは?

一般的には「順序=あるルールに沿った順列」みたいな意味がありますが、離散数学では「順序=順番を決めるルール」みたいな意味があります。

例えば、次のような数式を考えてみましょう。

$$1 \leq 2 \leq 3 \leq 4….$$

上の式において、一般的には、数字が大きい順になっている順列のことを順序と呼び、「数字が順序になっている」というように使いますが、離散数学では$ \leq $という順番を決めるルールにあたるもののことを順序と呼ぶのです。

2つの物事の順番を決めるルール(関係)のことを順序って呼ぶんすね!

その通り!

先生
先生

半順序とは?

半順序とは「一直線に並べることが出来ない順序」です。

例えば、集合$A=\{2,3,4,5,8,9\}$とし、$A$上の二項関係$R$を「$aRb$=$a$は$b$を割り切る」という意味に定義しましょう。すると、次のような2つの順列を作ることが出来ます。

$$2 R 4 R 8$$

$$3 R 9$$

$2R4R8$は「$2$は$4$を割り切る、かつ、$4$は$8$を割り切る」という意味だと考えてください。

この例では、一直線に並べることが出来ていません。つまり、「$aRb$=$a$は$b$を割り切る」という関係$R$は「半順序」です。

分ぐらいは一直線になる」から「順序」と言うのです。

先生
先生

また、$2$と$3$において、$2R3$も$3R2$も成り立ちません。このとき、「$2$と$3$は比較不能である」と言います。その意味で、半順序は「比較不能の組がある順序」ということもできます。

半順序になるための条件

集合$A$上の二項関係$R$が半順序になるためには次の3つの条件を満たさなくてはいけません。

半順序になるための3つの条件

反射律
  全ての$ a \in A$に対して、$aRa$が成り立つ

反対称律
  全ての$a,b \in A$に対して、$aRb$かつ$bRa \Rightarrow a=b$が成り立つ

推移律
  全ての$a,b,c \in A$に対して、$aRb$かつ$bRc \Rightarrow aRc$が成り立つ

例えば、先の「$aRb$=$a$は$b$を割り切る」と定義された関係$R$がこの3つを満たしているのか考えてみましょう。集合$A=\{2,3,4,5,8,9\}$です。

反射律
  「$3R3$=$3$は$3$を割り切る」は正しいです。他の数字でも「$aRa$」が成り立つの  
  で、反射律が満たされます。

反対称律
  $3R9$は正しいですが、$9R3$は間違いです。すなわち、「$aRb$かつ$bRa$」が成り立
  つのは$a=b$しかありえません。集合$A$内の全ての数字において
  「$aRb$かつ$bRa \Rightarrow a=b$」が成り立つので、反対称律が満たされます。

推移律
  「$2R4$かつ$4R8$ならば、$2R8$」は正しいです。他の数字でも
  「$aRb$かつ$bRc \Rightarrow aRc$」を満たすので、推移律は満たされます。

よって、「$aRb$=$a$は$b$を割り切る」と定義された関係$R$は「半順序」であることが確認されました。

くるる
くるる

何だか難しいっすね…

順序を理解するには、「反射律・対称律・推移律」と「二項関係」の理解が必要不可欠です。まだ理解できていない方は以下の記事を参考にしてみてください!

先生
先生

記事を取得できませんでした。記事IDをご確認ください。

記事を取得できませんでした。記事IDをご確認ください。

半順序の他の例

集合$A=\{1,2,3,4,5\}$上の二項関係「$\subseteqq$」も半順序です。条件を満たしているか確認してみましょう。

反射律
  全ての$ a \in A$に対して、$a \subseteqq a$が成り立つ

反対称律
  全ての$a,b \in A$に対して、$a \subseteqq b$かつ$b \subseteqq a \Rightarrow a=b$が成り立つ

推移律
  全ての$a,b,c \in A$に対して、$a \subseteqq b$かつ$b \subseteqq c \Rightarrow a \subseteqq c$が成り立つ

よって、集合$A$上の二項関係「$\subseteqq$」は半順序です。

また、「$aRb$=$a$は$b$の倍数」と定義された関係$R$も半順序です。

全順序

全順序は「一直線に並べることが出来る順序」です。つまり、半順序の逆ですね。
例えば、集合$A=\{2,3,4,5,8,9\}$とし、$A$上の二項関係「$\leq$」を考えると、

$$2 \leq 3 \leq 4 \leq 5 \leq 8 \leq 9$$

というように、一直線に並べることが出来ています。つまり、関係$\leq$は全順序です。$\leq$は実数上ならどんな数字の集合でも、全て一直線に並べることができます。

部の要素を一直線に並べることができる」から、「順序」と言うのです。

先生
先生

全順序になるための条件

実は、全順序は半順序でもあります。なので、半順序の条件「反射律・反対称律・推移律」をまず満たさなければなりません。

そして、半順序が全順序になるための条件は「全ての要素が比較可能である」ことです。
例えば、「$\leq$」という関係は、実数であればどのような数の組$a,b$でも「$a \leq b$」と比較することができます。

だから、「$\leq$」は全順序なんです。

先生
先生

全順序の他の例

例えば、集合$A=\{1,1,1,1\}$上の二項関係「=」も全順序です。条件を満たしているか確かめてみましょう。

反射律
  全ての$ a \in A$に対して、$a = a$が成り立つ

反対称律
  全ての$a,b \in A$に対して、$a = b$かつ$b = a \Rightarrow a = b$が成り立つ

推移律
  全ての$a,b,c \in A$に対して、$a = b$かつ$b = c \Rightarrow a = c$が成り立つ

全ての要素が比較可能
  集合$A$の全ての要素について比較できます

よって、集合$A$上の二項関係「=」は全順序です。

まとめ

今回の重要なポイントをまとめておきます。半順序・全順序はすぐに理解するのは難しいと思うので、少しずつ分かるところから理解を深めていきましょう。

半順序・全順序のまとめ

半順序は「一直線に並べることが出来ない順序」である。また、「比較不能の組がある順序」でもある。

全順序は「一直線に並べることが出来る順序」

・半順序が全順序になるための条件は「全ての要素が比較可能である」こと

お疲れ様でした!

先生
先生

シェアしてね!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です