なぜ同値関係は自己関係なのか

rap/Eq.ts · sueka/rap を作ったときに考へてゐたことを思ひ出したので書き残しておく。

¶ 定義

同値関係

集合 𝑋 上の二項関係 ~ が反射的、対称的かつ推移的なときiff、~ を 𝑋 上の同値関係と言ふ。𝑎 ~ 𝑏 のとき、「𝑎 と 𝑏 は同値である」などゝ言ふ。（𝑎, 𝑏 は 𝑋 の元。）

型

値の集合と演算の組を型と言ふ。例へば、ブール型は、{True, False} といふ値の集合と論理否定や論理和などの演算からなる。〈2の補数表現された32ビット整数型〉みたいなものも型である。

部分型

型 𝑆 のオブジェクト 𝑜₁ にそれぞれ、型 𝑇 によって定義された全てのプログラム 𝑃 について、𝑜₁ が型 𝑇 のオブジェクト 𝑜₂ の代はりに使はれても 𝑃 の動作が変はらないやうな 𝑜₂ が存在するなら、𝑆 は 𝑇 の部分型である。

 原文

If for each object 𝑜₁ of type 𝑆 there is an object 𝑜₂ of type 𝑇 such that for all programs P defined in terms of 𝑇, the behavior of P is unchanged when 𝑜₁ is substituted for 𝑜₂, then 𝑆 is a subtype of 𝑇.

Data Abstraction and Hierarchy (Liskov, 1988) より。

計算機プログラムでは、2つの項が同じであることを表現する手段が2つある。等価性^[1]と同値関係である。2つの値が同じ解釈^[2]を持つときiff、それらの値は等価である。

値には対応する抽象実体がある。抽象実体とは、例へば、13、青などである。ある値に対応する抽象実体をその値の解釈と言ふ。値の集合と抽象実体の集合の上の二項関係が左一意的^[3]なときiff、その型は一意に表現されてゐる。同様の関係が右一意的なときiff、その型は一義的である。一義的でない型は曖昧である。

一意に表現されてゐない型の例としては IEEE 754 浮動小数点数型や大文字と小文字を区別しない文字列型、曖昧な型の例としては2桁の数値として一世紀以上の期間の暦年を表現している型^[4]がある。

    graph LR
      subgraph Value[値]
        VPlusZero(+0)
        VMinusZero("-0")
      end
      subgraph AbstractEntity[抽象実体]
        AeZero(0)
      end
      VPlusZero --> AeZero
      VMinusZero --> AeZero
  

    graph LR
      subgraph Value[値]
        V97(97)
      end
      subgraph AbstractEntity[抽象実体]
        Ae1897(1897)
        Ae1997(1997)
      end
      V97 --> Ae1897
      V97 --> Ae1997
  

こゝで、値の集合が {𝑎, 𝑏, 𝑐}、抽象実体の集合が {𝜈₁, 𝜈₂} をそれぞれ含み、値の集合と抽象実体の集合の上の二項関係が {(𝑎, 𝜈₁), (𝑏, 𝜈₁), (𝑏, 𝜈₂), (𝑐, 𝜈₂)} を含むやうな型^[5]を考へる。このとき、𝑎 と 𝑏、𝑏 と 𝑐 はそれぞれ同じ解釈を持つから等価だが、𝑎 と 𝑐 は同じ解釈を持たないから等価ではない。よって、等価性は、同値関係とは異なり、推移律を要求しない^[6]。

これに対して、同値関係は、反射律、対称律および推移律を満たせば十分であり、同値関係にある2つの値が同じ解釈を持つ必要はない。例へば、剰余類は同値類である。整数の加法群 ℤ と偶数の加法群 𝔾 (⊆ ℤ) について、ℤ 上の同値関係 ~ を 𝑎 ~ 𝑏 ⇔ ∃𝑘 ∈ 𝔾 (𝑏 = 𝑎𝑘) と定義する。元 𝑎 の剰余類^[7] 𝑎𝔾 は 𝑎𝔾 = {𝑎𝑘 | 𝑘 ∈ 𝔾} と定義される。つまり、~ は、元 𝑏 が剰余類 𝑎𝔾 に属するときiffに 𝑎 と 𝑏 が同値であるやうな二項関係である。𝑏 = 𝑎𝑘 となる元 𝑘 が存在するのは、𝑎 と 𝑏 がともに偶数であるときと、ともに奇数であるときだけだから、この剰余類は、整数の集合を偶数の集合と奇数の集合に分割する。

剰余類が同値類であることを確認しておく。𝔾 は群なので、

• 演算が結合法則を満たし、
• 単位元が存在し、
• 逆元が存在し、かつ
• 演算に関して閉ぢてゐる。

したがって、

反射律

𝑎 = 𝑎𝑒 となる単位元 𝑒 が存在する。

対称律

元 𝑎^-1𝑏 が存在するなら、その逆元 𝑏^-1𝑎 も存在する。

推移律

演算に関して閉ぢてゐるので、元 𝑎^-1𝑏 が存在し、かつ元 𝑏^-1𝑐 も存在するなら、その積 (𝑎^-1𝑏)(𝑏^-1𝑐) もまた 𝔾 の元である。また、結合法則により、(𝑎^-1𝑏)(𝑏^-1𝑐) = 𝑎^-1(𝑏(𝑏^-1𝑐)) = 𝑎^-1((𝑏𝑏^-1)𝑐) = 𝑎^-1(𝑒𝑐) = 𝑎^-1𝑐 である。

実際、Java では、hashCode を使って整数を剰余類に分割することができる。hashCode の一般契約について、『Effective Java 第3版』（2018年、丸善出版）p. 52 には、

• アプリケーション実行中に同じオブジェクトに hashCode メソッドが繰り返し呼び出された場合、equals 比較で使われるオブジェクトの情報に変更がなければ、hashCode メソッドは常に一貫して同じ値を返さなければなりません。この値は、同じアプリケーションの一回の実行と別の実行で一致している必要はありません。
• 二つのオブジェクトが equals(Object) メソッドにより等しければ、二つのオブジェクトそれぞれに対する hashCode メソッド呼び出しは、同じ整数の結果を生成しなければなりません。
• 二つのオブジェクトが equals(Object) メソッドにより等しくなければ、二つのオブジェクトそれぞれに対する hashCode メソッド呼び出しが、異なる整数の結果を生成しなければならないとは要求されていません。しかし、等しくないオブジェクトに対して異なる整数の結果を生成することは、ハッシュテーブルのパフォーマンスを改善するかもしれないことをプログラマは認識しておくべきです。

とある^[8]が、整数型の hashCode を次のやうに実装したとしても、equals が hashCode を用ゐて正しく実装されてゐるなら、この契約には反さない:

@Override public int hashCode() {
  return value % 2;
}

よって、同値関係は、等価性と異なり、2つの値が同値なら、それらの値は同じ解釈を持つと言ふことはできない。（逆は言へる。）

要約すると、等価性は、

• 反射的、
• 対称的かつ
• 2つの値が同じ解釈を持つときiff、それらの値は等価である、すなはち、
  • 2つの値が同じ解釈を持つなら、それらの値は等価であり、かつ
  • 2つの値が等価なら、それらの値は同じ解釈を持つ

やうな関係であり、同値関係は、

• 反射的、
• 対称的かつ
• 推移的であり、また、
• 2つの値が同じ解釈を持つなら、それらの値は同値である^[9]

やうな関係である。

なほ、等価性は、その型が一意に表現されてゐるか、または一義的なら推移的である。

したがって、同値関係の実装に等価性を用ゐることはできない。仮令その等価性が推移的であっても、派生クラスの等価性は推移的でないことがある。

計算機プログラミングには型指定といふ仕組みがある。型指定は、C++ や Java などの言語ではキャストとも呼ばれる、プログラムの中で、項の型を指定する機能である。型が指定された項には、型検査器がその型を割り当てる。項の本来の型に対して、上位型を指定することをアップキャスト、部分型を指定することをダウンキャストと言ふ。

アップキャストは安全なので、互ひに部分型関係にある型の項が同値かどうかは、レシーバーと実引数のどちらかをアップキャストすれば、安全に調べられる。

しかし、型指定は値に影響を及ぼさないので、実際にかういふ方法で、互ひに部分型関係にある項が同値かどうかを調べるには、部分型の同値関係の検査が上位型の同値関係の検査としても振る舞ふやうに実装されてゐる必要がある。

インスタンス化可能なクラス 𝐴 と 𝐴 を public 継承するクラス 𝐵 があって、𝐴 がメソッド 𝑒𝑞 を持ち、𝐵 が 𝑒𝑞 をオーバーライドする場合、𝐴 が多態的に使はれる場合に備へて、𝐵 の 𝑒𝑞 は WORKS-LIKE-A を満たすやうに、つまり、𝐴 の 𝑒𝑞 としても振る舞ふやうに実装されるべきである^[10]。『Exceptional C++』（2000年、ピアソン・エデュケーション）p. 91 には、

リスコフの IS-A と WORKS-LIKE-A のモデルが成り立つときを除いて、決して public 継承を用いてはならない。オーバーライドされるメンバ関数はすべて、それ以上もそれ以下も要求してはならない。

とあり、同書 p. 108 には、

Robert Martin 氏がよく持ち出す、正方形（square）は矩形（rectangle）だという理由で、Rectangle クラスから Square クラスを継承する考え違いの例がある。これは、数学的には正しいかもしれないが、クラスの関係においては必ずしも正しいとはいえない。たとえば、Rectangle クラスが virtual SetWidth(int) という関数を持っているとしよう。幅を設定する Square の実装は、高さも自動的に設定してオブジェクトが正方形を保つようにする。しかし、システムのどこかに Rectangle オブジェクトに対し多様的に働くコードがあって、幅の変更によって高さも自動的に変更されるとうまくいかない部分があるかもしれない。

とある。（マークは引用者による。）

したがって、インスタンス化可能なクラスを拡張して、同値関係にとって意味のあるsignificantフィールドを追加することはできない。『Effective Java 第3版』p. 46 にも次のやうにある（マークは引用者による。）:

インスタンス化可能なクラスを拡張して値要素を追加するための、満足できる方法はありませんが、素晴らしい回避策があります。項目18「継承よりもコンポジションを選ぶ」の助言に従うことです。ColorPoint に Point を拡張させる代わりに、ColorPoint に private の Point フィールドを持たせて、そのカラーポイントと同じ位置のポイントを返す public のビュー (view) メソッド（項目6）を持たせてください。

よって、部分型が上位型にない意味のあるsignificantフィールドを持つやうな場合、それらの型の間の同値関係は検査できない。そこで、このやうなフィールドを取り除いてみると、部分型の値の集合は、上位型の値の集合の部分集合となる^[11]。

こゝで、集合 𝑋 と 𝑋 の真部分集合 𝑌 上の二項関係 𝑅 が対称律を満たす、すなはち、𝑋 の任意の元 𝑎 と 𝑌 の任意の元 𝑏 について、𝑎 𝑅 𝑏 なら 𝑏 𝑅 𝑎 だとする。このとき、𝑎 ∉ 𝑌 なら 𝑏 𝑅 𝑎 は定義されない。よって、𝑎 ∉ 𝑌 なら 𝑎 𝑅 𝑏 ではないから、𝑎 も 𝑌 の元でなければならない。∎

オブジェクト指向プログラミングに限って言へば、次のやうな論理でも、同じやうな結論を導くことができる。

インスタンス化可能なクラス 𝐴、𝐴 の派生クラス 𝐵、および 𝐵 の派生クラス 𝐶 がある。クラス 𝐴、𝐵、𝐶 にはそれぞれ、引数を1つ取って、レシーバーと実引数が同値なら真を返し、さもなければ偽を返すメソッド 𝑒𝑞 がある。𝑒𝑞 は、引数の型を指定するか、あるいは lang.java.Object の equals と同様に、任意の型の項を引数に取り、実行時に実引数の型を検査する。型を検査しないと、偶然同じフィールドを持つ2種類の値（例へば、半径を持つ円と球。）が同値と見做されてしまふことがある。𝐴 のインスタンスと 𝐵 のインスタンスが同値たりえるなら、𝐵 の 𝑒𝑞 は、実引数が 𝐴 のインスタンスであるかどうかを検査することになる。𝐵 と 𝐶 についても同じ。よって、𝑎、𝑏、𝑐 をそれぞれ 𝐴、𝐵、𝐶 のインスタンスとすると、推移律より、𝑐 𝑒𝑞 𝑏 かつ 𝑏 𝑒𝑞 𝑎 なら 𝑐 𝑒𝑞 𝑎 でなければならない。しかし、𝐶 は 𝐴 を知らないので、𝐶 の 𝑒𝑞 は実引数が 𝐴 のインスタンスかどうかを検査できない。

𝑒𝑞 の実装に基底クラスの 𝑒𝑞 を使へば、推移律の問題は解決する。しかし、基底クラスの 𝑒𝑞 は、実引数がレシーバーと同値たりえないときは単に偽を返すため、派生クラスの 𝑒𝑞 で追加の検査を行ふことはできない。これは 𝑒𝑞 をオーバーライドしなかった場合と同様である。