同値類 - pogi-log

同値類

同値類(どうちるい，英: equivalence class)

類は英語でclass

あるxが与えられたときに同値関係となる要素全体

同値類は反射律、対称律、推移律を満たすもの

以下のような擬似Pythonコードのイメージ？

code:memo

# 同値関係~の演算子が定義されていて、x ~ yが真になるものを集めるイメージ

def getEquivalenceClass(x, S):

map(lambda y: x ~ y, S)

定義

集合$ S における同値関係$ \sim がある

このとき、$ x \in S に対して、$ x と同値な元の全体

$ [x] = \bar{x} = \lbrace y \in S \hspace{1mm} \vert \hspace{1mm} x \sim y \rbrace \subset S

のことを$ x を含む(または$ x の)同値類(equivalence class)という。

このときの$ x は代表元(representative element)。

$ \bar{x} は$ S の部分集合

集合$ S を同値関係$ \sim で割っている？的な捉え方もあるため、

$ S/\sim = \{ \bar{x} | x \in S\}

という表記をして商集合(quotient)と言われるものも定義できる。$ S/\sim を集合$ S の関係$ 〜に関する商集合と読む。

定理

(i) $ y \sim z \quad (\forall y .z \in C(x))

(ii) $ y \in C(x) \Rightarrow C(x) = C(y)

(iii) $ C(x) \cap C(y) \neq \varnothing

同値類の構造を名前をつけて定義したものでSetoidというものがある

参考

https://youtu.be/FlG0UZZnTTI?si=pjpMoCw2KAzb7Vxt