同値類

集合上の同値関係を用いて集合を分割することが出来ます。ある性質を持つ元をまとめて考える事で、対象が調べやすくなります。

集合 \(S\) 上の同値関係 \(\sim\) に対して, 元 \(a\in S\) の同値類(equivalence class)を\[\{\ x\in S\ |\ x\sim a\ \}\]で定義する. \(a\) の同値類を \(\ \overline{a},\ [a],\ C(a)\ \) などと書くことが多い.
このとき \(a\) を同値類 \(\overline{a}\) の代表元(representative)という.

同値類の性質

集合 \(S\) 上の同値関係 \(\sim\) に対して, 元 \(x\in S\) の同値類を \(\overline{x}\) とするとき以下が成り立つ :

\(\ a\in \overline{a}\)
\(\ a\sim b\ \Longrightarrow\ \overline{a}=\overline{b}\)
\(\ \overline{a}\neq\overline{b}\ \Longrightarrow\ \overline{a}\cap\overline{b}=\emptyset\)

証明

は反射律 \(a\sim a\) から明らか.
\(x\in \overline{a}\) とすると \(x\sim a\) であるが, \(a\sim b\) でもあるので推移律から \(x\sim b\). よって \(x\in \overline{b}\). ゆえに \(\overline{a}\subset\overline{b}\). \(\overline{b}\subset\overline{a}\) も同様に示せるので \(\overline{a}=\overline{b}\).
\(\overline{a}\neq\overline{b}\) ならば \(a\sim b\) ではない. ここで \(c\in\overline{a}\cap\overline{b}\) が取れたとすると, \(c\sim a,\ \ c\sim b\) より, 対称律と推移律を使うと \(a\sim b\) となるがこれは矛盾. ゆえに \(\overline{a}\cap\overline{b}=\emptyset\)