Menge der Äquivalenzklassen als Partition
1. Satz
Sei \(X\) eine Menge, \(\sim\) eine Äquivalenzrelation. Dann ist die Menge aller verschiedenen Äquivalenzklassen ist eine Partition von \(X\)
Dabei werden Äquivalenzklassen \([x],[y]\), welche die gleichen Mengen sind, nicht mehrfach gezählt.
2. Beweis
2.1. alle elemente vorhanden
Man bemerke, dass jedes Element \(x \in X\) in mind. einer (genauer sogar genau einer) Äquivalenzklasse liegt, nämlich \([x]\)
2.2. paarweise disjunkt
Sei eine Äquivalenzklasse definiert als
\begin{align*} [x] \coloneqq \{y \in X \vert y \sim x\} \end{align*}und seien \([x],[y]\) Äquivalenzklassen.
Es bleibt zu zeigen, dass entweder \([x] = [y]\) gilt oder \([x] \cap [y] = \emptyset\). Angenommen \([x] \cap [y] \neq \emptyset\), so existiert ein \(z \in [x] \cap [y]\). Dann folgt aus \(z \in [x], z \in [y]\) auch \(z \sim x, z \sim y\) bzw. wegen Symmetrie \(y \sim z\) und wegen Transitivität \(y \sim x\).
Wir zeigen im folgenden \([y] \subseteq [x]\), also sei \(w \in [y]\) beliebig. Dann folgt aus \(w \sim y\) und \(y \sim x\) auch \(w \sim x\) (Transitivität) bzw. \([w] \in [x]\). Somit folgt \([y] \subseteq [x]\)
Die andere Richtung \([x] \subseteq [y]\) lässt sich analog zeigen (nachdem man durch Symmetrie folgert, dass \(x \sim y\) gilt)