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

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°90° dasselbe wie bei einer Drehung von 450°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:

xx und yy besitzen dieselbe ISB-Nummer.

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

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 eineindeutig 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 mit Hilfe 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 xx und yy äquivalent zueinander bezüglich einer Äquivalenzrelation RR sind, schreibt man oft xRyx\sim_R y oder einfach xyx\sim y anstatt der sonst üblichen Schreibweise xRyx\,R\,y beziehungsweise (x,y)R(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][x] bezeichnet:

Definition: (Äquivalenzklasse)

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

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

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

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

Es gilt auch die Umkehrung des obigen Satzes:

Satz: Aus [x]=[y][x]=[y] folgt xyx\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:

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 MM ist eine Menge PP von Teilmengen von MM, so dass

  • die Vereinigung aller Mengen von PP die Menge MM ergibt: APA=M\bigcup_{A\in P} A = M

  • alle Mengen von PP paarweise disjunkt sind: A,BP:ABAB=\forall A, B\in P: A\ne B \Rightarrow A \cap B = \emptyset

  • alle Mengen von PP nicht leer sind: AP:A\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/{M/{\sim}} bezeichnet und in bestimmten Kontexten der Mathematik ''Quotientenraum'' oder ''Faktorraum'' genannt. Die Zerlegung M/{M/{\sim}} der Grundmenge MM ist also:

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

**Satz: **(Äquivalenzrelationen induzieren eine Zerlegung)

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

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

Satz: (Jede Zerlegung induziert eine Äquivalenzrelation)

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

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?