Äquivalenzrelation

Eine Äquivalenzrelation ist eine binäre Relation auf einer Menge, die reflexiv, symmetrisch und transitiv ist.

Motivation

Die Äquivalenzrelation stellt gewissermaßen eine Verfeinerung der Gleichheitsrelation dar. Wir können immer entscheiden, ob zwei Elemente einer Menge gleich sind, d. h. ob a = b. Manchmal ist es aber nützlich festzustellen, ob zwei Elemente nur ähnlich sind, nicht unbedingt gleich. Oder anders gesagt – ob sie eine bestimmte wesentliche Eigenschaft gemeinsam haben. Zum Beispiel können wir zwei Bücher als ähnlich betrachten, wenn sie dasselbe Genre haben – oder mit Hilfe der Äquivalenz: Zwei Bücher sind äquivalent, wenn sie dasselbe Genre haben.

Was würden wir von einer solchen Äquivalenz erwarten? Nehmen wir ein anderes Beispiel. Zwei Wörter sind ähnlich/äquivalent, wenn sie gleich lang sind.

Wir würden wohl erwarten, dass sich beim Messen der Ähnlichkeit zweier gleicher Wörter ergibt, dass sie ähnlich sind. Für alle Wörter muss also gelten, dass sie zu sich selbst ähnlich/äquivalent sind. In der Sprache der Relationen: Die Äquivalenzrelation muss reflexiv sein.

Wenn weiter das Wort „Bach“ zum Wort „Emma“ ähnlich/äquivalent ist, dann erwarten wir sicher, dass auch das Wort „Emma“ zum Wort „Bach“ äquivalent ist. Mit anderen Worten: Die Reihenfolge spielt keine Rolle. In der Sprache der Relationen: Die Äquivalenzrelation muss symmetrisch sein.

Und schließlich, wenn das Wort „Haus“ zum Wort „Baum“ ähnlich/äquivalent ist und das Wort „Baum“ zum Wort „Hand“ äquivalent ist, dann erwarten wir, dass auch die Wörter „Haus“ und „Hand“ äquivalent sind. Die Äquivalenzrelation muss also auch transitiv sein.

Mehr erwarten wir von einer Äquivalenz nicht.

Beispiele

Weitere Beispiele für Äquivalenzen:

• In derselben Stadt wohnen. Jonas wohnt sicher in derselben Stadt wie Jonas (Reflexivität). Wenn Jonas in derselben Stadt wohnt wie Oskar, dann wohnt auch Oskar in derselben Stadt wie Jonas (Symmetrie). Und wenn Oskar in derselben Stadt wohnt wie Martin, dann wohnt auch Jonas in derselben Stadt wie Martin (Transitivität).
• In dieselbe Klasse gehen. Lena geht sicher in dieselbe Klasse wie Lena (Reflexivität). Wenn Lena und Ben in dieselbe Klasse gehen, dann gehen auch Ben und Lena in dieselbe Klasse (Symmetrie). Und wenn Ben und Mia in dieselbe Klasse gehen, dann gehen auch Lena und Mia in dieselbe Klasse (Transitivität).
• (a, b) ∈ R genau dann, wenn a − b eine gerade Zahl ist; a, b sind ganze Zahlen. Reflexivität: a − a = 0, null ist eine gerade Zahl. Symmetrie: Bezeichnen wir c = a − b. Dann ist b − a = −(a − b) = −c. Ist c gerade, dann muss auch −c gerade sein. Transitivität: Bezeichnen wir p = a − b, weiter q = b − c. Wir wissen, dass p und q gerade Zahlen sind. Nun sollen wir beweisen, dass a − c eine gerade Zahl ist. In diese Gleichung setzen wir für c ein: c = b − q, also a − (b − q), das ist gleich a − b + q. Aus den Voraussetzungen wissen wir, dass a − b eine gerade Zahl ist. Addieren wir zu einer geraden Zahl eine weitere gerade Zahl q, erhalten wir wieder eine gerade Zahl.
• Gleichheit. Die Gleichheit ist eine Äquivalenz, und zwar zugleich die kleinste Äquivalenz auf einer beliebigen Menge M.

Triviale Äquivalenz

Wir haben eine nichtleere Menge M. Was ist die kleinstmögliche Äquivalenz R auf der Menge M? Die kleinstmögliche Teilmenge des kartesischen Produkts M × M ist die leere Menge ∅. Erfüllt die leere Menge die Bedingungen einer Äquivalenz?

Sicher ist sie symmetrisch, denn da die Relation R keine Elemente hat, ist die Bedingung der Symmetrie automatisch und trivial erfüllt. Ähnlich die Transitivität. Das Problem ist die Reflexivität. Die Definition sagt, dass für alle Elemente x der Menge M gilt: (x, x) ∈ R. Ist das erfüllt? Die Menge M ist nichtleer, enthält also irgendein Element, zum Beispiel q. Liegt das Paar (q, q) in der Relation R? Nein. Die Relation R ist also nicht reflexiv.

Was ist die kleinste Relation, die die Reflexivität erfüllt? Die Gleichheitsrelation. Die Relation R muss mindestens die Paare (x, x) für alle Elemente von M enthalten. Das ist genau die Identitätsrelation. Ist eine solche Relation symmetrisch? Man sieht leicht, dass das der Fall ist. Ebenso leicht sieht man, dass sie auch transitiv ist. Die kleinste Äquivalenzrelation auf der Menge M ist also die Identitätsrelation, wir bezeichnen sie mit id_M, und sie enthält die Paare (x, x) für alle x ∈ M.

Was ist die größtmögliche Äquivalenz auf der Menge M? Die größte Teilmenge ist die ganze Menge M × M. Erfüllt sie die Bedingungen einer Äquivalenz? Das ist wohl trivialerweise der Fall.

Äquivalenzklasse

Jede Äquivalenz zerlegt die Menge M in ein System disjunkter Mengen, die wir dann Äquivalenzklassen nennen.

Nehmen wir die Menge aller Wörter M und die Äquivalenz R „gleich langes Wort“. Also (a, b) ∈ R genau dann, wenn die Wörter a und b gleich lang sind. Diese Äquivalenz zerlegt die Menge der Wörter in mehrere kleinere Mengen, die immer Wörter gleicher Länge enthalten. Die einzelnen Äquivalenzklassen können wir mit Hilfe eines unteren Index unterscheiden, der zugleich die Länge der Wörter in der jeweiligen Menge angibt:

• M₁ = {a; i; o; e; …}
• M₂ = {zu; im; am; er; …}
• M₃ = {und; auf; der; den; …}
• M₄ = {Haus; Park; Wald; Baum; …}
• …

Beachte zwei Dinge: 1) Die einzelnen Mengen sind paarweise disjunkt, sie haben kein gemeinsames Element. 2) Alle Elemente jeder einzelnen Menge sind zueinander äquivalent. Alle Wörter in der Menge M₃ sind zueinander äquivalent, weil alle Wörter die Länge drei haben, also dieselbe Länge, was die Bedingung der Äquivalenz ist.

Dabei bestimmt jedes Element eindeutig seine Äquivalenzklasse. Das schreiben wir üblicherweise mit der Notation M[x], wobei x ∈ M. Würden wir M[und] schreiben, dann bestimmen wir damit eindeutig die Äquivalenzklasse, die wir schon als M₃ bezeichnet haben.

Wie finden wir eigentlich die Äquivalenzklasse, wenn wir ein x ∈ M kennen? Wir gehen alle Elemente in M durch und stellen fest, welche dieser Elemente mit dem Element x äquivalent sind. Das werden alle Elemente sein, die Teil der Äquivalenzklasse M[x] sind.

Für M[und] würden wir alle Wörter in M durchgehen und in M₃ diejenigen Wörter behalten, die die Länge drei haben.

Definition und Eigenschaften der Äquivalenzklasse

Die Äquivalenzklasse könnten wir uns so definieren. Wir haben eine Menge M und darauf eine Äquivalenz R definiert. Dann verstehen wir unter der Klasse der Zerlegung, die das Element x ∈ M enthält:

$$M[x]=\{y\in M\mid (x,y)\in R\}$$

Die Definition sagt, dass das alle y sind, die mit dem gegebenen Element x äquivalent sind. Weil die Äquivalenzrelation reflexiv ist, gelangt auf diese Weise auch das Element x selbst hinein – denn x ist mit sich selbst äquivalent.

Unter der Zerlegung einer Äquivalenz verstehen wir dann die Menge aller Äquivalenzklassen. Die Zerlegung der Menge aller Wörter wäre also die Menge {M₁; M₂; M₃; …}.

Grundlegende Eigenschaften von Äquivalenzklassen:

• (a, b) ∈ R genau dann, wenn M[a] = M[b]. Haben wir zwei Elemente a, b, die äquivalent sind, dann müssen ihre Äquivalenzklassen gleich sein.
• Umgekehrt: Gilt (a, b) ∈ R nicht, dann ist auch M[a] ≠ M[b], genauer M[a] ∩ M[b] = ∅. Haben wir zwei Elemente, die nicht äquivalent sind, dann sind ihre Klassen der Zerlegung disjunkt.
• Die Vereinigung aller Äquivalenzklassen muss die ursprüngliche Menge M ergeben: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Die vorige Schreibweise gilt nur für eine endliche Anzahl von Äquivalenzklassen, im Allgemeinen können es aber unendlich viele sein.)

Beispiele für Zerlegungen einer Äquivalenz

Erstes Beispiel, ungerade und gerade Zahlen:

Nehmen wir eine einfache Äquivalenz R, definiert auf den natürlichen Zahlen N. (a, b) ∈ R genau dann, wenn a und b beide ungerade oder a und b beide gerade sind. Beispiele für Elemente: (1, 7), (13, 9), (4, 6), (8, 136). Bestimmen wir nun die Zerlegung dieser Äquivalenz in Äquivalenzklassen.

Wir beginnen der Reihe nach. Was ist die Klasse N[1]? Wir müssen alle Zahlen finden, die mit der Zahl eins äquivalent sind. Nach der Bedingung der Äquivalenz sind das alle ungeraden Zahlen, also N[1] = {1; 3; 5; 7; 9; …}.

Was ist die Klasse N[2]? Wir finden alle Zahlen, die mit der Zwei äquivalent sind. Das sind alle geraden Zahlen: N[2] = {2; 4; 6; 8; 10; …}.

Nun N[3]. Welche Zahlen sind mit der Drei äquivalent? Alle ungeraden Zahlen. Dadurch erhalten wir aber die Menge N[1], die wir im vorletzten Absatz ausgerechnet haben. Ähnlich für N[4], dort wieder die Menge der geraden Zahlen.

Wir sehen, dass sich weiter immer nur dieselben Mengen wiederholen würden. Das sieht man auch daran, dass für jede weitere natürliche Zahl n gilt: n ∈ N[1] oder n ∈ N[2]. Andere natürliche Zahlen als ungerade und gerade haben wir nicht, diese beiden Mengen bilden also die Zerlegung der Äquivalenz.

Es ist ähnlich, als würden wir uns eine Äquivalenz auf der Menge der Menschen vorstellen: a und b sind beide Männer oder a und b sind beide Frauen. Dann bekämen wir als Zerlegung die Menge der Frauen und die Menge der Männer.

Zweites Beispiel, Betrag:

Nehmen wir die Äquivalenz R auf der Menge der ganzen Zahlen Z, die so definiert ist: (a, b) ∈ R genau dann, wenn |a| = |b|. (Die senkrechten Striche sind der Betrag.) Wieder gehen wir der Reihe nach vor:

• Z[0] = {0}. Null steht nur mit null in Relation.
• Z[1] = {−1; 1}. Die Eins steht mit der Eins und mit der Minus-Eins in Relation, weil |1| = |−1|.
• Z[2] = {−2; 2}. Die Zwei steht mit der Zwei und mit der Minus-Zwei in Relation.
• Z[3] = {−3; 3}.
• …

Es ist wohl klar, wie es weitergeht. Die ganze Zerlegung wäre also die Menge der Klassen:

$$\{\{a;-a\}\mid a\in {\mathbb{Z}}_0^{+}\}$$

(Also alle Paare a, −a, wobei a eine nichtnegative ganze Zahl ist.) Du siehst, dass es unendlich viele Klassen gibt.