Äquivalenzrelation
Bei einer Äquivalenzrelation handelt es sich um eine zweistellige Relation, die symmetrisch, reflexiv und transitiv ist. Sie teilt die zugrundeliegende Menge in disjunkte Teilmengen auf – die Äquivalenzklassen –, die jeweils aus den Elementen derselben Eigenschaft, also aus den äquivalenten Elementen, bestehen. Äquivalenzrelationen und -klassen spielen bei der Begriffsbildung in der Mathematik eine grundlegende Rolle.
Definition
Äquivalenz
Elemente einer Menge, die in einer bestimmten Eigenschaft übereinstimmen oder sich auf eine bestimmte Art gleichen, werden als gleichwertig bzw. als äquivalent angesehen.
Diese Äquivalenz hat die folgenden Eigenschaften:
- Ein Element ist stets äquivalent zu sich selbst.
- Ist ein Element \(a\) äquivalent zu einem Element \(b\), so ist umgekehrt auch \(b\) äquivalent zu \(a\).
- Sind Elemente \(a\) und \(b\) sowie \(b\) und \(c\) äquivalent, so sind auch \(a\) und \(c\) äquivalent.
Äquivalenzrelation
Sei \(A\) eine Menge. Eine Relation \(R \subseteq A \times A\) wird Äquivalenzrelation genannt, wenn \(R\) den folgenden Eigenschaften genügt:
- Die Relation \(R\) ist symmetrisch, d. h. es gilt: \[ \forall a,b \in A: (a,b) \in R \Rightarrow (b,a) \in R. \]
- Die Relation \(R\) ist reflexiv, d. h. es gilt: \[ \forall a \in A: (a,a) \in R. \]
- Die Relation \(R\) ist transitiv, d. h. es gilt: \[ \forall a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \in R. \]
Äquivalenzklassen
Ist \(R\) eine Äquivalenzrelation auf einer (nichtleeren) Menge \(A\), so nennt man die Teilmenge
aller zu \(a\) äquivalenten Elemente die \(\mathbf{R}\)-Äquivalenzklasse von \(\mathbf{a}\). Ist aus dem Kontext heraus klar, dass es sich um die Relation \(R\) handelt, wird anstelle von \({[a]}_R\) oft nur \({[a]}\) geschrieben. Eine andere Schreibweise ist \(a / R\).
Faktor- und Quotientenmenge
Die Faktor- bzw. Quotientenmenge einer Äquivalenzrelation \(R\) auf der Menge \(A\) ist die Menge aller Äquivalenzklassen:
Partition
Die Faktormenge \(A / R\) aller Äquivalenzklassen einer Äquivalenzrelation \(R\) auf der Menge \(A\) bildet eine eindeutig bestimmte Zerlegung (oder auch Partition) \(\mathcal{P}\) der Menge \(A\). Umgekehrt lässt sich zu jeder Partition \(\mathcal{P}\) der Menge \(A\) eine Äquivalenzrelation \(R\) definieren durch:
Die Mächtigkeit (bzw. Kardinalität) \(\left| A/R \right|\) der Faktormenge \(A/R\) wird als Index der Äquivalenzrelation \(R\) bezeichnet.
Beispiel
Gegeben sei eine Menge \(A = \bigl\{ a,b,c,d,e,f \bigr\}\) sowie eine auf dieser Menge definierte zweistellige Relation \(R \subseteq A \times A\) mit
Bei der Relation \(R\) handelt es sich um eine Äquivalenzrelation, da sie symmetrisch, reflexiv und transitiv ist. Sie besitzt die drei Äquivalenzklassen
Hieraus ergibt sich die folgende Partition der Menge sowie der Index der Äquivalenzrelation \(R\).
Beispiele in der Mathematik
Konstruktion der ganzen Zahlen
Hauptartikel: Ganze Zahlen
Auf der Menge \(Z=\mathbb{N}_0 \times \mathbb{N}_0\) kann die folgende Äquivalenzrelation \(\sim\) definiert werden:
Die Menge \(\mathbb{Z}\) der ganzen Zahlen kann nun formal als \(\mathbb{Z} = Z / \sim\) definiert werden, also als die Faktormenge (die Menge der Äquivalenzklassen) der Äquivalenzrelation \(\sim\).
Konstruktion der rationalen Zahlen
Hauptartikel: Rationale Zahlen
Auf der Menge \(Q=\mathbb{Z} \times \left(\mathbb{Z} \setminus \{0\} \right)\) kann die folgende Äquivalenzrelation \(\sim\) definiert werden:
Die Menge \(\mathbb{Q}\) der rationalen Zahlen kann nun formal als \(\mathbb{Q} = Q / \sim\) definiert werden, also als die Faktormenge (die Menge der Äquivalenzklassen) der Äquivalenzrelation \(\sim\).
Konstruktion der Restklassenringe
Hauptartikel: Restklassenring
Auf der Menge \(\mathbb{Z}\) kann für jede natürliche Zahl \(m \in \mathbb{N}\) mit \(m\geq 1\) die folgende Äquivalenzrelation \(\equiv\), die Kongruenzrelation, definiert werden:
Die Menge \(\mathbb{Z}_m\) (oder auch \(\mathbb{Z}/m\mathbb{Z}\)) der Restklassen modulo \(m\) kann nun formal als \(\mathbb{Z}_m = \mathbb{Z} / \equiv\) definiert werden, also als die Faktormenge (die Menge der Äquivalenzklassen) der Relation \(\equiv\).