Äquivalenzbeziehungen

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

Begründung

Die Äquivalenzrelation ist eine Art Verfeinerung der Gleichheitsrelation. Wir können immer entscheiden, dass zwei Elemente einer Menge gleich sind, d. h., dass a = a. Aber manchmal ist es nützlich zu sehen, ob zwei Elemente nur ähnlich, nicht unbedingt gleich sind. Oder - ob sie die gleiche wesentliche Eigenschaft haben. Zum Beispiel können zwei Bücher als ähnlich angesehen werden, wenn sie das gleiche Genre haben - oder durch Äquivalenz: zwei Bücher sind äquivalent, wenn sie das gleiche Genre haben.

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

Wenn wir die Ähnlichkeit von zwei Wörtern messen, würden wir wahrscheinlich erwarten, dass sie ähnlich sind. Es muss also für alle Wörter gelten, dass sie sich selbst ähnlich/äquivalent sind. In der relationalen Sprache: Die Äquivalenzrelation muss reflexiv sein.

Wenn also das Wort "Bach" ähnlich/äquivalent zu dem Wort "Agatha" ist, dann erwarten wir sicherlich, dass das Wort "Agatha" äquivalent zu dem Wort "Bach" ist. Mit anderen Worten, die Reihenfolge spielt keine Rolle. In der relationalen Sprache: Die Äquivalenzbeziehung muss symmetrisch sein.

Wenn schließlich das Wort "Tod" dem Wort "Vogel" ähnlich/äquivalent ist und das Wort "Vogel" dem Wort "Fuß" entspricht, dann erwarten wir, dass die Wortpaare "Tod" und "Fuß" ebenfalls äquivalent sind. Die Äquivalenzrelation muss also auch transitiv sein.

Mehr erwarten wir von der Äquivalenz nicht.

Beispiele

Weitere Beispiele für Äquivalenzen:

• In der gleichen Stadt wohnen. Jirka wohnt sicherlich in der gleichen Stadt wie Jirka (Reflexivität). Wenn Jirka in der gleichen Stadt wie Ondra wohnt, dann wohnt Ondra in der gleichen Stadt wie Jirka (Symmetrie). Und wenn Ondra in der gleichen Stadt wie Martin lebt, dann lebt Jirka in der gleichen Stadt wie Martin (Transitivität).
• Lieder mit demselben Autor. Das Lied "The Furious Monologue of the Son of the Hatch" hat sicherlich denselben Autor wie das Lied "The Furious Monologue of the Son of the Hatch" (Reflexivität). Wenn die Lieder "The Furious Monologue of the Son of the Hatch" und "War on the Rags" denselben Autor haben, dann haben "War on the Rags" und "The Furious Monologue of the Son of the Hatch" denselben Autor (Symmetrie). Und wenn "Der Krieg gegen die Stäbe" und "Die Suche nach der Wahrheit des Schmutzes" denselben Autor haben, dann haben "Der wütende Monolog des Sohnes der Luke" und "Die Suche nach der Wahrheit des Schmutzes" denselben Autor (Transitivität).
• [a, b] ∈ R Gerade wenn a − b eine gerade Zahl ist; a, b sind ganze Zahlen. Reflexivität: a − a = 0, Null ist eine gerade Zahl. Symmetrie: Bezeichne c = a − b. Dann b − a = −(a − b) = −c. Wenn c gerade ist, dann muss −c gerade sein. Transitivität: bezeichne p = a − b, dann q = b − c. Wir wissen, dass p und q beide gerade Zahlen sind. Nun müssen wir beweisen, dass a − c eine gerade Zahl ist. Wir setzen c = b − q: a−(b − q), was a − b + q entspricht, in diese Gleichung nach c ein. Aus den Annahmen wissen wir, dass a − b eine gerade Zahl ist. Wenn wir zu der geraden Zahl q eine weitere gerade Zahl hinzufügen, erhalten wir wieder eine gerade Zahl.
• Gleichheit. Gleichheit ist Äquivalenz, sie ist auch die kleinste Äquivalenz auf einer beliebigen Menge M.

Triviale Äquivalenz

Wir haben eine nicht leere Menge M. Was ist die kleinstmögliche Äquivalenz von R mit der Menge M? Die kleinstmögliche Teilmenge des kartesischen Produkts M × M ist die leere Menge ∅. Erfüllt die leere Menge die Äquivalenzbedingungen?

Sie ist sicherlich symmetrisch, da die Sitzung R keine Elemente hat, ist die Symmetriebedingung automatisch und trivialerweise erfüllt. Ähnliches gilt für die Transitivität. Das Problem liegt in der Reflexivität. Die Definition besagt, dass für alle Elemente x der Menge M gilt, dass [x, x] ∈ R wahr ist. Ist dies erfüllt? Die Menge M ist nicht leer, sie enthält also einige Elemente, z. B. q. Ist das Paar [q, q] in der Sitzung R? Nein, ist es nicht. Die Sitzung R ist also nicht reflexiv.

Was ist die kleinste Lerneinheit, die reflexiv ist? Eine Gleichheits-Sitzung. Eine Sitzung R muss mindestens das Paar [x, x] für alle Elemente von M enthalten. Das ist eine reine Identitätssitzung. Ist eine solche Sitzung symmetrisch? Es ist leicht zu sehen, dass sie es ist. Ebenso ist leicht zu erkennen, dass sie transitiv ist. Die kleinste Äquivalenzrelation auf der Menge M ist also eine Identitätsrelation, bezeichnet als id_M, und enthält die Paare [x, x] für alle x ∈ M.

Was ist die größte mögliche Äquivalenzbeziehung in der Menge M? Die größte Teilmenge ist die gesamte Menge M × M. Erfüllt sie die Äquivalenzbedingungen? Es ist wahrscheinlich trivial zu sehen, dass sie es tut.

Die Äquivalenzklasse

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

Betrachten wir die Menge aller Wörter M und die Äquivalenz R mit der gleichen Wortlänge. Das heißt, [a, b] ∈ R nur dann, wenn die Wörter a und b die gleiche Länge haben. Diese Äquivalenz teilt die Menge der Wörter in mehrere kleinere Mengen auf, die immer Wörter mit derselben Länge enthalten. Wir können die verschiedenen Äquivalenzklassen unterscheiden, indem wir einen tiefgestellten Index verwenden, der auch die Länge der Wörter in der Menge unterscheidet:

• M₁ = {a, i, o, e, …}
• M₂ = {ve, do, se, my, mi, …}
• M₃ = {ale, bez, ten, tam, …}
• M₄ = {smrt, park, lest, niva, …}
• ...

Beachten Sie zwei Dinge: 1) Die einzelnen Mengen sind disjunkt, d. h. sie haben kein gemeinsames Element. 2) Alle Elemente in jeder einzelnen Menge sind äquivalent zueinander. Alle Wörter in der Menge M₃ sind äquivalent zueinander, weil alle Wörter die Länge drei haben, also gleich lang sind, was die Äquivalenzbedingung ist.

Auf diese Weise definiert jedes Element eindeutig seine Äquivalenzklasse. Üblicherweise schreiben wir dies mit M[x], wobei x ∈ M. Würden wir M[ale] schreiben, würden wir die Äquivalenzklasse, die wir bereits als M₃ markiert haben, eindeutig definieren.

Wie finden wir nun die Äquivalenzklasse, wenn wir x ∈ M kennen? Wir gehen alle Elemente in M durch und finden heraus, welche dieser Elemente äquivalent zu dem Element x sind. Dies sind dann alle Elemente, die zur Äquivalenzklasse M[x] gehören.

Für M[ale] würden wir alle Wörter in M durchgehen und die Wörter mit der Länge drei in M₃ speichern.

Äquivalenzklassendefinition und Eigenschaften

Wir könnten eine Äquivalenzklasse wie folgt definieren. Betrachten wir die Menge M und die darauf definierte Äquivalenz R. Dann verstehen wir die Zersetzungsklasse, die das Element x ∈ M enthält:

$$M[x] = {y \in M; [x, y] \in R}$$

Die Definition besagt, dass dies alle y sind, die mit dem angegebenen Element x äquivalent sind. Da die Äquivalenzrelation reflexiv ist, kommt das Element x auf diesem Weg dorthin - denn x ist äquivalent zu sich selbst.

Die Äquivalenzzerlegung ist dann die Menge aller Äquivalenzklassen. Die Zerlegung der Menge aller Wörter wäre also die Menge von {M₁, M₂, M₃, …}.

Grundlegende Eigenschaften von Äquivalenzklassen:

• [a, b] ∈ R Gerade wenn M[a] = M[b]. zwei Elemente von a, b äquivalent sind, dann müssen ihre Äquivalenzklassen gleich sein.
• Umgekehrt, wenn [a, b] ∈ M, dann auch M[a] ≠ M[b], genauer M[a] ∩ M[b] = ∅. Wenn wir zwei Elemente haben, die nicht äquivalent sind, dann sind ihre Zerlegungsklassen disjunkt.
• Die Vereinigung aller Äquivalenzklassen muss die ursprüngliche Menge M ergeben: M₁ ∪ M₂ ∪ … ∪ M_n = M(Die obige Schreibweise gilt nur für eine endliche Anzahl von Äquivalenzklassen, aber im Allgemeinen kann es unendlich viele geben).

Beispiele für Äquivalenzzerlegungen

Erstes Beispiel: Ungerade und gerade Zahlen:

Betrachten wir die einfache Äquivalenz R, die für die natürlichen Zahlen N. [a, b] ∈ R definiert ist, 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 sequentiell. Was wird die Klasse N[1] sein, die gleich ist? Wir müssen alle Zahlen finden, die mit einer gleich sind. Gemäß der Äquivalenzbedingung sind dies alles ungerade Zahlen, also N[1] = {1, 3, 5, 7, 9, …}.

Welchem Wert entspricht die Klasse N[2]? Wir finden alle Zahlen, die gleich zwei sind. Dies sind alles gerade Zahlen: N[2] = {2, 4, 6, 8, 10, …}.

Nun N[3]. Welche Zahlen sind äquivalent zu drei? Alles ungerade Zahlen. Aber damit haben wir die Menge N[1], die wir im vorigen Abschnitt berechnet haben. Ähnlich verhält es sich mit N[4], auch hier die Menge der geraden Zahlen.

Wir können sehen, dass sich von hier an die gleichen Mengen immer wiederholen würden. Das zeigt sich auch daran, dass für jede andere natürliche Zahl n, die wir nehmen, bereits gilt, dass n ∈ N[1] oder n ∈ N[2]. Es gibt keine anderen natürlichen Zahlen als die ungeraden und geraden Zahlen, so dass diese beiden Mengen eine Äquivalenzzerlegung bilden.

Das ist ähnlich, wie wenn man sich vorstellt, dass die Menge der Personen a i b ein Mann ist oder a i b eine Frau ist. Dann würden wir eine Menge von Frauen und eine Menge von Männern als Zerlegung erhalten.

Zweites Beispiel, absoluter Wert:

Nehmen wir eine Äquivalenz R auf der Menge der ganzen Zahlen Z, die wie folgt definiert ist: [a, b] ∈ R nur dann, wenn |a| = |b|. (Die vertikalen Linien sind der absolute Wert.) Wieder gehen wir der Reihe nach vor:

• Z[0] = {0}. Null steht nur mit Null in einer Beziehung.
• Z[1] = {−1, 1}. Eins ist in einer Beziehung mit Eins und minus Eins, weil |1| = |−1|.
• Z[2] = {−2, 2}. Zwei steht in einer Beziehung zu zwei und zu minus zwei.
• Z[3] = {−3, 3}.
• ...

Ich denke, es ist klar, wie das ablaufen wird. Die gesamte Dekomposition wäre also eine Menge von Klassen:

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

(Das heißt, alle Paare von a, −a, wobei a eine nichtnegative ganze Zahl ist.) Du kannst sehen, dass es unendlich viele Klassen gibt.