Äquivalenzrelation

In der Mathematik möchte man in vielen Zusammenhängen Objekte, die sich in gewissen Aspekten ähneln, als gleichwertig ansehen. Eine Formalisierung der Mindestanforderungen an einen solchen Gleichwertigkeitsbegriff ist der Begriff der Äquivalenzrelation.

Beispielsweise ist jeder Begriff, der als die Gleichheit gewisser Eigenschaften definiert werden kann, eine Äquivalenzrelation:

die Gleichmächtigkeit endlicher Mengen: zwei endliche Mengen heißen gleichmächtig, wenn sie die selbe Anzahl von Elementen haben;
die Kongruenz in der Geometrie: zwei Dreiecke sind kongruent, wenn sie dieselben Seitenlängen haben;
die Ähnlichkeit in der Geometrie: zwei Dreiecke sind ähnlich, wenn sie dieselben Innenwinkel haben;
die Kongruenz in der elementaren Zahlentheorie: zwei ganze Zahlen heißen kongruent modulo 5, wenn sie bei ganzzahliger Division durch 5 denselben Rest lassen;
die Gleichheit selbst.

Oft entstehen derartige Begriffe auch aus der Existenz von Abbildungen oder anderen Verbindungen mit gewissen Eigenschaften:

zwei endliche Mengen sind gleichmächtig, wenn es eine bijektive Abbildung zwischen ihnen gibt;
zwei Dreiecke sind kongruent, wenn sie durch eine Kongruenzabbildung auseinander hervorgehen;
zwei Dreiecke sind ähnlich, wenn sie durch eine Ähnlichkeitsabbildung auseinander hervorgehen;
zwei ganze Zahlen sind kongruent modulo 5, wenn sie durch Addition eines ganzzahligen Vielfachen von 5 auseinander hervorgehen.

Das Wort "äquivalent" stehe im folgenden für eine dieser Beziehungen zwischen zwei Objekten; dass zwei Objekte aa und bb äquivalent sind, sei durch

symbolisiert.

Alle diese Begriffe haben die folgenden drei Eigenschaften:

Reflexivität:

Jedes Objekt ist zu sich selbst äquivalent.

Symmetrie:

Wenn aa zu bb äquivalent ist, dann ist auch bb äquivalent zu aa (und umgekehrt).

Transitivität:

Wenn aa zu bb äquivalent und bb zu cc äquivalent ist, dann ist aa äquivalent zu cc.

Jede Beziehung zwischen Objekten, die diese Eigenschaften hat, heißt eine Äquivalenzrelation.

Die Äquivalenzklasse eines Objektes aa ist die Klasse der Objekte, die äquivalent zu aa sind.

Im Zusammenhang mit Äquivalenzrelationen 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?

Inhaltsverzeichnis

1 anschauliches Beispiel
2 Formale Definition einer Äquivalenzrelation
3 Äquivalenzklassen
4 Die Menge der Äquivalenzklassen
5 Beispiele
6 Universelle Eigenschaft
7 Weitere Äquivalenzbegriffe

anschauliches Beispiel

Ein Beispiel aus der Landwirtschaft soll die eingeführten Begriffe vorweg verdeutlichen. Betrachten wir die Menge aller Nutztiere in einem landwirtschaftlichen Betrieb. Wir definieren nun eine Relation: Wir sagen, zwei Tieren stehen in Relation zueinander, wenn sie von der selben Art sind. Die Kuh Erna zum Beispiel steht mit dem Ochsen Bruno in Relation, aber nicht mit dem Huhn Betti. Diese Relation ist eine Äquivalenzrelation: Jedes Tier ist von derselben Art wie es selbst (= "reflexiv"). Ist ein Tier von derselben Art wie das andere, dann ist das andere auch von derselben Art wie das eine (= "symmetrisch"). Wenn Erna und Lisa von derselben Art sind und Lisa und Bruno von derselben Art, dann sind Erna und Bruno von derselben Art (z.B. Rinder; = "transitiv"). Eine Äquivalenzklasse besteht hier also aus den Tieren einer Art. Zum Beispiel bilden Hühner eine Äquivalenzklasse und die Rinder eine andere Äquivalenzklasse.

Formale Definition einer Äquivalenzrelation

Eine Äquivalenzrelation auf einer Menge M ist eine Teilmenge , welche folgende Bedingungen erfüllt:

Reflexivität: Für alle ist .
Symmetrie: Für alle , für die gilt, ist auch .
Transitivität: Sind derart, dass und gilt, so ist auch .

Üblicherweise schreibt man

oder einfach

statt

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

Äquivalenzklassen

Ist RR eine Äquivalenzrelation auf einer Menge MM, so nennt man für ein Element

die Teilmenge

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

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

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

Die Äquivalenzklassen bilden eine Partition von MM.

Die Menge der Äquivalenzklassen

Die Menge der Äquivalenzklassen (manchmal auch Faktormenge genannt) ist

Die Kardinalität

wird manchmal auch als der Index der Äquivalenzrelation RR 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

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 MM seien zwei Elemente äquivalent, wenn sie gleich sind:

Äquivalenzklasse eines Elementes mm ist die einelementige Menge .
Die Menge der Äquivalenzklassen ist die Menge der einelementigen Teilmengen von MM; die Abbildung 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 kk ist die so genannte Restklasse

Die Menge der Äquivalenzklassen ist der Restklassenring

Brüche: Es sei die Menge der Paare ganzer Zahlen, deren zweiter Eintrag von Null verschieden ist. Zwei Paare und sollen äquivalent heißen, wenn gilt:

Die Äquivalenzklasse eines Paares besteht aus allen Paaren (Zähler, Nenner) für Bruchdarstellungen der rationalen Zahl .
Die Menge der Äquivalenzklassen wird durch

bijektiv auf die Menge der rationalen Zahlen abgebildet. Ein wichtiger Punkt ist hier die Wohldefiniertheit: wenn

gilt, dann ist das Bild nach der obigen Vorschrift

einerseits

, andererseits

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

Universelle Eigenschaft

Ist MM eine Menge, RR eine Äquivalenzrelation auf MM und NN eine weitere Menge, so vermittelt die Abbildung

eine Bijektion zwischen folgenden Mengen:

Abbildungen , bei denen RR-äquivalente Elemente dasselbe Bild haben

und

Abbildungen

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)

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

Weitere Beispiele für Äquivalenzrelationen:

Vervollständigung durch Äquivalenzklassen von Cauchyfolgen