はじめに

A=B、A=Cであるとき、B=Cとなるとは限らないという記事が出ていますが, すこしこの=や⊆という二つの値の関係を表す演算子についてこの際だからちょっとお話ししようと思います。

これを知っていると, いくつかプログラム上でも有用なことがあるので, それも併せて紹介できたらと思います。

二項関係

a=bやX⊆Yというような二つの値の間の関係を示すものを数学では二項関係といいます。（ここで詳しく厳密な定義はしません。）
例えば,1=1や{1,2}⊆{1,2,3}というものですね。
ちなみに1=2と書くこともできます。（これは偽の命題になりますね。）

一般にこの=や⊆のような演算子を一般化してRと書くことが多いのでそれに倣ってしばらくはaRbと書くことにします。

少し難しいことを書いてしまいましたがプログラマ的に言えば=演算子のような2つの値をとってその関係によってtrueかfalseを返す演算子やメソッドだと思ってください。
aRbというものはa,bという値を引数にとってある条件に当てはまっていればtrueさもなくばfalseを返すRというメソッドだと思ってもらえれば十分です。

疑似コードで書くと…

bool R(a,b){
  if(a,bが何かの条件を満たす){
    return true;
  }else{
    return false;
  }
}

というようなものが二項関係aRbだと思ってください。また, ここではRが具体的にどのようなものかは一切言及していないことに注意してください。また, a,bが整数なのか実数なのかはたまたほかの何かであるかも言及していません。

代表的な二項関係の性質

さて, この二項関係を考えていくときにこの関係にいくつか条件(性質)を付けることを考えます。そうすることで議論を先に進めていきましょう。代表的なものをいくつか紹介します。

反射律

aRaが常に成り立つ性質を反射律といいます。

例として,一般的によく言う=(等号)はこれを満たしますね。1=1ですし2=2です。(1,2)=(1,2)でもあります。
（一般的によく言うというのはまだ=をこの記事で定義していないからですが, このような一般的に使われている記号は意味の定義なしに使っていこうと思います。）

疑似コードは

if(R(a,a)){ /* 必ずここを通る */ }

これを満たさない関係があるのか！？と聞かれるとあります。

非反射律

aRaが常に成り立たない性質を非反射律といいます。

例としては, ≠がありますね。例えば, 1≠1は成り立ちません。

疑似コードは

if(!R(a,a)){ /* 必ずここを通る */ }

対称律

aRbならばbRaが常に成り立つ性質を対象律といいます。

先ほどお話しした, =はこれを満たします。≠もこれを満たします。プログラマ的には引数を入れ替えても結果が変わらないという素敵な性質ですね。

疑似コードは

if(R(a,b) == R(b,a)){ /* 必ずここを通る */ }

一方不等号≦はこれを満たしませんね。1≦2ですが2≦1を満たしません。
不等号に関する関係も後で紹介しますが, もう一つ=に関する重要な性質を先に紹介します。

推移律

aRbかつbRcならばaRcが常に成り立つという性質です。言い換えるとRは三段論法が成り立つ関係です。

=も当然成り立ちますし,≦や（集合の）⊆もこれを満たしますね。1≦2かつ2≦3ならば1≦3は真です。
一方≠はこれを満たしません。反例として1≠2かつ2≠1ならば1≠1は偽になりますよね。

反対称律

前述した対称律の対になる関係で,
aRbかつbRaならばa=bが常に成り立つ性質を言います。
言い換えればaRbかつa≠bならばbRaは常に成り立たない性質とも言えます。

≦や⊆はこれを満たしますね。1≦bかつb≦1が成り立つのはb=1のときだけですよね。
一方aがbより真に大きいかどうかを示す演算子＜はこれを満たさないことがわかります。

全順序律

任意のa.bに対してaRbまたはbRaが成り立つ性質を全順序律といいます。

これはどういうことかというと⊆は集合の大小を決める演算子ですが,例えば{1,2}と{1,3}は{1,2}⊆{1,3}でもなく{1,3}⊆{1,2}でもないですよね。
一方≦はどちらかが大きいかがはっきりと決まります。
つまりこれは, 順序を決めることができるという性質になります。

いろいろな関係

さて, この複数の性質を組み合わせることによっていくつか代表的な性質を持つ二項関係を構成することができます。
表題の同値関係もここで紹介することにします。

同値関係

同値関係とは次の3つの性質を満たす二項関係≡（同値関係ではよくRの代わりに≡が使われます）のことを言います。

1. 反射律(a≡aが真)
2. 対称律(a≡b⇒b≡a)
3. 推移律(a≡bかつb≡c⇒a≡c)

この関係の例としては何度もあげている=のほかに「AさんとBさんの出身県が同じという関係」や2つのユーザーレコードa,bの間に「同じ誕生月かどうか」という関係,二つの文字列a,bの間で「頭文字が同じ」という関係などもあります。

この関係のプログラムで扱ううえで重要な性質として, この関係は集合を「グループ化することができるという」性質を持ちます。このグループを同値類と言ったりしますが要するにgroup byができる関係を示します。
どのように作るかというと, aRbを満たせばaとbは同じグループ,満たさなければ別のグループになります。

実際に先ほど紹介した例はすべてグループを構成できますよね？(=は1グループ1要素,同じ県の人でグループを作る,同じ誕生月で作る,同じ頭文字で作るとできます。)

表題の証明については次の項目で行います。が, 同値関係についてはグループを作れるという性質が大事なんため覚えていてください。

半順序関係

半順序関係とは次の3つの性質を満たす二項関係≤(環境依存文字)のことを言います。

1. 反射律(a≤aが真)
2. 反対称律(a≤bかつb≤a⇒a=b)
3. 推移律(a≤bかつb≤c⇒a≤c)

この関係の例としては先ほど出した集合の包含関係を示す⊆です。また例えばRは二つのベクトル(a1,a2),(b1,b2)に対して, a≤bをa1≦b1かつa2≦b2と定義する関係もこれを満たします。

ここで気を付けるべきは, 要素同士を必ずしも比較できるとは限らないということです。
このようなものを扱うときは注意してください。
ただし, ゲームなどにおいては必ずしも順序がつけられないほうがゲームとして深みが出たりはするかもしれませんね。

全順序関係

全順序関係とは反順序関係にさらに全順序律を追加したものです。
つまり, 任意のa,bに対してa≤bまたはb≤aのどちらかを満たします。

この関係の例としては, 先ほどから何度も出ている実数や整数などの不等号≦が代表選手です。
ほかにもユーザーAとBの館員番号を比較するとか。文字列a,bを辞書順でソートしたときにbが後にくるとか, 要するに完全に一列に順番を付けることができるものを言います。

もちろん必ず比較できることが保証されますし。この関係を使ってソートもできます。
プログラマとしては反順序関係よりよっぽど扱いやすいと思います。

本題 =が「同値関係」ならばA=BかつA=CならばB=Cが成り立ちます！

本題の証明をします。

同値関係とは改めてこの性質を満たします。

1. 反射律(a≡aが真)
2. 対称律(a≡b⇒b≡a)
3. 推移律(a≡bかつb≡c⇒a≡c)

対象律a≡b⇒b≡aが成り立つため
推移律a≡bかつb≡c⇒a≡cはb≡aかつb≡c⇒a≡cとできます。

よって=が同値関係であればA=BかつA=CならばB=Cが成り立ちます！

以上ですね！！

え？反射律使ってないじゃんって？
それは実際正しくて実は=が同値関係であるというのは強めの主張であり, 実際反射律がなくてもこれを満たせます…が反射律ないと結構直感的に扱うのが面倒な関係もつくれるようになってしまうので, 今回はこれを入れてみました。

ちなみにおおもとのツイートで⊆はa⊆b,a⊆cでもb⊆cではないんですよ。とありましたが, これは推移律はあってお対象律を⊆は持っていないからなんですね。