12/27更新: 図に文言を追加しました。

f:id:nunuki:20161227000205p:plain

半対称律?半順序?なにそれおいしいの?
Wikipediaを見てもよくわからない
半順序と弱順序を間違えて恥かいた

という方のために(?)、二項関係、順序関係についてまとめました。

特に、厳密な定義を意識せずに普段から二項関係を使っているであろうプログラマの方が少しでも理解・整理しやすいように解説しました。

TL; DR

集合Pに二項関係「」が定義されているとき、Pの異なる2要素x,y の関係は次の4つのどれか:
- x<=y が真(true)、かつ y<=x が真(true): 同値な関係
- x<=y が真(true)、かつ y<=x が偽(false): y は x より真に大きい
- x<=y が偽(false)、かつ y<=x が真(true): x は y より真に大きい
- x<=y が偽(false)、かつ y<=x が偽(false): x と y は比較不能
上記４つの関係を許すか禁止するかで次の５種類の二項関係が定義さている。
- 前順序: 真に大小、同値、比較不能すべてOK。
- 弱順序: 比較不能はNG。必ずどちらかが真に大きいか、同値な関係にある。
- 半順序: 同値な関係はNG。必ずどちらかが真に大きいか、比較不能である。
- 全順序: 比較不能も同値もNG。必ずどちらかが真に大きい。
- 同値関係: 真に大小はNG。必ず同値な関係か、比較不能のどちらか。
上記５つの二項関係には、さらに、２つの制約がある。
- 推移律: 「３すくみ」の関係は存在しない。
- 反射律: 各要素は自分自身と同値

二項関係

まず、ある集合Pの2項関係(P,≦)を考えます。すなわち、集合 Pに対して、次のような演算子が定義されていると考えてください。

bool operator <=(P x, P y);

さて、この演算子の戻り値はtrue かfalse の２つですが、二つの要素x, yが与えられたとき、その比べ方は x<=y とy<=x の2通りのがあります。

このとき、xとyの間には、x<=y およびy<=x の真偽の組み合わせで4通りの関係性があることがわかります。ここでは、便宜上、次のように呼ぶことにします。

x<=y	y<=x	名前
true	true	xとyは同値な関係
true	false	yはxより真に大きい
false	true	xはyより真に大きい
false	false	xとyは比較不能

ここで、「比較不能」や「同値」という関係が出てきましたが、実際の問題を考えるときには、これらの関係が現れると不都合なことがあります。

たとえば、配列のソートをしようとしたとき、比較不能な要素が現れるとどちらを先に並べてよいか困りますね？

また、「同値な関係」とは、たとえば、「AさんとBさんは違う人だが、年齢だけ見るとどちらも10歳で見分けがつかない」といった状況で、たとえば、小学校の名簿の中からAさんを探すときに、年齢を使って二分探索しようとすると、小学校に10歳の児童はたくさん居ますので、 Aさんを見つけることはできませんね。この場合、年齢ではなく、(学年, 出席番号) という組を辞書順で比較するような順序関係を考えると Aさんと学年と出席番号が両方等しい人は学校に居ませんから、Aさんを一意に見つけ出すことができます。

実は、弱順序、半順序、全順序 というのは、「比較不能」や「同値」が禁止されているということを意味しているのです。

このことを見ていく前に、まず、「比較不能」も「同値」も禁止されていない 前順序 の満たすべき性質についてまとめ、次に弱・半・全順序をまとめていきます。

反射律・推移律と前順序

最も条件の緩い順序関係である、前順序 (preorder)とは、「反射的かつ推移的な２項関係」のことです。

「反射的」「推移的」という新しい言葉が出てきましたが、これらは前順序をはじめ、全ての順序関係で成り立つべき性質です。

反射律

全てのx について、x <= x が成り立つ。

これは、xが自分自身と同値な関係にある ことを意味しています。

推移律

x <= y かつ y <= z ならば、x <= z が成り立つ。

これは、じゃんけんのような「3すくみ」のような関係が無いことを意味しています。 (グー <= パーかつ、パー <= チョキだが、グー <= チョキ は成り立たない。)

完全律と弱順序

既に述べた通り、前順序は「反射的かつ推移的な２項関係」ですが、「比較不能」や「同値」が禁止されていない最も緩い条件の順序関係でした。

弱順序 (total preorder; (non-strict) weak order) とは、「比較不能」を禁止する条件である「完全律」を前順序に課したものです。

完全律の定義は以下のとおりです。

完全律

全てのx, y について、x<=y またはy<=x のどちらか一方は真である。

この定義は、対偶をとると、

全てのx,yについて、「x<=yとy<=xがどちらも偽である」は偽である

となりますので、すなわち、

「xとyは比較不能である」となるx,y は存在しない

ということを言っています。

反対称律と半順序

次に、「同値な関係」を禁止しましょう。異なる２要素の同値な関係を禁止する条件を「反対称律」といい、前順序にこれを課した順序関係を半順序 (partial order) と言います。

反対称律

全てのx, y について、x<=y かつ y<=x ならば、a=b である。

この定義は

xとyが同値な関係ならば、x とy が等しい

ということですので、対偶を取れば

xとyが相異なる２要素ならば、xとyは同値な関係ではない

ということを言っているのが分かります。

全順序

さて、弱順序と半順序がそれぞれ「比較不能」と「同値な関係」を禁止した順序関係であることを述べました。

全順序 (total order) は、「比較不能」と「同値な関係」の両方を禁止した順序関係になります。

すなわち、２項関係 <= が全順序であるならば、相異なる２要素x, y は、必ずどちらかが真に大きいということです。

対称律と同値関係

さて、半順序とは「反対称律」を課した前順序であることを述べましたが、「反対称律」の「反」とはどういうことなのでしょうか？

「反」があるのだから、普通の「対称律」もあるのでは？という疑問が湧いてきます。

結論から言うと、「対称律」という条件も存在して、反対称律の代わりに対称律を課した前順序として「同値関係」という二項関係があります。

そもそも、反対称律とは、何が「反」なのでしょうか？

上述の反対称律の定義を再び変形していくと、

相異なるx,y について、y<=x が真なら、x<=y は偽である。

となります。

「y<=x が真なら、x<=y は偽である」の部分を見ると、「xとyの順番を入れ替えると、真偽が入れ替わる」ということを意味しています。これが「反」対称と言われる所以です。

では、対称律はどうなっているでしょうか？

対称律

全てのx, y について、x<=yが真ならば y<=xも真である。

つまり、「xとyの順番を入れ替えても、真偽は変わらない」と言っているのです。

ここで、対称律には「相異なるx,y について」という条件がありませんが、 xとyが等しいとき、x<=x の「xとxの順番」を入れ替えても、真偽が変わらないのは当たり前ですから、書く必要が無いのです。

さて、対称律が成り立っているとき、 x<=yまたはy<=xのどちらかが成り立つと、自動的にもう一方も成り立ちますから、「xとyのどちらかがもう一方よりも真に大きい」という状況は起こりません。

つまり、対称律を課した順序関係である「同値関係」とは、とは、2つの要素間で「どちらかが真に大きい」という関係を禁止し、「同値な関係」または「比較不能」の２種類の関係だけを許す二項関係のことなのです。

また、同値関係では、x<=y とy<=x を区別する必要がありませんから、通常 $\leq$ という記号は用いず、 $x \sim y$ といった記号を用いることが多いです。

まとめ

順序関係(前順序)とは

反射的(各要素は自分自身と同値)で推移的(３すくみがない)な２項関係

のことでした。

このような二項関係で相異なる２要素 x, y を比較した時、 x<=y とy<=x の真偽の組み合わせによって４つの関係性（xが真に大、yが真に大、xとyは同値、xとyは比較不能）があります。

これら４つの関係性のうち、いくつかを禁止する条件を加えることによって５種類の二項関係を得ました。

	真に大小	同値な関係	比較不能
禁止する条件	対称律	反対称律	完全律
前順序	◯	◯	◯
弱順序	◯	◯	×
半順序	◯	×	◯
全順序	◯	×	×
同値関係	×	◯	◯

最後に、これらの包含関係をまとめておきます。