# 同値関係 ## 定義 同値関係(equivalence relation)とは、反射的(reflexive)・対称的(symmetric)・推移的(transitive)な[[二項関係]]をいう。合同算術における「mod n で合同」という関係(`x ≡ y (mod n)`)は同値関係の代表例であり、等号(equality)そのものも同値関係である。任意の全域関数(total function)`f: A → B` に対し、`a ~f a' :⟺ f(a) = f(a')` という関係を定めると、これは等号の性質を継承して自動的に同値関係になる。逆に、任意の同値関係はある全域関数の「同じ像を持つ」関係として表現できる。集合 `A` 上の同値関係 `R` と要素 `a ∈ A` に対し、`a` の**同値類(equivalence class)** `[a]_R` は `R` によって `a` と関係づけられる要素全体の集合 `{x ∈ A | a R x}` として定義され、これは `R` による `a` の像 `R(a)` に等しい。同値関係の同値類は、台集合 `A` の**分割(partition)**——`A` の空でない部分集合(ブロック、block)への分割であって各要素がちょうど1つのブロックに属するもの——のブロックと一対一に対応する(定理9.10.4)。すなわち、同値関係と分割は同じ構造を異なる形式で述べたものである。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]]) ## 横断的知見 (この concept は本 ingest が初出のため、複数ソースの突き合わせによる横断的知見はまだない。合同算術・分割・分類問題を扱う他ソースが ingest された際にここへ追記する。特に第8章(数論)の合同算術は本章の同値関係の中心例として使われており、第8章の source ページとの突き合わせが見込まれる。) ## 未解決の問い - 同値関係と分割の対応(定理9.10.4)は、機械学習のクラスタリング(データ点を「同じクラスタに属する」という同値関係的な関係で分割する)とどこまで形式的に対応するか。本章では触れられていない。 - 「あらゆる同値関係はある全域関数から誘導できる」(§9.10)という主張の逆——分割から出発して自然に定まる商集合(quotient set)への写像——を本章は明示的には定義していない。商集合の概念は後続章で扱われるか確認する必要がある。 ## 関連 - 概念: [[二項関係]] / [[半順序]] / [[有向グラフ]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 9.