[C++]狭義の弱順序(strict weak orderings)とは?

STLにおいて値の大小比較が必要なところでは、operator<を使うかCompare型の関数オブジェクトを渡すことで任意の型についての順序を決定できるようになっています。その時、その順序付けの性質として「狭義の弱順序(もしくは厳密で弱い順序、strict weak orderings)」が要求されますが、これがどういう意味が一目でわかるのは数学科行った人くらいでしょう。cpprefjpのAlgorithmヘッダのところには一応説明が書いてありましたので見てみますと
algorithm - cpprefjp C++日本語リファレンス

二分探索以外のアルゴリズムでは、comp は「狭義の弱順序 (strict weak ordering) 」を示さなければならない。

ここでの用語「狭義 (strict) 」 は非反射関係 (irreflexive relation) (全ての x について !comp(x,x) である)の要求を示し、用語「弱 (weak) 」は全順序 (total ordering) ほど強くはないが半順序 (partial ordering) よりは強い要求を示す。!comp(a, b) && !comp(b, a) として equiv(a, b) を定義する場合、用語「弱」の要求は comp と equiv の両方が以下のように推移的関係 (transitive relations) となることである。

comp(a, b) && comp(b, c) は comp(a, c) を意味する
equiv(a, b) && equiv(b, c) は equiv(a, c) を意味する

読む人が読めばわかるのだろうか・・・。この後にも例が示されているのですが、少なくとも私にはさっぱりワカラナイ。なので、分からないなりに調べてみたことのまとめです。

順序

順序とは、ある値の大小や集合の包含などの関係性を一般化したもので、集合上の二項関係(引数2つを取りboolを返す関数)によって定義されます。4つの性質(順序の公理)があり、満たす性質によって主に4つの種類の順序が定義されます。

集合PとP上の二項関係Rについて

  1. 反射律:P の任意の元 a に対し、a R a が成り立つ。
  2. 推移律:P の任意の元 a, b, c に対し、a R b かつ b R c ならば a R c が成り立つ。
  3. 反対称律:P の任意の元 a, b に対し、a R b かつ b R a ならば a = b が成り立つ。
  4. 全順序律:P の任意の元 a, b に対し、a R b または b R a が成り立つ。

もはやなんのこっちゃでしょう。少し具体的に、二項関係Rを≦(小なり)とします。集合Pは例えば実数だと思ってください。成り立つ、とは結果が真(true)になる、という事です。

  1. 反射律:P の任意の元 a に対し、a ≦ a がtrue。
  2. 推移律:P の任意の元 a, b, c に対し、a ≦ b かつ b ≦ c ならば a ≦ c がtrue。
  3. 反対称律:P の任意の元 a, b に対し、a ≦ b かつ b ≦ a ならば a = b がtrue。
  4. 全順序律:P の任意の元 a, b に対し、a ≦ b または b ≦ a がtrue。

少し見晴らしがよくなりました。これらの公理の満たし方によって、前順序、半順序、弱順序、全順序の4つの順序が定義されます。

前順序(preorder)

二項関係R(≦)が前順序であるとは、反射律と推移律を満たすことを言います。

  • 反射律:P の任意の元 a に対し、a ≦ a が成り立つ。

Pのある要素について、自分自身との関係性を表しています。自分自身との順序は常にtrueです(実数aについて≦の場合、aは常にa以上となる)。

  • 推移律:P の任意の元 a, b, c に対し、a ≦ b かつ b ≦ c ならば a ≦ c が成り立つ。

順序が一方向性であることを言っています。≦でいうなら、bはaより大きく、cはbよりも大きい、その時、aがcより大きいという事があってはならない、というルールを表しています。

見てみると割と当たり前、これだけで順序付けが出来ていそうな雰囲気があります。しかし、抜け穴があり、残りの種類の順序ではその穴を埋めていきます(現代の抽象的な数学はこのような穴を埋める作業を突き詰めます)。

また、残り3つの順序は全てこの前順序の性質を満たしています。つまり、前順序はその他の順序を包含しています。

半順序(partial order)

二項関係R(≦)が半順序であるとは、前順序であり、反対称律を満たすことを言います。

  • 反対称律:P の任意の元 a, b に対し、a ≦ b かつ b ≦ a ならば a = b が成り立つ。

この順序によって、どういう時に二つの値が等しいと言えるか?を定義しています。
この対偶を取って言い換えると

  • 反対称律:P の任意の元 a, b に対し、 a ≠ b ならば a ≦ b と b ≦ a はどちらか一方のみが成り立つ(同時に成り立たない)。

という意味でもあります(こちらの方が分かりやすい?)。

つまりは、異なる要素(a ≠ b)間の関係(R)は同値になることがないという事で、同値となれる値を制限しています。
P上の異なる二要素a,bを取ってきた時に、a=bとなるかは=の取り方によりますが、反対称律を導入することでa=bとはならないことを定めています。
実数でいうなら1と同値(=)なのは1だけであるように、実数のいかなる要素も自分以外の値とは同値になりません。これが反対称律を満たしている、という事です。

全順序(total order)

二項関係R(≦)が全順序であるとは、半順序であり全順序律を満たしたものです。つまりは、最初に上げた4つの公理をすべて満たしている順序です。

  • 全順序律:P の任意の元 a, b に対し、a ≦ b または b ≦ a の少なくともどちらか一方が成り立つ。

任意の二つの要素間の比較が不可能、というケースが存在しないことを言っています。全順序であればPから取ってきた二つの要素は必ず比較ができる(a R bとb R aのどちらかは必ずtrueとなる)訳です。

全順序であるとは、任意の要素について自分自身との順序Rはtrueであり、順序Rの方向は一方向。かつ、異なる値は同値にならず、比較不能な要素が存在しない。
となり当然、4つの順序の中で最も厳しい要求をする順序となるため、集合によってはどうしても満たすことが出来ない場合が多々あります。

弱順序(weak order)

二項関係R(≦)が弱順序であるとは、半順序であり、次の性質を満たすことを言います。

  • 比較不能性の推移律:P の任意の元 a, b, c に対し、aとbが比較不能(a ≦ b も b ≦ a もともにfalse)かつ bとcも比較不能ならば、aとcも比較不能である。

言い換えてみると

  • 比較不能性の推移律:P の任意の元 a, b, c に対し、a ≦ b ならば、a ≦ c または c ≦ b の少なくともどちらか一方が成り立つ。

あるいは

  • 比較不能性の推移律:P の任意の元 a, b, c (a ≠ c かつ b ≠ c) に対し、aとbが比較不能 ならば、次の少なくとも一つが成り立つ
    • a ≦ c かつ b ≦ c
    • c ≦ a かつ c ≦ b
    • cとaは比較不能 かつ cとbも比較不能

とてつもなく分かりにくいですが、これは比較不能な要素について同列とする事を認めるということです。比較不能性の推移とは、比較不能な要素同士を同値だとみなして順序付けするために必要な要求です。
どういう事でしょうか?
例えば、集合Pから3つの要素 a, b, cを取り出して並べてみようとしてみます。
この時、比較不能な要素は同値としてまとめてしまう事を決めておきます。

まず、aとbが比較不能である事が分かったので、aとbをまとめます。
→(a b)
次に、bとcも比較不能であったので、bとcもまとめます。
→(a b c)
最後に、aとcを比較したところ、比較することが出来ました(仮にa < cとしておきます)。なので、a < c と並べました。
→a < c
しかし、この時bはどこに行くのでしょうか?比較不能な要素同士は同値として扱うのでa及びcとまとめる必要があります。
→(a b) < (b c)
これは一体何でしょうか?いうなれば矛盾です、これでは並べられません。
この様な事が起きることを防ぐためには比較不能であることが推移する必要があることが分かると思います(この例ならaとcも比較不能でなければならない)。

たとえが分かりづらい?そんな気もします・・・。
現実的な弱順序を考えると、何かしらのレース(例えば100m走)の結果が分かりやすいでしょうか。
5人が走って、1着は1人だったが、次点で同着が二人おり、残り3人はそれぞれ遅れてゴールした、とします。
二着が二人いるという事はすなわちこの二人の順位は比較不能です。したがって、この結果は全順序ではありません。しかし、比較不能(同着)を同値(二位)として扱っています。これが弱順序です(すなわち半順序でもありますが、半順序ではこの二人を1位と5位として扱う事も許してしまいます)。
どうやって二位であることを決定したのかと言えば、1位と4位との比較が可能だからです。

すなわち弱順序とは、比較不能なケースを同値として扱い、その順序は他の順序との相対的な関係によって定義するものです。

ご理解いただけたでしょうか?少しは何かつかめていると幸いです・・・。
全順序では比較不能なケースを認めません、半順序では比較不能なケースを許容しますが順序を与えません。弱順序では半順序に制約を加えることで比較不能なケースに順序を与えています。
つまり
前順序→半順序→弱順序→全順序
の順番に制約が強くなっています。そしておそらく、全順序ほど強くなく、半順序ほど弱くなくという制約から弱順序となったのでしょう(個人の感想です)。

狭義の(strict)

二項関係Rが狭義の(半|弱|全)順序であるとは、Rにおいて等しいことを許容しない順序である(a = bのとき、a R bはfalseとなる)ことを言います。これまで定義してきた順序に対して反射律を次のような非反射律と入れ替えたような順序の事です。

  • 非反射律:P の任意の元 a に対し、a<a が成り立たない(常にfalse)。

難しいことはなく、≦に対する<がこれに当たります(≧に対する>も同様)。言葉でいうなら、以上(以下)に対して、超える(未満)、という関係。

狭義の弱順序(strict weak ordering)

さて、ここまで読んで理解していればこの言葉の意味も分かっているのではないでしょうか?(説明が悪くて理解できない場合はごめんなさい)

狭義の弱順序が満たす性質を並べてみると

  1. 非反射律:P の任意の元 a に対し、a<a が成り立たない(常にfalse)。
  2. 推移律:P の任意の元 a, b, c に対し、a < b かつ b < c ならば a < c が成り立つ。
  3. 反対称律:P の任意の元 a, b に対し、a < b かつ b < a ならば a = b が成り立つ。
    • 反対称律:P の任意の元 a, b に対し、 a ≠ b ならば a < b と b < a はどちらか一方のみが成り立つ(同時に成り立たない)。
  4. 比較不能性の推移律:P の任意の元 a, b, c に対し、aとbが比較不能(a < b も b < a もともにfalse)かつ bとcも比較不能ならば、aとcも比較不能である。

のようになります。

これらの事からC++標準が要求する狭義の弱順序とは

まず、STLの文脈ではoperator<かそれと同等なCompare型の関数オブジェクトを要求するので、この二項関係は<(≦)となります。そして

  • 狭義の:<(≦ではない)
  • 弱順序:比較出来ない要素は同値として並べる(他の要素との相対的な順序をつける)

となります。
読み解いてしまえば簡単な事というか、順番に並べる、という事を考えた時に当たり前のことを言っています。
各種ソートアルゴリズムを考えた時に、暗黙的にこれを要求していることも分かるのではないでしょうか?
例えば、実数上の<は全順序ですが、その値を持ってきた集合(コンテナ)は全順序ではありません(重複が考えられるため)。それをソートしようとしたときに(狭義の)弱順序が自然である事が分かるでしょう。


※追記
狭義の弱順序が満たす一番最後の性質「比較不能性の推移律」ですが、文脈によっては次のような形になっていることがあります。

  • 同値性の推移律(Equivalenceにおける推移性):P の任意の元 a, b, c に対し、a = b かつ b = c であるならば、a = c が成り立つ。

推移律ではありますが、比較不能性ではなく同値性になっています。この場合に、狭義の弱順序という言葉の意味するところはどう変化するのでしょうか?
しかし、その場合でもその他の性質は同じ意味であり、反対称律を満たしているはずです。そして、比較不能な要素が同値であるという性質は反対称律の特別な場合として定義されます(いわば反対称律から導出されます、上では説明しませんでしたが・・・)。
つまり、反対称律を満たしていれば比較不能な要素は同値であるとみなすことが出来て、比較不能な要素同士は同値であるので、比較不能性の推移=同値性の推移、となる事が分かります。
なので、結局同じ意味になります。


参考文献:
http://www.geocities.jp/abreverse/ordering/ordering.pdf
順序集合 - Wikipedia
Weak ordering - Wikipedia
半順序?弱順序?二項関係・順序関係まとめ - ぬぬろぐ