※私は数学者ではありません。自分用のまとめとしてこれを書いています。楽しむ範囲でご覧いただければ幸いです。内容の正確性については専門家のサイトや動画、あるいは専門書で必ず確認をお願いします。
* * *
前回の記事から、二項関係について考えています。一般に、$X$の直積の部分集合$R\subset X\times X$を二項関係といい、$X$の直積を変域とする命題関数 $(x_1, x_2)\in R$を $x_1 R x_2$と表記します。二項関係には同値、順序、整列などがあります。これらのうち、前回は同値についてみました。この記事では順序についてみます。
順序
集合$X$の順序 $(\leq)$を調べる二項関係を$(X, \leq)$と表記します。順序には前順序、半順序、全順序があります。これらのうち前順序（preoder）とは、次の2条件を満たす二項関係です。
反射律：すべての$x$について、$x\leq x$が真
推移律：すべての$x_1, x_2, x_3$について、$x_1\leq x_2$が真かつ$x_2\leq x_3$
が真であれば、$x_1\leq x_3$は真
なんだか難しそうですが、$X=\{2, 4, 6\}$を例に考えればすぐわかります。まず、反射律ですが
$$2\leq 2 4\leq 4 6\leq 6$$
これらの式は等号の意味で満たされています。つづいて推移律ですが
$$2\leq 4 かつ 4\leq 6 ならば 2\leq 6$$
明らかに$2\leq 4$は真、かつ$4\leq 6$は真です。そして$2\leq 6$も真です。難しそうにみえますが、順序は小学1年生から使っている概念です。上の２条件に加え、次に示す反対称律も満たす二項関係を半順序（partial oder）といいます。
反対称律：すべての$x_1, x_2$について、$x_1\leq x_2$が真かつ$x_2\leq x_1$が真
であれば、$x_1=x_2$は真
同値の条件の1つに対称律がありましたが、半順序の条件の1つは反対称律であることに注意しましょう。反対称律も難しくありません。たとえば、集合$X$から$x_1=2$、$x_2=4$を取り出してみましょう。このとき
$$2\leq 4 は真だが 4\leq 2 は偽$$
となります。異なる要素を取り出すと、不等式のいずれかが偽になってしまいます。2つの不等式ともに真であるためには $x_1=x_2$でなければなりません。たとえば、$x_1=4$、$x_2=4$を取り出してみましょう。このとき
$$4\leq 4 かつ 4\leq 4 ならば 4=4$$
と反対称律を満たします。反射律、推移律、反対称律に加え、完備律も満たす二項関係を全順序（total order）といいます。
完備律：$(X, \leq)$が半順序であるとする。このとき、すべての$x_1, x_2$
について$x_1\leq x_2$が真、または$x_2\leq x_1$が真
全順序は鎖（chain）、線形順序（linear order）もいわれます。不等号を基準に、集合のすべての要素が綺麗に一列に並びます。呼び名には「順序に枝分かれを許さない」という強いメッセージが込められています。
「順序を前順序、半順序、全順序に分けるのはなぜですか」という問いには、「ド・モルガンの法則は完備律を満たす全順序に適用できるが、半順序と前順序には適用できない」と答えるのがよさそうです。前につく否定を外すとき、不等号の向きをひっくり返す操作ができる二項関係は全順序と整列です。この点は、数々の補題や定理を証明するとき、大きな意味を持ちます。
半順序であるが全順序ではない二項関係の例は込み入ります。関係$\leq$を集合の包含関係や自然数の割り切れる商などに読み替える例のようです。こちらの動画をご覧ください。
次の動画では半順序と全順序の違いについて、イメージできる解説をしています。いくつかの支流から本流に流れ込む川の流れや入れ子構造の集合を例にしています。
順序には、完全律や三分律といった条件もありますが、ここでは割愛します。詳細は『WIIS』の説明をご参照ください。
順序同型
2つの集合 $X=\{1, 2, 3\}$ と $Y=\{みかん, りんご, いちご\}$ について、順序 $(X, \leq)$ と $(Y, \leq)$ を考えます。ここで、$X$の$\leq$は小さい数から大きい数への順序、$Y$の$\leq$は一番安いみかん、二番目に安いりんご、三番目に安いいちごという果物の値段についての順序だとします。これらの順序集合を関係づける次のような写像 $f$ を与えます。
$1\stackrel{f}{\mapsto}みかん$
$2\stackrel{f}{\mapsto}りんご$
$3\stackrel{f}{\mapsto}いちご$
写像 $f$ は、$X$の一番目の要素の像が$Y$の一番目の要素、$X$の二番目の要素の像が$Y$の二番目の要素、$X$の三番目の要素の像が$Y$の三番目の要素になっています。この $f$ のような、2つの集合の順序を損ねない写像を順序を保つ写像といいます。
順序を保つ写像が全単射であるとき、順序同型写像といい、順序同型写像で関係づけられる2つの順序集合を順序同型（order isomorphic）といいます。一般に、順序集合$(X, R)$、$(Y, S)$、$(Z, T)$について、以下が成り立ちます。
- $(X, R)$と$(X, R)$は順序同型
- $(X, R)$と$(Y, S)$が順序同型であれば、$(Y, S)$と$(X, R)$も順序同型
- $(X, R)$と$(Y, S)$が順序同型、かつ$(Y, S)$と$(Z, T)$が順序同型であれば、$(X, R)$と$(Z, T)$は順序同型
これらはそれぞれ同値関係の反射律、対称律、推移律のイメージです。