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

Drehung

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:

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

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

Bücher

Übungsaufgabe zu dieser Relation:

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.

Äquivalenzklasse Bücher

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

Verständnisfrage: Was musst du tun, wenn du entscheiden sollst, ob eine Relation eine Äquivalenzrelation ist oder nicht?

Um zu entscheiden, ob eine Relation eine Äquivalenzrelation ist, musst du folgende Fragen beantworten: Relation Ja/Nein

Aufgabe: Welche der folgenden Relationen ist eine Äquivalenzrelation?
Verständnisfrage: Wie viele lineare Äquivalenzrelationen auf einer Grundmenge %%M%% gibt es?

Ä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: $$[x] := \{ y\in M\,|\, y\sim x\}$$

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

$$[x]_R := \{ y\in M\,|\, y\sim_R 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]%%.

Beweis:

Sei %%x\sim y%%. Zu zeigen ist, dass %%[x]\subseteq [y]%% und %%[y]\subseteq [x]%% ist. Sei also %%a\in [x]%% beliebig. Es gilt damit %%a\sim x%%. Da außerdem %%x\sim y%% ist, folgt aus der Transitivität der Äquivalenzrelation, dass auch %%a\sim y%% ist. Dies bedeutet aber %%a\in [y]%%. Da %%a\in [x]%% beliebig war, ist %%[x]\subseteq[y]%%.

Dass auch %%[y]\subseteq [x]%% ist, kannst du analog beweisen.

Es gilt auch die Umkehrung des obigen Satzes:

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

Beweis:

Sei %%[x]=[y]%%. Damit ist %%[x]\subseteq [y]%%, also %%a\in [y]%% für alle %%a\in [x]%%. Nun ist %%x\in[x]%%, da %%x\sim x%% aufgrund der Reflexivität der Äquivalenzrelation. Daraus folgt, dass %%x\in [y]%% und somit nach Definition %%x\sim y%% ist.

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: $$[x] = [y] \Leftrightarrow x\sim y$$

Aufgabe zu Äquivalenzklassen

Beschreibe, wie die Äquivalenzklassen der folgenden Äquivalenzrelationen aussehen:

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:

$${M/{\sim}} := \{ [x]\,|\,x\in M \}$$

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.

Beweis: (Äquivalenzrelationen induzieren eine Zerlegung)

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?

Wie kann eine solche Äquivalenzrelation aussehen?

Damit die induzierte Menge der Äquivalenzrelation gleich der Partitionsmenge %%P%% sein kann, muss für alle %%x,y\in M%% gelten:

%%\big( x%% und %%y%% gehören derselben Partitionsmenge an %%\Rightarrow x\sim y\big)%%

Damit gibt es nur einen möglichen Kandidaten einer Äquivalenzrelation:

$$x\sim y :\Leftrightarrow \exists A\in P: x,y\in A$$

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: $$x\sim y :\Leftrightarrow \exists A\in P: x,y\in A$$

Beweis: (Jede Zerlegung induziert eine Äquivalenzrelation)
Beweis Version 2:

Sei %%M%% eine Menge und %%P%% eine Zerlegung dieser Menge. Wir führen den Beweis in zwei Schritten. Zunächst beweisen wir die Existenz einer solchen Äquivalenzrelations und danach die Eindeutigkeit.

Beweis: Existenz einer Äquivalenzrelation, die diese Zerlegung induziert

Wir definieren die Relation %%\sim%% über folgende Definition:

%%x\sim y :\Leftrightarrow \exists A\in P: x,y\in A%%

Zeige die folgenden drei Behauptungen, um die Existenz zu beweisen:

Beweis: Eindeutigkeit dieser Äquivalenzrelation

Sei %%\sim_2%% eine weitere Äquivalenzrelation mit %%P=M/{\sim_2}%%. Sei %%x,y\in M%% beliebig. Es gilt dann $$\begin{align} x\sim_2 y & \Leftrightarrow \exists [a] \in M/{\sim_2}: x,y\in [a] \\[0.3em] & \ \left\downarrow\ P=M/{\sim_2}\right.\\[0.3em] & \Leftrightarrow \exists A\in P: x,y\in A \end{align}$$


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.

Kommentieren Kommentare

Zu article Äquivalenzrelationen:
Sarittaa04 2017-07-13 14:02:24+0200
Hallo,
ich habe eine Frage bei
„x und y sind ungerade“ auf der Menge ℕ≥1" Wie kommt ihr da auf die zwei, muss die Zahl nicht ungerade sein ? und muss man hier für die Reflexivität X und Y getrennt voneinander betrachten ?
Renate 2017-07-14 11:24:17+0200
Hallo Sarittaa04, ich denke, das ist so gemeint:
"x und y sind ungerade" sollte man vielleicht besser lesen als "x und y haben die GEMEINSAMKEIT, dass sie BEIDE ungerade sind"
- Das ist dann eine Relation, in der zwei Zahlen zueinander stehen können (z. B. 19 und 23) oder auch nicht (z. B. 20 und 27).
Insbesondere stehen zwei gerade Zahlen NIE in dieser Relation zueinander, und damit steht auch JEDE GERADE ZAHL nie zu sich selbst in dieser Relation - also zum Beispiel nicht 2 und 2 (ebensowenig natürlich wie 4 und 4 oder 700 und 700 usw.).
Daher kann die Relation nicht reflexiv sein, und damit ist sie keine Äquivalenzrelation.
Sarittaa04 2017-07-14 21:16:42+0200
Danke Renate für die schnelle Antwort, ich denke ich habe es dadurch jetzt erst richtig verstanden ;-)