何故，厳密で弱い順序が重要なのか？

さて，ようやく自分の疑問の核心部にたどり着きました．
厳密で弱い順序が何故STLにおいてここまで重要視されているのか，多くの書籍は「数学的な詳細には立ち入らない」としてこの部分の議論を避けているので，ここではあえてそれに踏み入ってみます．
厳密で弱い順序で私が一番疑問に思っていたのが最後の条件です．

equivalenceに対する推移性：xとyがequivalentでありyとzもequivalentであるとき，xとzもequivalentである

この条件はいったい何なのか？何のために必要なのか？ということが非常に疑問だったのです．
これは，逆に言えばこの条件を外すとどうなるのか？ということにもつながります．実はこの条件を厳密で弱い順序から外した以下の3つの定義は「半順序（Partial Order）」と呼ばれる順序の種類の定義になります．

（非）反射性：f(x, x)は常にfalseである
（非）対称性：xとyが等しくないとき，f(x, y)がtrueならば!f(y, x)もtrueである
推移性：f(x, y)がtrueでありf(y, z)がtrueであるならf(x, z)はtrueである

自分の疑問は「何故この3条件だけではダメなのか」と言い換えることもできます．
また，もう一つの大きな疑問がありました．以下のことはどうやって証明できるのか，ということです．
a < b, b <> c $\Rightarrow$ a < c
ここでは，分かりやすく書くためにf(a, b)をa < b，bとcがequivalentであることをb <> cと書いています．この関係を仮に「equivalenceを通した順序の推移性」と呼ぶことにします．
これが何故重要なのか？今以下のような場合を想定してみます．
a < b <> c < d
これは，a, b, c, dをソートした結果の隣接要素間の順序関係を表したものです．bとcがequivalentだったというわけです．
で，sortしたということは当然a < c, a < d, b < dであるべきです．これが保証されるためにはどうしても「equivalenceを通した順序の推移性」が必要です．
つまり，sortの事後条件として隣接要素間の順序だけを見れば良い，ということを保証するためにはどうしても「equivalenceを通した順序の推移性」が必要になります．
今日暇な時間があったのでその時間の間このことをぼけ〜っと考えていたのですが，最終的に上の2つの疑問は同時に解決しました．
結論は，「equivalenceの推移性」と上の「equivalenceを通した順序の推移性」は同値である，です．証明は余白が無いので省略します・・・簡単な証明ですがｗ．
これによって，厳密で弱い順序は「equivalenceを通した順序の推移性」を保証する，ということになります．従って，厳密で弱い順序によるソートの事後条件を確認するためには隣接要素間だけをみれば良い，ということになります．
さらに言うと，この「equivalenceを通した順序の推移性」はソートを行う多くのアルゴリズムにとって非常に重要な意味を持ちます．何故かというと，quick sortのように陽に全ての異なる要素間を比較しないソートでは部分的な要素の順序と順序の推移性によって全体の順序関係が保証されるということを仮定しているので，「equivalenceを通した順序の推移性」が無いと結果的にquick sortではsortされない（また他のsortの機能，例えばmulti_setやmulti_mapの実装における赤黒木によるkeyの順序の保証などが働かない）ということになります．
＃追記：別の言い方をすると「ソートアルゴリズムの複雑性がO(N logN)であるための必要最低限の要求こそ『厳密で弱い順序』である」といえる．
これが，STLで厳密で弱い順序が強調されている理由である，と私は結論付けました．
(´-｀).。oＯ（多分，ものの本読めばこういう事ってさらっと書いてあるんだろうなぁ・・・）
最後に，上のことを例示するコードとして，ただの半順序でstd::sortを使った場合の例を示します．ここで使っている半順序f(a, b)は「aがbの約数ならtrue，それ以外はfalse（ただし非反射性が要るのでa == bならfalse）」というものです．これを「順序」と呼ぶのは非常に違和感を感じると思いますが，実際これは厳密で弱い順序から最後の条件だけを除いた，半順序の3条件を全て満たす「順序」です（それにこの「順序」は半順序としては代表的なものです）．

#include 
#include 
#include 
#include 
#include 

struct is_measure
  : std::binary_function
{
  bool operator()(int lhs, int rhs) const
  {
    return lhs != rhs && rhs % lhs == 0;
  }
};

int main(int argc, char *argv[])
{
  using namespace std;

  vector v;

  for(int i = 20; i >= 1; --i){
    v.push_back(i);
  }

  sort(v.begin(), v.end(), is_measure());

  copy(v.begin(), v.end(), ostream_iterator(cout, "\n"));

  return 0;
}

自分の環境では，上のコードは以下のように表示されました．

1, 5, 10, 20, 19, 18, 17, 16, 14, 13, 12, 11, 9, 8, 7, 6, 4, 3, 2

ちなみに上のコードによって期待している「ソート」の結果とは，「ある要素の約数が必ずそれよりも前にある」です．ソートが全く機能していないのは一目瞭然ですね（ですか？）．これはis_measureが厳密で弱い順序の4つ目の条件を満たしていない「順序」だからです（注意：これがちゃんとソートされないのは，std::sortの実装がクイックソートだからだ，とも言えます．バブルソートなどのアルゴリズムでは正しく「ソート」されます）．
逆に，厳密で弱い順序の条件を満たした順序によるソートの例として，以下のコードを挙げておきます．

#include 
#include 
#include 
#include 
#include 

struct modulo_less
  : std::binary_function
{
  bool operator()(int lhs, int rhs) const
  {
    return lhs % 3 < rhs % 3;
  }
};

int main(int argc, char *argv[])
{
  using namespace std;

  vector v;

  for(int i = 20; i >= 1; --i){
    v.push_back(i);
  }

  sort(v.begin(), v.end(), modulo_less());

  copy(v.begin(), v.end(), ostream_iterator(cout, "\n"));

  return 0;
}

上の結果がきちんと「ソート」されているのが分かりますか？（ちなみに上のソートではequivalenceが3の剰余系に対応しています）