Nachlesen

Ä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 binäre Relation $R \subseteq A \times A$ wird Äquivalenzrelation genannt, wenn sie 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.$

Äquivalenzklasse

Sei $R$ eine Äquivalenzrelation auf einer (nichtleeren) Menge $A$. Die Teilmenge

{[a]}_R := \Bigl\{ b \in A \bigm| (b,a) \in R \Bigr\}

aller zu $a$ äquivalenten Elemente wird R-Äquivalenzklasse von a genannt (oder vereinfacht: Äquivalenzklasse von $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$.

Faktormenge und Quotientenmenge

Die Faktormenge bzw. die Quotientenmenge einer Äquivalenzrelation $R$ auf der Menge $A$ ist die Menge aller Äquivalenzklassen:

A/R := \Bigl\{ {[a]}_R \bigm| a \in A \Bigr\}.

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:

(a,b) \in R \quad\Leftrightarrow\quad \exists B \in \mathcal{P}: a,b \in B.

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

\begin{align*} R &= \Bigl\{ (a,a),\ (a,b),\ (a,c),\ (b,a),\ (b,b),\ (b,c),\ (c,a) \\[0.5em] &\qquad (c,b),\ (c,c),\ (d,d),\ (e,e),\ (e,f),\ (f,e),\ (f,f)\Bigr\}. \end{align*}

Darstellung der Äquivalenzrelation R als gerichteter Graph — Darstellung der Äquivalenzrelation $R$ als gerichteter Graph

Bei der Relation $R$ handelt es sich um eine Äquivalenzrelation, da sie symmetrisch, reflexiv und transitiv ist. Sie besitzt die drei Äquivalenzklassen

\begin{align*} A_1 &= \bigl\{ a,b,c \bigr\} \\[0.5em] A_2 &= \bigl\{ d \bigr\} \\[0.5em] A_3 &= \bigl\{ e,f \bigr\}. \end{align*}

Hieraus ergibt sich die folgende Partition der Menge sowie der Index der Äquivalenzrelation $R$.

\begin{align*} \mathcal{P} = A/R &= \bigl\{ A_1, A_2, A_3 \bigr\} \\[0.5em] \left| A/R \right| &= 3 \end{align*}

Jetzt üben!

Nutze den individuell konfigurierbaren Aufgabengenerator, um unbegrenzt Aufgaben zum Thema Eigenschaften von Relationen überprüfen zu erzeugen und zu üben.

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:

(a,b) \sim (c,d) \Leftrightarrow a+d = c+b.

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:

(a,b) \sim (c,d) \Leftrightarrow ad = cb.

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:

a \equiv b \pmod{m} \Leftrightarrow m \mid (a-b).

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$.