順序関係

順序関係とは、集合上の二項関係のうち、反射的・反対称的・推移的なもののことです。

はじめに

順序は日常生活でもよく使う考え方です。単語を五十音順やアルファベット順に並べる、学校の生徒を身長順に並べる、商品を値段順に並べるなど、さまざまなものを何らかの方法で並べることができます。これらはすべて順序関係で表せます。順序関係はふつう記号 $\leqq$ で表します。関連する記号には <、>、$\geqq$ があります。意味は明らかでしょう。

このような関係にはどんな性質を期待するでしょうか。記号からもわかるように、順序関係では等しい要素どうしも関係をもちます。つまり、定義したいのは「以下」の関係の性質です。したがって、この関係は反射的であるべきです。$a\leqq a$ が成り立たなければなりません。

次はどうでしょうか。対称性は成り立たないはずです。値段の順序を考えると、車がパンより安いなら、同時にパンが車より安いということはありえません。では一般に、$a\leqq b$ かつ $b\leqq a$ となったとき、何を期待するでしょうか。そのようなことに意味がある場合はあるでしょうか。あります。a = b のときです。二つの要素の順番を入れかえても関係が成り立つのは、その要素どうしが等しいときだけです。したがって、順序は反対称的です。

最後に、車がパンより高く、飛行機が車よりさらに高いことがわかっていれば、飛行機は当然パンより高いはずです。これを表すのが推移性です。

半順序

ここまでで定義したものは、実は半順序にすぎず、全順序ではありません。なぜ全順序ではないのでしょうか。集合どうしの順序を定義してみましょう。二つの集合はどのように比べればよいでしょうか。

A ⊆ B、つまり A が B の部分集合のとき、集合 A は集合 B 以下であると決めます。これは理にかなっています。例えば A = {1, 2}、B = {1, 2, 3} なら、A のほうが小さいといえるでしょう。B は A と同じ要素をすべて含み、さらに3も含んでいるからです。したがって、例えば次の関係が成り立ちます。

• $\{a,c\}\leqq \{a,b,c,d\}$
• $\mathrm{\varnothing }\leqq \{5,n,x\}$
• $\{x,e,s\}\leqq \{x,e,s\}$

困るのは、A = {a, b} と B = {a, c} のような集合を比べたいときです。どちらが小さく、どちらが大きいのでしょうか。どちらの集合も要素 a を含んでいますが、もう一つの要素はそれぞれ異なります。どちらの集合も他方の部分集合ではないので、$A\leqq B$ も $B\leqq A$ も成り立ちません。このような集合は、この順序では比較できません。

そこで、集合のどの二つの要素も比較できるとき、その集合を全順序集合、または鎖といいます。例えば、数の集合はふつうの大小関係について全順序集合です。どの二つの実数 a、b についても、$a\leqq b$ と $b\leqq a$ の少なくとも一方が成り立ちます。

身近な例

比べないほうがよい例として、美しさによる順序が考えられます。関係 < は「より見劣りする」という意味になります。角が立たないように、逆に > を「より美しい」と定義したほうがよいかもしれません。二人の女性を比べることには意味がありそうです。例えば「花子」 < 「さくら」は、さくらさんのほうが花子さんより美しいという意味です。二人の男性でも同じで、「太郎」 < 「健太」は、健太さんのほうが太郎さんより美しいという意味です。

問題は、男性と女性の美しさを比べるのは難しいということです。さくらさんと健太さんではどちらが美しいでしょうか。花子さんと太郎さんではどちらが見劣りするでしょうか。これは深入りしないほうがよさそうです。

最後の例で女性だけに限れば、全順序集合が得られるといえます。すべての女性の美しさを比べられるからです。

極小元と極大元、最小元と最大元

順序集合 M が与えられたとき、x < min となる x ∈ M が存在しないならば、要素 min ∈ M を極小元といいます。つまり、要素 min より小さい要素を見つけることができません。

x > max となる x ∈ M が存在しないならば、要素 max ∈ M を極大元といいます。つまり、それより大きい要素を見つけることができません。

この二つの概念は、最小元・最大元とは異なります。

すべての x ∈ M について $a\leqq x$ が成り立つとき、要素 a ∈ M を最小元といいます。つまり、最小元 a は集合 M の他のすべての要素以下です。

すべての x ∈ M について $b\geqq x$ が成り立つとき、要素 b ∈ M を最大元といいます。最大元 b は集合 M の他のすべての要素以上です。

最大元と極大元の違いは何でしょうか。集合は全順序とは限らないので、極大元は複数あることがあります。見た目で人を比べる例に戻ると、例えばさくらさんがいちばん美しい女性で、健太さんがいちばん美しい男性だとします。しかし、この二人はもう比べられません。さくらさんと健太さんのどちらが美しいかはわかりません。

したがって、どちらの要素も極大元です。健太さんより美しい人は見つかりません。健太さんは他のどの男性よりも美しく、女性とは比べられないからです。さくらさんも同様で、どの女性よりも美しく、男性とは比べられません。

しかし、どちらも最大元、この意味での「いちばん美しい人」ではありません。健太さんがいちばん美しい人、つまり最大元であるためには、すべての女性を含むすべての人より美しくなければなりません。しかし、すでに述べたように健太さんは女性と比べられないので、いちばん美しい人にはなれません。順序の理論の用語でいえば、極大元にすぎません。

集合に最大元があれば、それは極大元でもあることはすぐにわかるでしょう。要素 a が集合の他のすべての要素より大きければ（最大元の定義）、それよりさらに大きい要素は当然見つかりません（極大元の定義）。

最大元と最小元をもつ集合の例として、閉区間 [0, 1] があります。同じ区間でも開区間 (0, 1) にすると、最大元も最小元もありません。

極小元が無数にある順序がほしければ、順序 R を次のように定義できます。まず補助の集合 M_x を定義します。区間 (0, 1) のすべての x について、集合 M_x = {y | y = x + n} を定義します。ここで n は0以上の整数です。これにより、例えば次のような集合が得られます。

$$\begin{array}{rcl}{M}_{0,5}& =& \{0.5;1.5;2.5;3.5;\dots \}\\ M_{0,7}& =& \{0.7;1.7;2.7;3.7;\dots \}\\ M_{0,8}& =& \{0.8;1.8;2.8;3.8;\dots \}\end{array}$$

各集合 M_x にふつうの大小関係を定義し、それを R_x とします。最後に、これらの順序の和集合 R = ∪ R_x をとります。この順序では、もとの鎖の中でしか比較できません。$0.5\leqq 2.5$ かどうかはわかりますが、$0.5\leqq 2.7$ かどうかはわかりません。この二つの数は同じ集合 M_x に属していないので、その関係が定義されていないからです。

この順序関係では、区間 (0, 1) のすべての要素が極小元になります。

ハッセ図

順序集合はハッセ図でかき表せます。ハッセ図はグラフの一種で、頂点が集合の要素を表します。頂点の組 (a, b) を結ぶ辺は、a < b であり、かつ a < c < b となる c が存在しないことを表します。つまり、要素 a と b の間には他の要素がありません。また、グラフでは頂点 a を頂点 b より下にかかなければなりません。ハッセ図の例を見てみましょう。

このハッセ図は、順序集合 {A, B, C, D, E, F} を表しています。ここでは A < B、B < E が成り立ちます。当然 A < E も成り立ちますが、この二つの頂点の間に辺はありません。A < B < E となる頂点 B があるからです。要素 E と D は比較できません。どちらも他方の上にも下にもないからです。

ハッセ図はふつうこのようにきれいに整えてかきますが、必ずしもそうする必要はありません。前のハッセ図は次のようにかくこともできます。

別の例として、集合 A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} を考えます。これは 60 の正の約数全体の集合です。約数・倍数の関係による順序は次のように表せます。

約数・倍数の関係による順序とは、a が b を割り切るとき、かつそのときに限り (a, b) ∈ R となる順序です。図を見ると、どの数もその上に、自分が割り切る数があることがわかります。例えば 6 の上には 12、30、60 があります。4 の上には 12、20、60 があります。他も同様です。一方、3 の上には 10 がありません。3は10を割り切らないからです。図では 10 が 3 より上にかかれていますが、3から10へ「下から上へ」向かう線はないので注意しましょう。3 から上だけに進むと、15 と 6 へ行け、そこから 30 へ行けます。10 へは一度下に降りなければたどり着けませんが、それは許されません。