今回は「半順序と全順序」について解説していきます。
全然分かんないんっすよね…
半順序と全順序って難しいですよね。僕も習いたての頃は２つの違いが全然分からなくて、混乱しまくりました。
その経験を基に、簡単な例を使いながら、「半順序と全順序」を分かりやすく解説したので、ぜひ最後までご覧ください！
そもそも順序とは？
一般的には「順序＝あるルールに沿った順列」みたいな意味がありますが、離散数学では「順序＝順番を決めるルール」みたいな意味があります。
例えば、次のような数式を考えてみましょう。
$$1 \leq 2 \leq 3 \leq 4….$$
上の式において、一般的には、数字が大きい順になっている順列のことを順序と呼び、「数字が順序になっている」というように使いますが、離散数学では$ \leq $という順番を決めるルールにあたるもののことを順序と呼ぶのです。
２つの物事の順番を決めるルール（関係）のことを順序って呼ぶんすね！
その通り！
半順序とは？
半順序とは「一直線に並べることが出来ない順序」です。
例えば、集合$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$が半順序になるためには次の３つの条件を満たさなくてはいけません。
・反射律
全ての$ 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$がこの３つを満たしているのか考えてみましょう。集合$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$は「半順序」であることが確認されました。
何だか難しいっすね…
順序を理解するには、「反射律・対称律・推移律」と「二項関係」の理解が必要不可欠です。まだ理解できていない方は以下の記事を参考にしてみてください！
半順序の他の例
集合$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$上の二項関係「＝」は全順序です。
まとめ
今回の重要なポイントをまとめておきます。半順序・全順序はすぐに理解するのは難しいと思うので、少しずつ分かるところから理解を深めていきましょう。
・半順序は「一直線に並べることが出来ない順序」である。また、「比較不能の組がある順序」でもある。
・全順序は「一直線に並べることが出来る順序」
・半順序が全順序になるための条件は「全ての要素が比較可能である」こと
お疲れ様でした！
離散数学解説してるサイト自体少ない中でとても分かりやすい説明ありがとうございます。とても参考になりました。