Äquivalenzrelation – Serlo „Mathe für Nicht-Freaks“

Einführendes Beispiel

Eine Drehung um 90° hat dasselbe Ergebnis wie eine Drehung um 450°.

Oftmals verhalten sich verschiedene Objekte in bestimmten Aspekten gleich oder besitzen gleiche, beziehungsweise sehr ähnliche Eigenschaften. So ist das Ergebnis einer Drehung von $90^{\circ }$ dasselbe wie bei einer Drehung von $450^{\circ }$. Exemplare von Büchern derselben ISB-Nummer besitzen denselben Inhalt und Autor. In diesem Kapitel wirst du die mathematischen Werkzeuge kennen lernen, mit denen du solche Äquivalenzen zwischen Objekten einer Grundmenge sauber beschreiben kannst.

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

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.

Frage: Welche Eigenschaften besitzt diese Relation?

Die Relation ist

• reflexiv: Für jedes Buchexemplar $x$ gilt: $x$ und $x$ besitzen dieselbe ISB-Nummer. Sprich: ein Buchexemplar hat immer dieselbe ISB-Nummer wie es selbst.
• nicht irreflexiv: Weil die Grundmenge nicht leer ist, gibt es mindestens ein Buchexemplar $x$. Dieses steht mit sich selbst in Relation, weil die Relation reflexiv ist, und damit ist die Relation nicht irreflexiv.
• symmetrisch: Wenn $x$ und $y$ dieselbe ISB-Nummer besitzen, dann besitzen auch $y$ und $x$ dieselbe ISB-Nummer.
• nicht antisymmetrisch: Es gibt mindestens zwei verschiedene Buchexemplare $x$ und $y$, die dieselbe ISB-Nummer besitzen. Für diese beiden Exemplare steht zwar $x$ in Relation zu $y$ und $y$ in Relation zu $x$, aber es ist $x\neq y$.
• transitiv: Wenn die Buchexemplare $x$ und $y$ dieselbe ISB-Nummer besitzen und die Buchexemplare $y$ und $z$ dieselbe ISB-Nummer besitzen, dann besitzen auch $x$ und $z$ dieselbe ISB-Nummer.
• nicht linear: Nehme zwei verschiedene Buchexemplare $x$ und $y$, so dass beide eine verschiedene ISB-Nummer haben. Dann steht weder $x$ mit $y$ noch $y$ mit $x$ in Relation. Damit ist die Relation nicht linear.

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.

Menge von acht Buchexemplaren, die durch die Äquivalenzrelation „$x$ und $y$ besitzen dieselbe ISB-Nummer“ in Äquivalenzklassen zerlegt wurde.

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 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: "Für jedes Element $x$ aus der Grundmenge gilt: $x\sim x$"
• symmetrisch: "Für je zwei Elemente $x,y$ aus der Grundmenge gilt: $x\sim y\implies y\sim x$"
• transitiv: "Für je drei Elemente $x,y,z$ aus der Grundmenge gilt: $x\sim y$ und $y\sim z\implies x\sim z$"

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:

Entscheidungsbaum zum Nachweis von Äquivalenzrelationen

Verständnisfrage: Welche der folgenden Relationen ist eine Äquivalenzrelation?

1. „$x$ und $y$ gehen in dieselbe Klasse“ auf der Menge aller Schüler einer Schule
2. „$x\geq y$“ auf der Menge $\mathbb {Z}$ der ganzen Zahlen
3. „$x$ und $y$ sind ungerade“ auf der Menge $\mathbb {N} _{\geq 1}$
4. „$x$ und $y$ besitzen denselben Rest bei der Division durch zwei“ auf der Menge $\mathbb {N} _{\geq 1}$
5. „$x=y$“ auf einer beliebigen, nicht leeren Grundmenge $M$

Antwort:

1. Äquivalenzrelation
2. keine Äquivalenzrelation (die Relation ist nicht symmetrisch – so ist zwar $-3\leq -1$, aber nicht auch $-1\leq -3$)
3. keine Äquivalenzrelation (die Relation ist nicht reflexiv – beispielsweise steht 2 nicht mit sich selbst in Relation)
4. Äquivalenzrelation
5. Äquivalenzrelation

Verständnisfrage: Wie viele totale Äquivalenzrelationen auf einer Grundmenge $M$ gibt es? (Eine Relation $R$ ist total, wenn für jeweils zwei Elemente $x$ und $y$ mindestens ein Element mit einem anderen in Relation steht. Sprich es gilt $xRy$ oder $yRx$.)

Sei $R\subseteq M\times M$ eine Äquivalenzrelation auf der Grundmenge $M$. Seien $x,y\in M$ beliebig. Da $R$ total ist, steht $x$ in Relation zu $y$ oder $y$ in Relation zu $x$. Sei oBdA $x\,R\,y$. Auf Grund der Symmetrie ist dann aber auch $y\,R\,x$. Damit steht jedes Element mit jedem anderen Element in Relation.

Es gibt also genau eine totale Äquivalenzrelation auf einer Grundmenge $M$, nämlich $R=M\times M$, bei der jedes Element mit jedem anderen in Relation steht.

Ä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]\iff x\sim y$

Greift man aus jeder Äquivalenzklasse ein Element heraus, so erhält man ein Vertretersystem:

Definition (Vertretersystem, Repräsentantensystem)

Ist $\sim$ eine Äquivalenzrelation auf $M$, so ist ein Vertretersystem (oder Repräsentantensystem) eine Teilmenge von $M$, die aus jeder Äquivalenzklasse von $\sim$ genau ein Element enthält.

Verständnisfrage: Wie sehen die Äquivalenzklassen der folgenden Äquivalenzrelationen aus? Gib ein mögliches Vertretersystem an.

1. „$x$ und $y$ gehen in dieselbe Klasse“ auf der Menge aller Schüler einer Schule
2. „$x$ und $y$ besitzen denselben Rest bei der Division durch zwei“ auf der Menge $\mathbb {N} _{\geq 1}$
3. „$x=y$“ auf einer beliebigen, nicht leeren Grundmenge $M$

Antwort:

1. Die Menge der Äquivalenzklassen ist die Menge aller Klassen der Schule. Dabei ist jede Klasse als Menge aller Schüler modelliert, die diese Klasse besuchen. Ein mögliches Vertretersystem ist die Menge aller Klassensprecher.
2. Es gibt zwei Äquivalenzklassen: Die Menge $\{2,4,6,8,\ldots \}$ aller Zahlen, die restlos durch 2 geteilt werden können, und die Menge $\{1,3,5,7,\ldots \}$ aller Zahlen, die bei Division durch 2 den Rest 1 lassen. Damit zerfällt die Grundmenge $\mathbb {N} _{\geq 1}$ in die Menge der geraden und in die Menge der ungeraden Zahlen. Ein Vertretersystem ist z.B. $\{4,7\}$
3. Jede Äquivalenzklasse ist einelementig. Die Grundmenge zerfällt also in die Menge $\{\,\{x\}\,|\,x\in M\}$ (Beachte, dass dies eine Menge von einelementigen Mengen ist. Die Zerlegungsmenge ist ungleich der Grundmenge). Das einzige Vertretersystem ist $M$ selbst.

Zerlegung einer Menge

Oft haben wir bereits von der Zerlegung einer Menge gesprochen (welche in der Mengenlehre auch Partition genannt wird). Eine Zerlegung ist eine Aufteilung einer Grundmenge in verschiedene Teilmengen, so dass jedes Element aus der Grundmenge in genau einer Teilmenge enthalten ist. Eine Zerlegung kann man also als eine Menge von Teilmengen der Grundmenge auffassen. Damit garantiert ist, dass jedes Element der Grundmenge in genau einer Teilmenge enthalten ist, müssen zusätzliche Bedingungen erfüllt sein, die in der folgenden Definition zusammengefasst sind:

Definition (Zerlegung einer Menge)

Eine Zerlegung einer Menge $M$ ist eine Menge $P$ von Teilmengen von $M$ (also $P\subseteq {\mathcal {P}}(M)$), welche folgende Bedingungen erfüllt:

• Die Vereinigung aller Mengen von $P$ ergibt die Menge $M$:
  $\bigcup _{A\in P}A=M$
• Alle Mengen von $P$ sind paarweise disjunkt:
  $\forall A,B\in P:A\neq B\implies A\cap B=\emptyset$
• Alle Mengen von $P$ sind nicht leer:
  $\forall A\in P:A\neq \emptyset$

Im nächsten Abschnitt werden wir den Zusammenhang zwischen Äquivalenzrelation und der durch ihr definierten Zerlegung genauer untersuchen. Alternativ kann die Zerlegung $P$ durch folgende Aussagen charakterisiert werden:

• $\forall x\in M:\exists A\in P:x\in A$,
• $\forall A,B\in P:\forall x\in M:x\in A\land x\in B\implies A=B$,
• $\forall A\in P:\exists x\in M:x\in A$.

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)

Um zu zeigen, dass ${M/{\sim }}:=\{[x]\,|\,x\in M\}$ eine Zerlegung von $M$ ist, müssen wir folgende Behauptungen beweisen:

Beweisschritt: $\bigcup _{A\in P}A=M$

Es ist genau dann $\bigcup _{A\in P}A=M$, wenn $\bigcup _{A\in P}A\subseteq M$ und wenn $M\subseteq \bigcup _{A\in P}A$ ist.

Beweisschritt: $\bigcup _{A\in P}A\subseteq M$

Jede Äquivalenzklasse $A\in P$ ist nach Definition eine Teilmenge von $M$. Damit ist auch die Vereinigung aller Äquivalenzklassen $\bigcup _{A\in P}A$ eine Teilmenge von $M$.

Beweisschritt: $M\subseteq \bigcup _{A\in P}A$

Sei $x\in M$ beliebig. Da auf Grund der Reflexivität von $R$ das Element $x$ in Relation zu sich selbst steht, ist $x\in [x]$. Nun ist $[x]\in P$ und damit

$x\in [x]\subseteq \bigcup _{A\in P}A\implies x\in \bigcup _{A\in P}A$

Da $x$ beliebig war, ist $M\subseteq \bigcup _{A\in P}A$.

Beweisschritt: $\forall A,B\in P:A\neq B\implies A\cap B=\emptyset$

Seien $A,B\in P$ mit $A\neq B$. Dann ist $A=[x]$ und $B=[y]$ für ein $x,y\in M$.

Widerspruchsbeweis: Sei $A\cap B=[x]\cap [y]\neq \emptyset$. Dann gibt es ein $a\in M$ mit $a\in [y]$ und $a\in [x]$. Damit ist $a\sim x$ und $a\sim y$. Aus der Transitivität folgt $x\sim y$ und damit $[x]=[y]$ aus dem Satz über den Zusammenhang zwischen Äquivalenzklassen und der Äquivalenz der Repräsentanten des vorherigem Abschnitts. Jedoch ist $A=[x]=[y]=B$ ein Widerspruch zu Annahme $A\neq B$, so dass $A\cap B=\emptyset$ sein muss.

Beweisschritt: $\forall A\in P:A\neq \emptyset$

Sei $A\in P$ beliebig. Dann ist $A=[x]$ für ein $x\in M$. Wegen der Reflexivität von der Äquivalenzrelation ist $x\sim x$ und damit $x\in [x]$. Daraus folgt, dass insbesondere $A=[x]\neq \emptyset$ ist.

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?

Frage: 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:

$x{\text{ und }}y{\text{ gehören derselben Partitionsmenge an}}\implies x\sim y$

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

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

Beweis (Jede Zerlegung induziert eine Äquivalenzrelation)

Sei $M$ eine Menge und $P$ eine Zerlegung dieser Menge.

Beweisschritt: Existenz einer Äquivalenzrelation, die diese Zerlegung induziert

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

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

Beweisschritt: $\sim$ ist eine Äquivalenzrelation

Beweisschritt: $\sim$ ist reflexiv

Sei $x\in M$ beliebig. Da die Vereinigung aller Mengen von $P$ die Grundmenge ergibt, gibt es eine Menge $A\in P$ mit $x\in A$. Damit ist

$\left(\exists A\in P:x,x\in A\right)\implies x\sim x$

Beweisschritt: $\sim$ ist symmetrisch

Sei $x,y\in M$ beliebig. Es ist

${\begin{aligned}x\sim y&\iff \exists A\in P:x,y\in A\\[0.3em]&\iff \exists A\in P:y,x\in A\\[0.3em]&\iff y\sim x\end{aligned}}$

Beweisschritt: $\sim$ ist transitiv

Sei $x,y,z\in M$ mit $x\sim y$ und $y\sim z$. Dann gibt es ein $A\in P$ und ein $B\in P$ mit $x,y\in A$ und $y,z\in B$. Damit ist $A\cap B\neq \emptyset$, da $y$ sowohl ein Element von $A$ als auch ein Element von $B$ ist. Da $P$ eine Partition ist, muss $A=B$ sein. Daraus folgt $x,z\in A=B$ und damit $x\sim z$.

Beweisschritt: $\forall A\in P:\forall x\in A:[x]=A$

Sei $A\in P$ und $x\in A$ beliebig.

Beweisschritt: $[x]\subseteq A$

Sei $y\in [x]$ beliebig, also $x\sim y$. Dann gibt es ein $B\in P$ mit $x,y\in B$. Da $x\in A$ und $x\in B$ ist, ist $A\cap B\neq \emptyset$. Daraus folgt $A=B$, weil verschiedene Mengen von $P$ disjunkt sind. Damit ist $y\in B=A$, was zu beweisen war.

Beweisschritt: $A\subseteq [x]$

Sei $y\in A$ beliebig. Damit ist sowohl $x$ als auch $y$ ein Element von $A$ und damit $y\sim x$. Daraus folgt $y\in [x]$. Da $y\in A$ beliebig war, ist $A\subseteq [x]$.

Aus den Behauptungen (2.1) und (2.2) folgt, dass $[x]=A$ ist.

Beweisschritt: $M/{\sim }=P$

Beweisschritt: $M/{\sim }\subseteq P$

Sei $[x]\in M/{\sim }$ beliebig. Da $\bigcup _{A\in P}A=M$ ist, gibt es ein $A\in P$ mit $x\in A$. Aus der Behauptung (2) folgt, dass $[x]=A$ und damit $[x]=A\in P$ ist.

Beweisschritt: $P\subseteq M/{\sim }$

Sei $A\in P$ beliebig. Da alle Mengen aus $P$ nach Definition nicht leer sind, gibt es ein $x\in M$ mit $x\in A$. Aus Behauptung (2) folgt, dass $A=[x]$ und damit $A=[x]\in M/{\sim }$ ist.

Die Behauptung (3) folgt direkt aus Behauptung (3.1) und (3.2).

Beweisschritt: Eindeutigkeit dieser Äquivalenzrelation

Sei $\sim _{2}$ eine weitere Äquivalenzrelation mit $P=M/{\sim _{2}}$. Sei $x,y\in M$ beliebig. Es gilt dann

${\begin{aligned}x\sim _{2}y&\iff \exists [a]\in M/{\sim _{2}}:x,y\in [a]\\[0.3em]&\ \left\downarrow \ P=M/{\sim _{2}}\right.\\[0.3em]&\iff \exists A\in P:x,y\in A\end{aligned}}$

Induzierte Äquivalenzrelation

Hinweis

Wir benutzen hier den Begriff der Funktion, der erst später definiert wird.

Das Nachrechnen, dass eine gegebene Relation wirklich eine Äquivalenzrelation ist, benutzt oft ein Standardschema, was wir in diesem Satz zusammenfassen:

Satz

Seien $M,N$ nichtleere Mengen und $f:M\to N$ eine Abbildung.

Auf $N$ sei eine Äquivalenzrelation $\sim _{N}$ gegeben. Wir definieren für $x,y\in M$ die Relation $x\sim _{M}y:\iff f(x)\sim _{N}f(y)$.

Dann ist $\sim _{M}$ eine Äquivalenzrelation. Diese nennen wir "die durch $f$ induzierte Äquivalenzrelation".

Beweis

Wir müssen die drei Eigenschaften einer Äquivalenzrelation nachprüfen. Seien also $x,y,z\in M$

Beweisschritt: Reflexivität

$f(x)\sim _{N}f(x)$, da $\sim _{N}$ reflexiv ist. Das ist nach Definition von $\sim _{M}$ äquivalent zu $x\sim _{M}x$, also ist $\sim _{M}$ reflexiv.

Beweisschritt: Symmetrie

Gelte $x\sim _{M}y$ für $x$ und $y\in M$. Wir zeigen $y\sim _{M}x$.

${\begin{aligned}&\ x\sim _{M}y\\[0.3em]&\ {\color {OliveGreen}\downarrow {\text{Definition von }}{\sim _{M}}}\\[0.3em]\implies &\ f(x)\sim _{N}f(y)\\[0.3em]&\ {\color {OliveGreen}\downarrow {\sim _{N}}{\text{ ist symmetrisch}}}\\[0.3em]\implies &\ f(y)\sim _{N}f(x)\\[0.3em]&\ {\color {OliveGreen}\downarrow {\text{Definition von }}{\sim _{M}}}\\[0.3em]\implies &\ y\sim _{M}x\end{aligned}}$

Also ist $\sim _{M}$ symmetrisch.

Beweisschritt: Transitivität

Sei $x\sim _{M}y$ und $y\sim _{M}z$. Wir zeigen, dass $x\sim _{M}z$.

${\begin{aligned}&\ x\sim _{M}y{\text{ und }}y\sim _{M}z\\[0.3em]&\ {\color {OliveGreen}\downarrow {\text{nach Definition von }}{\sim _{M}}}\\[0.3em]\implies &\ f(x)\sim _{N}f(y){\text{ und }}f(y)\sim _{N}f(z)\\[0.3em]&\ {\color {OliveGreen}\downarrow {\sim _{N}}{\text{ ist transitiv}}}\\[0.3em]\implies &\ f(x)\sim _{N}f(z)\\[0.3em]&\ {\color {OliveGreen}\downarrow {\text{nach Definition von }}{\sim _{M}}}\\[0.3em]\implies &\ x\sim _{M}z\end{aligned}}$

Also ist $\sim _{M}$ transitiv.

Damit ist $\sim _{M}$ eine Äquivalenzrelation auf $M$.

Hinweis

Die häufigste Anwendung ist die, wo auf der Menge $N$ die Relation $\sim _{N}$ die Gleichheit "$=$" ist. Ist $f$ dann noch surjektiv, so ist keine Urbildmenge $f^{-1}(\{n\})$ für $n\in N$ leer und die Äquivalenzklassen in $M$ sind gerade die Urbilder der Elemente von $N$. In diesem Fall kann man den Beweis schneller führen, wenn man nachrechnet, dass die Urbilder der Elemente von $N$ eine Zerlegung der Menge $M$ erzeugen.

Beispiel (Induzierte Äquivalenzrelation in $\mathbb {N}$)

Wähle $M=\mathbb {N}$, $N=\{0,1,2\}$ und $f$ die Funktion, die jeder natürlichen Zahl den Rest bei der Division durch 3 zuordnet. Dann besteht $M$ aus den Äquivalenzklassen

$\{3,6,9,12,\ldots \}$ (Rest 0)

$\{1,4,7,10,\ldots \}$ (Rest 1)

$\{2,5,8,11,\ldots \}$ (Rest 2)

Beispiel (Induzierte Äquivalenzrelation im $\mathbb {R} ^{2}$)

Seien $M=\mathbb {R} ^{2}$ und $N=\mathbb {R}$. Außerdem definiere $f:\mathbb {R} ^{2}\to \mathbb {R}$ mit $f(x,y)=y-2x$. Die Funktion $f$ ist wegen $f(0,y)=y$ sicher surjektiv. Die Äquivalenzklassen sind Geraden parallel zu der Urspungsgeraden $y=2x$, auf denen $y-2x$ den konstanten Wert $c$ hat.

Warum sind Äquivalenzklassen interessant?

In vielen Fällen betrachtet man Äquivalenzklassen auf einer Menge mit einer durch einer oder mehrere Verknüpfungen definierten Struktur, wie Gruppe oder Vektorraum.

Dort betrachtet man Äquivalenzrelationen, wo man die Verknüpfungen der Grundmenge auf die Äquivalenzklassen "transportieren" kann. Als Teaser: wenn man in dem letzten Beispiel irgendeinen Vektor des $\mathbb {R} ^{2}$ mit $c=2$ zu einen beliebigen anderen Vektor mit $c=3$ addiert, erhält man immer einen Vektor der Klasse mit $c=5$, egal, welche Vektoren man nimmt.

Genauso landet man immer in der Klasse mit $c=6$ , wenn man einen beliebigen Vektor der Klasse mit $c=2$ mit $3$ multipliziert.

Das wird später im Kapitel Faktorraum genauer untersucht.