Äquivalenzrelation

In der Mathematik wird das Wort äquivalent für verschiedene Abschwächungen der Forderung der Gleichheit benutzt. Oft werden Objekte äquivalent genannt, wenn sie nur gewisse Eigenschaften gemein haben.

Alle diese Begriffe haben die folgenden drei Eigenschaften:

• Reflexivität: $a\sim a$

Jedes Objekt ist zu sich selbst äquivalent

• Symmetrie: $a\sim b\quad \iff \quad b\sim a$

Wenn $a$ zu $b$ äquivalent ist, dann ist auch $b$ äquivalent zu $a$ (und umgekehrt).

• Transitivität: $a\sim b\ \mathrm {und} \ b\sim c\quad \Longrightarrow \quad a\sim c$

Wenn $a$ zu $b$ äquivalent und $b$ zu $c$ äquivalent ist, dann ist $a$ äquivalent zu $c$.

Handelt es sich bei den Objekten $a,b,c,\ldots$ um Elemente einer festen Menge $M$, so spricht man von einer Äquivalenzrelation auf $M$. Eine Äquivalenzrelation ist also eine reflexive, symmetrische und transitive Relation.

Im Zusammenhang mit Äquivalenzbegriffen gibt es drei verschiedene Sichtweisen:

• einzelne Objekte: Sind zwei Objekte äquivalent oder nicht?
• einzelne Äquivalenzklassen: Wie sieht die Gesamtheit der Objekte aus, die äquivalent zu einem vorgegebenen sind?
• die Menge der Äquivalenzklassen: Wie sieht die Gesamtheit aller Objekte aus, wenn man äquivalente Objekte als gleich ansieht?

Formale Definition einer Äquivalenzrelation

Eine Äquivalenzrelation auf einer Menge M ist eine Teilmenge $R\subseteq M\times M$, welche folgende Bedingungen erfüllt:

• Reflexivität: Für alle $a\in M$ ist $(a,a)\in R$.
• Symmetrie: Für alle $a,b\in M$, für die $(a,b)\in R$ gilt, ist auch $(b,a)\in R$.
• Transitivität: Sind $a,b,c\in M$ derart, dass $(a,b)\in R$ und $(b,c)\in R$ gilt, so ist auch $(a,c)\in R$.

Üblicherweise schreibt man

$a\sim _{R}b$ oder einfach $a\sim b$ statt $(a,b)\in R,$

und dann nehmen diese Forderung genau die in der Einleitung genannte Form an.

Äquivalenzklassen

Ist $R$ eine Äquivalenzrelation auf einer Menge $M$, so nennt man für ein Element $a\in M$ die Teilmenge

$[a]_{R}=\{x\in M\mid x\sim _{R}a\}\subseteq M$

die $R$-Äquivalenzklasse von $a$. Ist aus dem Kontext klar, dass Äquivalenzklassen bezüglich $R$ gebildet werden, lässt man den Zusatz "$R$-" weg. Andere Schreibweisen sind

$[a],\quad [a]_{\sim },\quad {\bar {a}},\quad a/R,\quad a/{\sim _{R}}.$

Elemente einer Äquivalenzklasse werden ihre Vertreter oder Repräsentanten genannt.

Jedes Element von $M$ ist in genau einer Äquivalenzklasse enthalten. Die Äquivalenzklassen zu zwei Elementen sind entweder gleich oder disjunkt, ersteres genau dann, wenn die Elemente äquivalent sind:

$[a]=[b]\quad \iff \quad a\sim b\quad \iff \quad a\in [b]\quad \iff \quad b\in [a].$

Die Äquivalenzklassen bilden eine Partition von $M$.

Die Menge der Äquivalenzklassen

Die Menge der Äquivalenzklassen ist

$M/{\sim }:=\{[a]\mid a\in M\}.$

Die Kardinalität $\left|M/{\sim }\right|$ wird manchmal auch als der Index der Äquivalenzrelation $R$ bezeichnet.

Die Menge der Äquivalenzklassen ist diejenige Menge, die entsteht, wenn man äquivalente Elemente "gleich macht". Siehe auch Identifizierungsabstraktion.

Es gibt eine kanonische surjektive Abbildung

$M\to M/{\sim },\quad m\mapsto [m].$

Beispiele

• Schulklassen: die zugrundeliegende Menge M ist die Menge aller Schüler auf einer Schule; zwei Schüler seien äquivalent, wenn sie in dieselbe Klasse gehen.

• Äquivalenzklasse eines Schülers ist seine Klasse.
• Die Menge der Äquivalenzklassen ist die Menge der Klassen.

• Gleichheit: auf einer beliebigen Menge $M$ seien zwei Elemente äquivalent, wenn sie gleich sind:

$m\sim n\quad :\Longleftrightarrow \quad m=n$

• Äquivalenzklasse eines Elementes $m$ ist die einelementige Menge $\{m\}$.
• Die Menge der Äquivalenzklassen ist die Menge der einelementigen Teilmengen von $M$; die Abbildung $M\to M/{\sim }$ ist eine Bijektion.

• Kongruenz in der Zahlentheorie: Die zugrundeliegende Menge ist die Menge Z der ganzen Zahlen, zwei Zahlen sind äquivalent, wenn sie denselben Rest bei Division durch 5 haben. Eine gleichwertige Formulierung ist: wenn ihre Differenz durch 5 teilbar ist.

• Äquivalenzklasse einer ganzen Zahl $k$ ist die so genannte Restklasse

${\bar {k}}=k+5\mathbb {Z} =\{k+5z\mid z\in \mathbb {Z} \}=\{\ldots ,k-10,k-5,k,k+5,k+10,\ldots \}.$

• Die Menge der Äquivalenzklassen ist der Restklassenring

$\mathbb {Z} /5\mathbb {Z} =\{{\bar {0}},{\bar {1}},{\bar {2}},{\bar {3}},{\bar {4}}\}.$

• Brüche: Es sei $M:=\{(z,n)\in \mathbb {Z} ^{2}\mid n\not =0\}$ die Menge der Paare ganzer Zahlen, deren zweiter Eintrag von Null verschieden ist. Zwei Paare $(z_{1},n_{1})$ und $(z_{2},n_{2})$ sollen äquivalent heißen, wenn gilt:

${\frac {z_{1}}{n_{1}}}={\frac {z_{2}}{n_{2}}}.$

• Die Äquivalenzklasse eines Paares $(z,n)$ besteht aus allen Paaren (Zähler, Nenner) für Bruchdarstellungen der rationalen Zahl ${\frac {z}{n}}$.
• Die Menge der Äquivalenzklassen wird durch

$M/{\sim }\to \mathbb {Q} ,\quad [(z,n)]\mapsto {\frac {z}{n}}$

bijektiv auf die Menge der rationalen Zahlen abgebildet. Ein wichtiger Punkt ist hier die Wohldefiniertheit: wenn $[(z_{1},n_{1})]=[(z_{2},n_{2})]$ gilt, dann ist das Bild nach der obigen Vorschrift

einerseits ${\frac {z_{1}}{n_{1}}}$, andererseits ${\frac {z_{2}}{n_{2}}}$.

Die Äquivalenzrelation war aber gerade so gewählt, dass diese beiden rationalen Zahlen gleich sind.

Universelle Eigenschaft

Ist $M$ eine Menge, $R$ eine Äquivalenzrelation auf $M$ und $N$ eine weitere Menge, so vermittelt die Abbildung $M\to M/{\sim _{R}}$ eine Bijektion zwischen folgenden Mengen:

• Abbildungen $M\to N$, bei denen $R$-äquivalente Elemente dasselbe Bild haben

und

• Abbildungen $M/{\sim _{R}}\to N.$

Weitere Äquivalenzbegriffe

Besondere Bedeutung kommt Äquivalenzrelationen zu, die mit einer algebraischen Struktur auf einer Menge kompatibel sind; das Hauptinteresse gilt hier der Menge der Äquivalenzklassen, die die algebraische Struktur "erbt":

• Faktorraum (für Vektorräume)
• Faktorgruppe (für Gruppen)
• Faktorring (für Ringe)
• Kongruenzrelation (für allgemeine algebraische Strukturen)

Viele Äquivalenzbegriffe entstehen aus der Forderung, dass ein Paar von Abbildungen mit gewissen Eigenschaften zwischen zwei Objekten existiert, die "mehr oder weniger" invers zueinander sind:

• Isomorphie
• Homöomorphie
• Homotopieäquivalenz
• natürliche Äquivalenz
• Äquivalenz von Kategorien