Äquivalenzrelation/Äquivalenzklassen/Einführung/Textabschnitt

Eine Äquivalenzrelation ${}R\subseteq M\times M$ auf einer Menge ${}M$ kann auch als Zerlegung 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, also einfach die Faser zu ${}x$. Jede Teilmenge ${}S\subseteq M$, die die Gestalt ${}S=[x]$ für ein ${}x\in M$ besitzt, heißt Äquivalenzklasse. Jedes Element ${}y\in [x]$ heißt ein Repräsentant für die Äquivalenzklasse ${}[x]$. Insbesondere ist ${}x$ selbst ein Repräsentant für die Klasse ${}[x]$, doch ist dies keineswegs der einzige oder der „beste“ Repräsentant.

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.

Beispiel

Wir knüpfen an Beispiel an. Die gesamte Wäsche haben wir gemäß der Waschverträglichkeit sortiert und es haben sich dabei verschiedene Haufen ergeben, wobei zwei Kleidungsstücke genau dann auf dem gleichen Haufen gelandet sind, wenn sie zueinander waschverträglich sind. Die Haufen sind also die Äquivalenzklassen. Die Äquivalenzklasse zu einem bestimmten Kleidungsstück ${}x$ besteht aus allen zu ${}x$ waschverträglichen Kleidungsstücken, also aus allen Kleidungsstücken, die zusammen mit ${}x$ auf dem gleichen Haufen liegen. Wenn wir aus jedem Haufen ein bestimmtes Kleidungsstück auswählen, so haben wir ein Repräsentantensystem für die Waschverträglichkeit.

Bemerkung  

Wir betrachten in einigen Beispielen von Äquivalenzrelationen die Äquivalenzklassen. Wenn die Äquivalenzrelation die Gleichheit ist, so sind alle Äquivalenzklassen einelementig und die Äquivalenzklasse zu ${}x$ ist einfach die einelementige Menge ${}[x]=\{x\}$. Im anderen Extremfall, wenn alle Elemente zueinander äquivalent sind, so gibt es nur eine einzige Äquivalenzklasse, nämlich die Gesamtmenge ${}M$.

Bei der Äquivalenzrelation auf der Menge der Bruchterme, die durch die Wertegleichheit in ${}\mathbb {Q}$ gegeben ist, besteht die Äquivalenzklasse zu ${}{\frac {a}{b}}$ aus allen anderen Bruchdarstellungen dieser Zahl, also beispielsweise aus ${}{\frac {a}{b}},{\frac {2a}{2b}},{\frac {3a}{3b}},\ldots$. Ein Repräsentantensystem liegt in der Menge aller gekürzten Brüche vor.

Wenn eine Äquivalenzrelation auf ${}M$ durch eine Abbildung ${}f\colon M\rightarrow N$ im Sinne von Fakt festgelegt ist, so sind die Äquivalenzklassen die nichtleeren Fasern der Abbildung. Die Äquivalenzklasse zu ${}x\in M$ besteht aus dem Urbild von ${}f(x)$, ist also gleich

${}f^{-1}(f(x))={\left\{y\in M\mid f(y)=f(x)\right\}}\,.$

Um ein Repräsentantensystem zu erhalten, muss man aus jeder Faser ein Element auswählen. Im Allgemeinen gibt es hier kein besonders einfaches Repräsentantensystem.

In Beispiel besteht die Äquivalenzklasse zu ${}x\in K$ aus ${}\{x,-x\}$ (wobei diese beiden Zahlen nicht unbedingt, wie etwa bei ${}x=0$, verschieden sein müssen). Wenn ${}K$ angeordnet ist, so kann man die nichtnegativen Elemente ${}K_{\geq 0}$ als ein übersichtliches Repräsentantensystem heranziehen.

In Beispiel bei der durch die Gaußklammer gegebenen Äquivalenzrelation besteht die Äquivalenzklasse zu ${}x$ aus dem halboffenen Intervall

${}[\left\lfloor x\right\rfloor ,\left\lfloor x\right\rfloor +1[={\left\{y\in K\mid y\geq x{\text{ und }}y<x+1\right\}}\,.$

Ein besonders einfaches Repräsentantensystem ist durch die Menge der ganzen Zahlen ${}\mathbb {Z}$ gegeben.

Bei der durch das Betrachten des Bruchanteils (der Nachkommazahl) gegebenen Äquivalenzrelation auf ${}K$ besteht die Äquivalenzklasse zu ${}x$ aus der Menge ${}x+\mathbb {Z}$, also aus allen Zahlen, die man von ${}x$ aus mit einem ganzzahligen Schritt erreichen kann. Die Menge der Zahlen zwischen ${}0$ und ${}1$ einschließlich der ${}0$ und ausschließlich der ${}1$, also der Zahlen aus dem halboffenen Intervall ${}[0,1[$, ist ein Repräsentantensystem.

In Beispiel, der Erreichbarkeitsrelation auf dem Landweg, besteht die Äquivalenzklasse zu ${}x$ aus der Insel bzw. dem Kontinent, auf der bzw. dem der Punkt ${}x$ liegt.

Beispiel

Es sei ${}d\in \mathbb {N}$ fixiert. Wir bestimmen auf ${}\mathbb {Z}$ die Äquivalenzklassen zur Äquivalenzrelation ${}\sim$, bei der zwei Zahlen ${}a,b\in \mathbb {Z}$ als äquivalent betrachtet werden, wenn ihre Differenz ${}a-b$ ein Vielfaches von ${}d$ ist. Zu jeder Zahl ${}a\in \mathbb {Z}$ kann man einfach die zugehörige Äquivalenzklasse finden, sie besteht aus allen Zahlen der Form

${}a+\mathbb {Z} d={\left\{a+nd\mid n\in \mathbb {Z} \right\}}\,.$

In jeder Äquivalenzklasse gibt es ein Element (einen Vertreter, einen Repräsentanten) zwischen ${}0$ und ${}d-1$, da ja insbesondere ${}a$ zu seinem Rest bei der Division durch ${}d$ äquivalent ist. Andererseits sind bei

${}0\leq r<s\leq d-1\,$

die Äquivalenzklassen zu ${}r$ und zu ${}s$ verschieden. Es ist nämlich

${}(r+\mathbb {Z} d)\cap (s+\mathbb {Z} d)=\emptyset \,,$

da aus

${}r+nd=s+md\,$

sofort

${}s-r=(n-m)d\,$

folgt, was wegen

${}0<s-r<d\,$

nicht sein kann.

Beispiel

In der Ebene ${}E$ sei ein bestimmter Punkt ${}M$ markiert. Wir betrachten die Äquivalenzrelation, bei der zwei Punkte ${}P$ und ${}Q$ als äquivalent gelten, wenn sie zu ${}M$ den gleichen Abstand besitzen. Dies wird durch

${}d(P,M)=d(Q,M)\,$

ausgedrückt. Dies ist eine Äquivalenzrelation, wie man direkt überprüfen kann und was auch aus Fakt folgt, da man ja die Situation mittels der Abbildung

$E\longrightarrow \mathbb {R} _{\geq 0},\,P\longmapsto d(P,M),$

interpretieren kann. Die Äquivalenzklasse zu einem Punkt ${}P$ besteht aus allen Punkten der Ebene, die in ihrem Abstand zu ${}M$ mit ${}d(P,M)$ übereinstimmen. Dies ist genau der Kreis mit Mittelpunkt ${}M$ durch den Punkt ${}P$. Die Äquivalenzklassen sind also die konzentrischen Kreise um den Mittelpunkt ${}M$, wobei man hier den Punkt ${}\{M\}$ als Kreis mit Radius ${}0$ mitzählen muss (man kann sich darüber streiten, ob das ein Kreis ist, jedenfalls ist diese einpunktige Menge hier eine Äquivalenzklasse).

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.

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