Mengen

Äquivalenzrelationen

Definition: Teilt

Sei \(n \in \mathbb{N}\) und \(a \in \mathbb{Z}\). Wir sagen "\(n\) teilt \(a\)" und schreiben dafür \(n|a\), wenn es ein \(x \in \mathbb{Z}\) gibt, sodass \(x \cdot n = a\).

Beispiele: Teilt

1. Es ist \(2|6\), denn \(3 \cdot 2 = 6\).
2. Es ist \(5|35\), denn \(7 \cdot 5 = 35\).
3. Es ist \(8|24\), denn \(3 \cdot 8 = 24\).
4. Es ist \(4|-12\), denn \((-3) \cdot 4 = -12\).
5. Es ist \(3|-15\), denn \((-5) \cdot 3 = -15\).

Satz: Teiler von Summen und Differenzen

Sei \(n \in \mathbb{N}\) und \(a, b \in \mathbb{Z}\). Es gelte \(n|a\) und \(n|b\). Dann gilt auch \(n|(a + b)\) und \(n|(a - b)\).

Beweis:

Es gelte \(n|a\). Dann gibt es ein \(x_1 \in \mathbb{Z}\) mit \(x_1n = a\). Weiterhin gelte \(n|b\). Dann gibt es ein \(x_2 \in \mathbb{Z}\) mit \(x_2n = b\). Daraus folgt \(a + b = x_1n + x_2n = (x_1 + x_2) \cdot n\), also \(n|(a + b)\). Weiterhin folgt \(a - b = x_1n - x_2n = (x_1 - x_2) \cdot n\), also \(n|(a - b)\). \(\square\)

Beispiele: Teiler von Summen und Differenzen

1. Es ist \(2|6\), denn \(3 \cdot 2 = 6\), und \(2|8\), denn \(4 \cdot 2 = 8\). Offenbar ist dann \(3 \cdot 2 + 4 \cdot 2 = 7 \cdot 2 = 14 = 6 + 8\) und somit \(2|(6 + 8)\).
2. Es ist \(3|9\), denn \(3 \cdot 3 = 9\), und \(3|15\), denn \(5 \cdot 3 = 15\). Offenbar ist dann \(3 \cdot 3 + 5 \cdot 3 = 8 \cdot 3 = 24 = 9 + 15\) und somit \(3|(9 + 15)\).
3. Es ist \(5|20\), denn \(4 \cdot 5 = 20\), und \(5|35\), denn \(7 \cdot 5 = 35\). Offenbar ist dann \(4 \cdot 5 - 7 \cdot 5 = (-3) \cdot 5 = -15 = 20 - 35\) und somit \(5|(20 - 35)\).

Definition: Kongruent modulo

Seien \(a, b \in \mathbb{Z}\) und sei \(m \in \mathbb{N}\). Wir schreiben \(a \equiv b\;mod\;m\), wenn \(m\) die Zahl \(b - a\) teilt, wenn also \(m|(b - a)\) gilt. Ausgesprochen wird \(a \equiv b\;mod\;m\) als "\(a\) ist kongruent zu \(b, modulo\;m\)".

Beispiele: Kongruent modulo

1. Es ist \(21 \equiv 0\;mod\;7\), denn \(7|(0 - 21)\) wegen \(-3 \cdot 7 = -21\).
2. Es ist \(2 \equiv 12\;mod\;5\), denn \(5|(12 - 2)\) wegen \(2 \cdot 5 = 10\).
3. Es ist \(-8 \equiv 4\;mod\;2\), denn \(2|(4 - (-8))\) wegen \(6 \cdot 2 = 12\).
4. Es ist \(5 \equiv -19\;mod\;4\), denn \(4|(-19 - 5)\) wegen \((-6) \cdot 4 = -24\).

Definition: Äquivalenzrelation

Sei \(M\) eine Menge. Eine Teilmenge \(R \subseteq M \times M\) heißt Äquivalenzrelation auf \(M\), wenn für alle \(x, y, z \in M\) die drei folgenden Eigenschaften gelten:

1. Reflexivität: \((x, x) \in R\)
2. Symmetrie: Wenn \((x, y) \in R\), dann gilt auch \((y, x) \in R\)
3. Transitivität: Wenn \((x, y) \in R\) und \((y, z) \in R\), dann gilt auch \((x, z) \in R\)

Eine Äquivalenzrelation ist also eine Menge, deren Elemente bestimmte Eigenschaften erfüllen müssen.

Wenn \(R\) eine Äquivalenzrelation auf \(M\) ist und \((x, y) \in R\), dann schreiben wir dafür \(x \sim_R y\). Man spricht dies "\(x\) ist äquivalent zu \(y\)" aus.

Häufig schreibt man statt \(x \sim_R y\) abgekürzt einfach \(x \sim y\), wenn aus dem Zusammenhang hervorgeht, auf welche Menge sich die Äquivalenzrelation bezieht.

Beispiele: Äquivalenzrelationen

1. Sei \(M\) die Menge aller eingeschriebenen Studenten an einer bestimmten Universität. Die Universität bietet drei Studiengänge an: Medizin, Informatik und Geschichte. Jeder Student ist in genau einem dieser Studiengänge eingeschrieben. Falls zwei Studenten \(x, y \in M\) im gleichen Studiengang sind, so setzen wir hierfür \(x \sim y\). Dann ist \(\sim\) eine Äquivalenzrelation auf \(M\), wie man sich folgendermaßen überlegt.
   1. \(\sim\) ist reflexiv, denn für alle \(x \in R\) bezeichnen \(x\) und \(x\) dieselbe Person und diese ist natürlich im gleichen Studiengang wie sie selbst. Es gilt also \(x \sim x\).
   2. \(\sim\) ist symmetrisch, denn für alle \(x, y \in R\) besuchen \(y\) und \(x\) den gleichen Studiengang, wenn \(x\) und \(y\) den gleichen Studiengang besuchen. Aus \(x \sim y\) folgt somit \(y \sim x\).
   3. \(\sim\) ist transitiv, denn für alle \(x, y, z \in R\) gilt: Wenn \(x\) und \(y\) den gleichen Studiengang besuchen, und wenn überdies \(y\) und \(z\) den gleichen Studiengang besuchen, dann besuchen folglich auch \(x\) und \(z\) den gleichen Studiengang. Aus \(x \sim y\) und \(y \sim z\) folgt somit \(x \sim z\).
   Damit erfüllt \(\sim\) alle geforderten Eigenschaften und ist somit eine Äquivalenzrelation auf \(M\). \(\square\)


2. Sei \(n \in \mathbb{N}\). Für \(a, b \in \mathbb{Z}\) setzen wir \(a \sim_n b\), wenn \(n\) die Zahl \(a - b\) teilt, also \(n|(a - b)\), oder, anders ausgedrückt, wenn es ein \(x \in \mathbb{Z}\) gibt mit \(xn = a - b\). Ausgesprochen wird \(a \sim_n b\) als "\(a\) ist äquivalent zu \(b\) modulo \(n\)". \(a \sim_n b\) ist eine Äquivalenzrelation auf \(\mathbb{Z}\):
   1. \(\sim_n\) ist reflexiv, denn für \(a \in \mathbb{Z}\) gilt wegen \(0 \cdot n = 0 = a - a\), dass \(n|(a - a)\).
   2. \(\sim_n\) ist symmetrisch, denn für \(a, b \in \mathbb{Z}\) gilt, falls \(n|(a - b)\), so ist auch \(n|-(a - b)\) und damit \(n|(b - a)\).
   3. \(\sim_n\) ist transitiv, denn falls \(n|(a - b)\) und \(n|(b - c)\) für \(a, b, c \in \mathbb{Z}\) so gilt auch \(n|(a - b) + (b - c)\), und wegen \((a - b) + (b - c) = a - c\) gilt damit \(n|(a - c)\). \(\square\)
   Wenn \(a \sim_n b\) ist, dann gilt \(n|(a - b)\). Dies ist gleichbedeutend mit \(a \equiv b\;mod\;n\). Man bezeichnet deshalb die Äquivalenzrelation \(\sim_n\) auch als Kongruent-Modulo-Äquivalenzrelation.

Definition: Äquivalenzklasse

Sei \(M\) eine Menge und sei \(R\) eine Äquivalenzrelation auf \(M\). Eine nichtleere Teilmenge \(L \subseteq M\) heißt Äquivalenzklasse bezüglich \(R\), falls die beiden folgenden Eigenschaften gelten:

1. Aus \(x, y \in L\) folgt \(x \sim y\).
2. Wenn \(x \in L\) und \(y \in M\) ist, und wenn \(x \sim y\) gilt, so folgt \(y \in L\).

Eine Äquivalenzklasse bezeichnet somit eine nichtleere Teilmenge \(L\) einer Menge \(M\), bezüglich der wir eine Äquivalenzrelation gebildet haben. Eigenschaft 1. besagt, dass alle Elemente einer solchen Äquivalenzklasse \(L\) paarweise zueinander äquivalent sein müssen. Eigenschaft 2. besagt, dass jedes Element von \(M\), welches äquivalent zu einem Element der Äquivalenzklasse \(L\) ist, auch Element dieser Äquivalenzklasse sein muss.

Beispiele: Äquivalenzklassen

1. Betrachten wir die Menge \(M\) der eingeschriebenen Studenten in den Fächern Medizin, Informatik und Geschichte aus dem vorherigen Beispiel. Wir haben gesehen, dass die Eigenschaft, ob zwei Studenten im gleichen Studiengang sind, eine Äquivalenzrelation auf \(M\) bildet. Wir nehmen an, dass jeder Studiengang mindestens einen Studenten hat (sonst würde er von der Universität nicht angeboten). Jeder der Studenten ist also in genau einem dieser Studiengäng eingeschrieben. Dann können wir drei Mengen definieren: \[S_M := \{x \in M|x \text{ studiert Medizin}\} \subseteq M\] \[S_I := \{x \in M|x \text{ studiert Informatik}\} \subseteq M\] \[S_G := \{x \in M|x \text{ studiert Geschichte}\} \subseteq M\] Zunächst halten wir fest, dass \(S_M \not = \emptyset, S_I \not = \emptyset\) und \(S_G \not = \emptyset\) ist. Das ist nach der vorangegangenen Definition wichtig, denn Äquivalenzklassen sind stets nichtleere Teilmengen. Wenn \(x, y \in S_M\) ist, dann studieren \(x\) und \(y\) beide Medizin, sind also im gleichen Studiengang eingeschrieben. Damit gilt \(x \sim y\). Entsprechendes gilt für \(x, y \in S_I\) und \(x, y \in S_G\). Somit ist die erste Eigenschaft für Äquivalenzklassen für alle drei Mengen erfüllt. Wenn \(x \in S_M\) äquivalent zu \(y \in M\) ist, d.h., wenn \(x \sim y\) gilt, dann sind \(x\) und \(y\) im gleichen Studiengang und studieren insbesondere beide Medizin. Damit ist aber auch \(y \in S_M\), denn \(S_M\) ist gerade die Menge aller Medizinstudenten. Entsprechendes gilt für die Mengen \(S_I\) und \(S_G\). Somit ist die zweite Eigenschaft für Äquivalenzklassen ebenfalls für alle drei Mengen erfüllt. Damit folgt, dass \(S_M, S_I\) und \(S_G\) Äquivalenzklassen bezüglich \(\sim\) sind. \(\square\)


2. Betrachten wir die Äquivalenzrelation \(\sim_n\) auf \(\mathbb{Z}\). Sei \(a \in \mathbb{Z}\) und \([a] := \{a + kn|k \in \mathbb{Z}\}\). Die Menge \([a]\) ist eine Äquivalenzklasse bezüglich \(\sim_n\), was man sich wie folgt überlegt:
   Wegen \(a = a + 0n\) ist \(a \in [a]\). Somit ist \([a] \not = \emptyset\). Seien \(x, y \in [a]\). Dann gibt es \(k, k' \in \mathbb{Z}\) mit \(x = a + kn\) und \(y = a + k'n\). Es ist \(x - y = a + kn - a - k'n = n(k - k')\). Wegen \(n|n(k - k')\) gilt \(n|(x - y)\) und damit \(x \sim_n y\). Sei \(x \in [a]\), d.h., es gibt ein \(k \in \mathbb{Z}\) mit \(x = a + kn\). Weiterhin sei \(y \in \mathbb{Z}\) und es gelte \(x \sim_n y\), also \(n|(x - y)\). Dann folgt \(n|((a + kn) - y)\). Somit gib es ein \(m \in \mathbb{Z}\) mit \(mn = a + kn - y\). Wir formen die Gleichung um und erhalten \(y = a + kn - mn = a + (k - m)n\). Daraus folgt \(y \in [a]\). Insgesamt folgt somit, dass \([a]\) eine Äquivalenzklasse bezüglich \(\sim_n\) ist. \(\square\)

Man kann sich nun die Frage stellen, ob ein Element auch in mehr als einr Äquivalenzklasse enthalten sein könnte. Der folgende Satz besagt, dass das nicht möglich ist.

Satz: Eindeutigkeit von Äquivalenzklassen

Sei \(M\) eine Menge und sei \(R\) eine Äquivalenzrelation auf \(M\). Dann liegt jedes \(x \in M\) in genau einer Äquivalenzklasse von \(M\) bezüglich \(R\).

Beweis:

Sei \(x \in M\) und sei \(L_x := \{y \in M|y \sim x\}\).

Zunächst zeigen wir, dass \(L_x\) eine Äquivalenzklasse ist, die \(x\) enthält. Anschließend werden wir beweisen, dass \(L_x\) eindeutig ist.

Es ist \(L_x \not = \emptyset\), denn wegen der Reflexivität von \(\sim\) ist \(x \sim x\) und damit \(x \in L_x\).

Seien \(y, y' \in L_x\). Dann gilt \(y \sim x\) und \(y' \sim x\). Weil \(\sim\) symmetrisch ist, folgt \(x \sim y'\). Weil \(\sim\) zudem transitiv ist, folgt aus \(y \sim x\) und \(x \sim y'\) weiterhin \(y \sim y'\).

Sei \(y \in L_x\) und \(y' \in M\). Es gelte \(y \sim y'\). Wegen \(y \in L_x\) gilt \(x \sim y\). Weil \(\sim\) transitiv ist, folgt \(x \sim y'\) und somit \(y' \in L_x\).

Folglich ist \(L_x\) eine Äquivalenzklasse, die \(x\) enthält. Es bleibt zu zeigen, dass \(L_x\) eindeutig ist, d.h. dass \(x\) in keiner anderen Äquivalenzklasse liegt.

Sei hierzu \(L'_x\) eine weitere Äquivalenzklasse von \(M\) bezüglich \(R\), die \(x\) enthält.

Sei \(y \in L_x\). Dann ist \(y \sim x\) und auch \(y \in M\). Weil \(L'_x\) eine Äquivalenzklasse ist und weil \(x \in L'_x\), folgt mit der zweiten Eigenschaft von Äquivalenzklassen, dass \(y \in L'_x\) ist. Somit gilt \(L_x \subseteq L'_x\).

Sei \(y' \in L'_x\). Dann ist \(y' \sim x\) und auch \(y' \in M\). Weil \(L_x\) eine Äquivalenzklasse ist und weil \(x \in L_x\), folgt mit der zweiten Eigenschaft von Äquivalenzklassen, dass \(y' \in L_x\) ist. Somit gilt ebenfalls \(L'_x \subseteq L_x\) und damit insgesamt \(L_x = L'_x\). \(\square\)

Damit haben wir die oben gestellte Frage beantwortet: Jedes Element der Menge liegt genau in einer Äquivalenzklasse. Betrachten wir abschließend noch kurz, wie Äquivalenzklassen zueinander in Beziehung stehen können.

Satz: Beziehungen von Äquivalenzklassen

Sei \(M\) eine nichtleere Menge und sei \(R\) eine Äquivalenzrelation auf \(M\). Seien \(L\) und \(L'\) Äquivalenzklassen bezüglich \(R\). Dann sind \(L\) und \(L'\) entweder gleich oder disjunkt.

Beweis:

Die Behauptung folgt unmittelbar aus der Eindeutigkeit der Äquivalenzklassen, die wir zuvor bewiesen haben. Falls zwei Äquivalenzklassen ein gemeinsames Element enthalten, sind sie aufgrund der Eindeutigkeit gleich. Falls sie kein gemeinsames Element enthalten, sind sie disjunkt. Eine dritte Möglichkeit existiert nicht. \(\square\)

Jede Äquivalenzrelation auf einer nichtleeren Menge liefert somit eine Zerlegung dieser Menge in disjunkte Äquivalenzklassen. Das Praktische an Äquivalenzklassen ist, dass die Wahl eines Elementes daraus häufig beliebig ist, sofern man nur an der Eigenschaft interessiert ist, durch die die Äquivalenzrelation definiert ist. Weil alle Elemente einer Klasse zueinander äquivalent sind und damit den gleichen Wert in der betrachteten Eigenschaft haben, ist die Auswahl eines Vertreters beliebig. Es ist beispielsweise vollkommen irrelevant, welchen Studenten wir im obigen Beispiel aus der Gruppe der Medizinstudenten betrachten, wenn wir nur an der Studienrichtung interessiert sind, weil alle Personen in dieser Gruppe das gleiche, nämlich Medizin, studieren. Dies schlägt sich in folgender Definition nieder.

Definition: Repräsentant einer Äquivalenzklasse

Sei \(M\) eine nichtleere Menge und sei \(R\) eine Äquivalenzrelation auf \(M\). Sei \(L\) eine Äquivalenzklasse bezüglich \(R\). Ein beliebiges Element \(x \in L\) nennen wir Repräsentant der Äquivalenzklasse.

Beispiele: Beziehungen und Repräsentanten von Äquivalenzklassen

1. Betrachten wir unser Beispiel mit den eingeschriebenen Studenten in den Fächern Medizin, Informatik und Geschichte. Wir haben gesehen, dass die Äquivalenzklassen hierzu durch \(S_M, S_I\) und \(S_G\) gegeben sind. Offenbar ist \(M = S_M \cup S_I \cup S_G\) eine Zerlegung der Menge \(M\) und es gilt \(S_M \cap S_I = \emptyset, S_M \cap S_G = \emptyset\) und \(S_I \cap S_G = \emptyset\). Jeder Medizinstudent ist ein Repräsentant der Äquivalenzklasse \(S_M\), jeder Informatikstudent ein Repräsentant von \(S_I\) und jeder Geschichtsstudent ein Repräsentant von \(S_G\).


2. Betrachten wir die Äquivalenzrelation \(\sim_n\). Die Äquivalenzklassen bezüglich \(\sim_n\) waren für \(a \in \mathbb{Z}\) gegeben durch \([a] := \{a + kn|k \in \mathbb{Z}\}\). Wir haben also Äquivalenzklassen \([0] := \{0 + kn|k \in \mathbb{Z}\}, [1] := \{1 + kn|k \in \mathbb{Z}\}, [2] := \{2 + kn|k \in \mathbb{Z}\}\) usw. Zunächst überlegen wir uns, dass diese Klassen tatsächlich eine Zerlegung von \(\mathbb{Z}\) liefern: \([0]\) ist die Äquivalenzklasse, die \(0\) enthält. Da alle Äquivalenzklassen, die \(0\) enthalten, gleich sind, können wir \(0\) als Repräsentanten dieser Klasse wählen und \([0]\) als die Äquivalenzklasse bezeichnen, die \(0\) enthält. Entsprechend wählen wir \(1\) als Repräsentanten der Äquivalenzklasse \([1]\) und bezeichnen \([1]\) als die Äquivalenzklasse, die \(1\) enthält. \([2]\) ist dann die Äquivalenzklasse, die \(2\) enthält usw.
   Offenbar ist \(n \in [0]\) und \(n \in [n]\). Somit sind \([0]\) und \([n]\) nicht disjunkt und damit gleich, d.h. \([0] = [n]\). Ebenso ist \(n \in [2n], n \in [3n]\) usw., also allgemein \(n \in [kn]\) für \(k \in \mathbb{Z}\). Damit ist \([0] = [kn]\) für \(k \in \mathbb{Z}\). Entsprechend ist \(n + 1 \in [1]\) und \(n + 1 \in [n + 1]\), also \([1] = [n + 1]\). Weiterhin ist \(n + 1 \in [2n + 1], n + 1 \in [3n + 1]\) usw., also allgemein \(n + 1 \in [kn + 1]\) für \(k \in \mathbb{Z}\). Somit gilt \([1] = [kn + 1]\) für \(k \in \mathbb{Z}\). Analog ist \([2] = [kn + 2], [3] = [kn + 3]\) usw. Wir erhalten somit eine Zerlegung von \(\mathbb{Z}\) durch \(\mathbb{Z} = [0]\;\cup\;[1]\;\cup\;...\;\cup\;[n - 1]\).
   Untersuchen wir, ob diese Mengen disjunkt sind: Seien \(a, b \in \mathbb{Z}\) mit \(0 \leq a, b \lt n\) und sei \(x \in [a]\;\cap\;[b]\). Dann gibt es \(k, k' \in \mathbb{Z}\) mit \(x = a + nk\) und \(x = b + nk'\). Indem wir die Gleichungen voneinander subtrahieren, erhalten wir \(0 = a + nk - b - nk' = a - b + n(k - k')\). Wir stellen die Gleichung um und erhalten \(b - a = n(k - k')\). Damit folgt \(n|(b - a)\), d.h. \(n\) ist ein Teiler von \(b - a\). Wegen \(0 \leq a, b \lt n\) ist \(-n \lt b - a \lt n\) und somit \(-1 \lt \frac{b - a}{n} \lt 1\). Weil \(n\) ein Teiler von \(b - a\) ist, muss \(\frac{b - a}{n} \in \mathbb{Z}\) sein, und damit folgt \(\frac{b - a}{n} = 0\). Wegen \(n \in \mathbb{N}\) ist insbesondere \(n \not = 0\) und damit folgt \(b - a = 0\), also \(a = b\). Wir erhalten somit eine disjunkte Zerlegung von \(\mathbb{Z}\) durch \(\mathbb{Z} = [0]\;\cup\;[1]\;\cup\;...\;\cup\;[n - 1]\) bezüglich der Äquivalenzrelation \(\sim_n\).