Äquivalenzrelation/Äquivalenzklassen/Textabschnitt

Eine Äquivalenzrelation ${}R\subseteq M\times M$ auf einer Menge ${}M$ kann auch als Zerlegung (Partition) der Menge ${}M$ aufgefasst werden. Hierzu ist der Begriff der Äquivalenzklasse nützlich.

Definition

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation und ${}x\in M$. Dann ist

${}[x]:={\left\{y\in M\mid (x,y)\in R\right\}}\,$

die Äquivalenzklasse von ${}x$ bezüglich ${}R$.

In Worten: ${}[x]$ ist die Teilmenge aller Elemente von ${}M$, die zu ${}x$ äquivalent sind. Jedes Element ${}y\in [x]$ heißt ein Repräsentant für die Äquivalenzklasse ${}[x]$.

Definition

Es sei ${}\sim$ eine Äquivalenzrelation auf einer Menge ${}M$. Eine Teilmenge ${}T\subseteq M$ heißt ein Repräsentantensystem für die Äquivalenzrelation, wenn es für jede Äquivalenzklasse genau ein Element in ${}T$ aus dieser Klasse gibt.

Drei Äquivalenzklassen für die durch die Parallelität gegebene Äquivalenzrelation.

Beispiel

Auf der Menge aller Geraden in der Ebene kann man die Parallelität als Äquivalenzrelation auffassen. Eine Gerade ist zu sich selbst parallel, die Relation ist offenbar symmetrisch und wenn ${}G_{1}$ zu ${}G_{2}$ parallel und ${}G_{2}$ zu ${}G_{3}$ parallel ist, so ist auch ${}G_{1}$ zu ${}G_{3}$ parallel. Die Äquivalenzklasse zu einer Geraden ${}G$ besteht aus allen zu ${}G$ parallelen Geraden, diese bilden eine parallele Geradenschar. Wir fixieren einen Punkt ${}M$ in der Ebene. Dann gibt es zu jeder Geraden ${}G$ eine dazu parallele Gerade ${}G'$, die durch den Punkt ${}M$ verläuft. Man kann also jede Äquivalenzklasse durch eine Gerade durch den Punkt ${}M$ repräsentieren, und zwar eindeutig, da parallele Geraden, die durch einen Punkt verlaufen, übereinstimmen müssen. Die Menge der Geraden durch ${}M$ bildet also ein Repräsentantensystem für die Äquivalenzrelation der Parallelität.

Unter der Äquivalenzrelation „erreichbar auf dem Landweg“ sind Inseln und Kontinente die Äquivalenzklassen.

Beispiel

Es sei eine Situation gegeben, wo gewisse Orte (oder Objekte) von gewissen anderen Orten aus erreichbar sind oder nicht. Die Erreichbarkeit kann dabei durch die Wahl eines Verkehrsmittels oder durch eine abstraktere (Bewegungs)-Vorschrift festgelegt sein. Solche Erreichbarkeitsrelationen liefern häufig eine Äquivalenzrelation. Dass ein Ort von sich selbst aus erreichbar ist, sichert die Reflexivität. Die Symmetrie der Erreichbarkeit besagt, dass wenn man von ${}A$ nach ${}B$ kommen kann, dass man dann auch von ${}B$ nach ${}A$ kommen kann. Das ist nicht für jede Erreichbarkeit selbstverständlich, für die meisten aber schon. Die Transitivität gilt immer dann, wenn man die Bewegungsvorgänge hintereinander ausführen kann, also zuerst von ${}A$ nach ${}B$ und dann von ${}B$ nach ${}C$.

Wenn erreichbar beispielsweise dadurch gegeben ist, dass man auf dem Landweg von einem Ort zu einem anderen kommen kann, so sind zwei Ortspunkte genau dann äquivalent, wenn sie auf der gleichen Insel (oder dem gleichen Kontinent) liegen. Inseln und Kontinente sind dann die Äquivalenzklassen. In der Topologie spielt der Begriff des Wegzusammenhangs eine wichtige Rolle: Zwei Punkte sind wegzusammenhängend, wenn man sie durch einen stetigen Weg verbinden kann. Oder: Auf den ganzen Zahlen lebe eine Kolonie von Flöhen, und jeder Flohsprung geht fünf Einheiten weit (in beide Richtungen). Wie viele Flohpopulationen gibt es, welche Flöhe können sich begegnen?

Beispiel

Beim Schach darf ein Läufer diagonal in jede Richtung beliebig weit ziehen. Zwei Felder heißen läuferäquivalent, wenn man von dem einen Feld mit endlich vielen Läuferzügen zu dem anderen Feld gelangen kann. Das ist eine Äquivalenzrelation. Da sich bei einem Diagonalzug die Farbe des Feldes nicht ändert, bleibt ein Läufer, der auf einem weißen Feld steht, stets auf einem weißen Feld. Zugleich kann ein Läufer, der auf einem weißen Feld steht, jedes weiße Feld (grundsätzlich, ohne Beachtung von anderen Figuren in einer Stellung) erreichen. Deshalb gibt es zwei Äquivalenzklassen: die weißen Felder und die schwarzen Felder, und entsprechend spricht man von weißfeldrigen Läufern und schwarzfeldrigen Läufern (das ist nicht die Farbe der Figur).

Beispiel

Visualisierung des Beispiels

Wir betrachten die Produktmenge ${}M=\mathbb {N} \times \mathbb {N}$, die wir uns als ein Punktgitter vorstellen. Wir fixieren die Sprünge (man denke an Springmäuse, die alle diese Sprünge ausführen können)

$\pm (2,0)\,\,{\text{ und }}\,\,\pm (3,3),$

und sagen, dass zwei Punkte ${}P=(a,b),\,Q=(c,d)\in M$ äquivalent sind, wenn man ausgehend von ${}P$ den Punkt ${}Q$ mit einer Folge von solchen Sprüngen erreichen kann. Dies ist eine Äquivalenzrelation (dafür ist entscheidend, dass bei den Sprüngen auch der entgegengesetzte Sprung dazu gehört). Typische Fragestellungen sind: Wie kann man äquivalente Felder charakterisieren, wie entscheiden, ob zwei Felder äquivalent sind oder nicht? Wie viele Äquivalenzklassen gibt es überhaupt, gibt es für sie ein schönes Repräsentantensystem?