Äquivalenzrelationen

Zunächst werden wir in einem einführenden Beispiel die vorkommenden Begriffe motivieren. Im zweiten Abschnitt werden wir dann die Äquivalenzrelation, Äquivalenzklasse und Zerlegung einer Menge definieren. Diese drei Begriffe werden wir im letzten Abschnitt untersuchen und nützliche Sätze beweisen.

Andere Eigenschaften von Relationen findest du in diesem Artikel.

Einführendes Beispiel

Oftmals verhalten sich verschiedene Objekte in bestimmten Aspekten gleich oder besitzen gleiche, beziehungsweise sehr ähnliche Eigenschaften.

Beispielsweise besitzen Exemplare von Büchern derselben ISB-Nummer denselben Inhalt und Autor.

Weiterhin ist das Ergebnis einer Drehung von $90°$ dasselbe wie bei einer Drehung von $450°$ .

In diesem Kapitel wirst du die mathematischen Werkzeuge kennen lernen, mit denen du solche Äquivalenzen zwischen Objekten einer Grundmenge sauber beschreiben kannst.

Eine Beziehung, die die Gleichwertigkeit zwischen Objekten unter bestimmten Aspekten ausdrückt, wird Äquivalenzrelation genannt.

Wir werden sehen, dass folgende Relation auf der Grundmenge aller bisher gedruckter Buchexemplare eine Äquivalenzrelation ist:

Betrache die nebenstehende Menge mit acht Buchexemplaren und eingezeichneter Äquivalenzrelation " $x$ und $y$ besitzen dieselbe ISB-Nummer“ als Pfeildiagramm.

$x$ und $y$ besitzen dieselbe ISB-Nummer.

Wir werden sehen, dass die Eigenschaften der Reflexivität, Symmetrie und Transitivität der obigen Relation genau diejenigen sind, die hinreichend und notwendig für eine Äquivalenzrelation sind.

Es gibt eine weitere Möglichkeit Äquivalenzrelationen zu beschreiben: Die Möglichkeit die Grundmenge in verschiedene disjunkte Teilmengen zu zerlegen.

Nehmen wir wieder das obige Beispiel mit den Büchern. Stell dir vor, wir fassen alle Exemplare in eine Menge zusammen, die dieselbe ISB-Nummer besitzen.

Es kommen also genau dann zwei Bücher x und y in dieselbe Menge, wenn sie dieselbe ISB-Nummer besitzen, wenn also x in Relation zu y steht. Eine so entstandene Teilmenge werden wir später Äquivalenzklasse nennen.

Das Ergebnis ist eine Zerlegung der Grundmenge aller gedruckter Buchexemplare in disjunkte Teilmengen. Jede dieser Teilmengen steht für ein konkretes Schriftwerk eines Autors. Denn jede ISB-Nummer bezeichnet eindeutig ein solches Schriftwerk und jede Teilmenge enthält genau diejenigen Exemplare, die dieselbe ISB-Nummer besitzen.

Man kann diese Teilmengen nun als neue Objekte betrachten. Dadurch erhältst du die Menge aller Schriftwerke. Jedes Schriftwerk ist dabei als Menge, nämlich der Menge aller Exemplare dieses Schriftwerks, modelliert. Durch eine Zerlegung einer Menge mithilfe einer Äquivalenzrelation können also neue Objekte modelliert werden (dies ist eine gängige Vorgehensweise in der Mathematik).

Definitionen

Äquivalenzrelation

Eine Äquivalenzrelation ist folgendermaßen definiert:

Definition: (Äquivalenzrelation) Eine Äquivalenzrelation ist eine homogene, binäre Relation auf einer Grundmenge, die folgende Eigenschaften besitzt:

reflexiv
symmetrisch
transitiv

Zwei Elemente, die bezüglich einer Äquivalenzrelation in Relation stehen, heißen ''äquivalent''. Wenn zwei Elemente $x$ und $y$ äquivalent zueinander bezüglich einer Äquivalenzrelation $R$ sind, schreibt man oft $x\sim_R y$ oder einfach $x\sim y$ anstatt der sonst üblichen Schreibweise $x\,R\,y$ beziehungsweise $(x,y)\in R$ .

Äquivalenzklasse

Im obigen Beispiel haben wir durch die Äquivalenzrelation die Grundmenge in disjunkte Teilmengen zerlegt, indem wir alle Buchexemplare in einer Teilmenge zusammengefasst haben, die in Relation steht. Eine solche Teilmenge wird ''Äquivalenzklasse'' genannt und mit $[x]$ bezeichnet:

Definition: (Äquivalenzklasse)

Eine Äquivalenzklasse $[x]$ ist die Menge aller Elemente der Grundmenge $M$ , die zum Element $x$ äquivalent sind:

\displaystyle [x] := \{ y\in M\,|\, y\sim x\}

Wenn du die Relation explizit angeben musst, kannst du auch $[x]_R$ schreiben. Es ist dann

\displaystyle [x] := \{ y\in M\,|\, y\sim x\}

Das Element $x$ in der Schreibweise $[x]$ nennt man ''Repräsentant'' oder ''Vertreter''. Ist unsere obige Definition für Äquivalenzklassen korrekt im Sinne, dass $[x]=[y]$ wenn $x$ und $y$ äquivalent zueinander sind? Dies beantwortet der folgende Satz:

Satz: Ist $x\sim y$ , dann ist $[x]=[y]$ .

Es gilt auch die Umkehrung des obigen Satzes:

Satz: Aus $[x]=[y]$ folgt $x\sim y$ .

Zusammen ergeben die vorherigen beiden Sätze folgenden wichtigen Satz:

Satz: (Zusammenhang zwischen Äquivalenz der Repräsentanten und der Äquivalenzklassen)

Für Äquivalenzklassen und deren Vertreter gilt folgender Zusammenhang:

\displaystyle [x] := \{ y\in M\,|\, y\sim x\}

Zerlegung einer Menge

Oft haben wir bereits von der Zerlegung einer Menge gesprochen (welche in der Mengenlehre auch Partition genannt wird). Hier die Definition der Zerlegung einer Menge (im nächsten Abschnitt werden wir den Zusammenhang zwischen Äquivalenzrelation und der durch ihr definierten Zerlegung untersuchen):

Definition:(Zerlegung einer Menge) Eine Zerlegung einer Menge $M$ ist eine Menge $P$ von Teilmengen von $M$ , so dass

die Vereinigung aller Mengen von $P$ die Menge $M$ ergibt: $\bigcup_{A\in P} A = M$

alle Mengen von $P$ paarweise disjunkt sind: $\forall A, B\in P: A\ne B \Rightarrow A \cap B = \emptyset$
alle Mengen von $P$ nicht leer sind: $\forall A \in P: A \ne \emptyset$

Zusammenhang zwischen Äquivalenzrelationen und der Zerlegung einer Menge

Wollen wir nun den Zusammenhang zwischen Äquivalenzrelationen und der Zerlegung einer Menge untersuchen.

Im einführenden Beispiel haben wir gesehen, dass eine Äquivalenzrelation eine Zerlegung der Grundmenge definiert, indem man alle äquivalenten Elemente in einer Teilmenge, der Äquivalenzklasse, zusammenfasst. Eine solche Zerlegung einer Menge durch eine Äquivalenzrelation wird mit ${M/{\sim}}$ bezeichnet und in bestimmten Kontexten der Mathematik ''Quotientenraum'' oder ''Faktorraum'' genannt. Die Zerlegung ${M/{\sim}}$ der Grundmenge $M$ ist also:

\displaystyle [x] := \{ y\in M\,|\, y\sim x\}

Doch ist dies wirklich eine Zerlegung im Sinne der obigen Definition? Beweisen wir es:

Satz: (Äquivalenzrelationen induzieren eine Zerlegung)

Sei $R$ eine Äquivalenzrelation auf der Grundmenge $M$ . Dann ist die Menge aller Äquivalenzklassen ${M/{\sim_R}}:= \{ [x]_R\,|\,x\in M\}$ eine Zerlegung der Grundmenge.

Doch wie sieht es umgekehrt aus? Kannst du aus einer vorgegebenen Partition $P$ einer Menge $M$ so eine Äquivalenzrelation definieren, dass ${M/{\sim}}=P$ ist?

Satz: (Jede Zerlegung induziert eine Äquivalenzrelation)

Sei $M$ eine Menge und $P$ eine Zerlegung dieser Menge. Dann gibt es genau eine Äquivalenzrelation $\sim$ , die diese Zerlegung induziert, für die also $M/{\sim}=P$ ist. Diese Äquivalenzrelation ist definiert durch:

\displaystyle [x] := \{ y\in M\,|\, y\sim x\}

Dieses Kapitel basiert auf dem Artikel "Äquivalenzrelation" der freien Lehrbuchreihe „Mathe für Nicht-Freaks“. Die Autoren des Artikels kann der Versionsgeschichte entnommen werden. Dieser Kapitel steht wie das Original unter einer CC-BY-SA 3.0 Lizenz.

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?