同値類
同値類(どうちるい,英: equivalence class)
以下のような擬似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) $ \forall y .z \in C(x), y \sim z
(ii) $ y \in C(x) \Rightarrow C(x) = C(y)
(iii) $ C(x) \cap C(y) \neq \varnothing
参考
https://youtu.be/FlG0UZZnTTI?si=pjpMoCw2KAzb7Vxt
関連