Äquivalenzrelationen
Zu den wichtigsten Typen relationaler Strukturen gehören die Äquivalenzrelationen. Sie erfüllen die drei grundlegenden Eigenschaften der Gleichheit:
Definition (Äquivalenz, äquivalent)
Sei A eine Menge. Eine Relation ≡ auf A heißt eine Äquivalenzrelation oder kurz Äquivalenz auf A, falls gilt:
| (E1) | ∀a ∈ A a ≡ a(Reflexivität) |
| (E2) | ∀a, b ∈ A (a ≡ b → b ≡ a)(Symmetrie) |
| (E3) | ∀a, b, c ∈ A (a ≡ b ∧ b ≡ c → a ≡ c)(Transitivität) |
Gilt a ≡ b für a, b ∈ A, so sagen wir, dass a und b äquivalent bzgl. ≡ sind.
Das geordnete Paar (A, ≡ ) nennen wir auch eine Äquivalenzstruktur.
Für eine Äquivalenz wählen wir bevorzugt Symbole wie ≡ , ∼, ≃, …, die an das Gleichheitszeichen = erinnern. Das Gleichheitszeichen verwenden wir weiterhin ausschließlich für die Identität.
Äquivalenzen beschreiben die Ähnlichkeit von Objekten unteg einem bestimmten Gesichtspunkt. Wir betrachten einige Beispiele.
Beispiele
(1) | Sei A = { 1, 2, 3, 4 } und ≡ = { (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (3, 4), (4, 3) }. Dann ist ≡ eine Äquivalenz auf A. Wie für jede Äquivalenz ist jedes Element von A zu sich selbst äquivalent. Daneben sind 1 und 2 äquivalent und weiter 3 und 4 äquivalent: 1 ≡ 2 und 3 ≡ 4. |
(2) | Ist m ≥ 1, so ist die Kongruenz ≡ m modulo m eine Äquivalenz auf ℤ. Für alle a, b ∈ ℤ gilt a ≡ m b genau dann, wenn m ein Teiler von a − b ist. Formal gilt ≡ m = { (a, b) ∈ ℤ2 | es gibt ein k ∈ ℤ mit k m = a − b }. |
(3) | Ist G = (E, K) ein Graph, so ist die Erreichbarkeit ∼G eine Äquivalenz auf der Menge E der Ecken des Graphen. Für alle Ecken a, b ∈ E gilt a ∼G b, falls es einen Kantenzug von a nach b gibt. |
(4) | Ist E eine endliche nichtleere Menge, so ist die Isomorphie ≅ eine Äquivalenz auf der Menge 𝒢 = { G | G ist ein Graph mit der Eckenmenge E }. Für alle Graphen G1 = (E, K1), G2 = (E, K2) gilt G1 ≅ G2, falls es einen Isomorphismus zwischen G1 und G2 gibt. |
Eine Äquivalenz teilt die Grundmenge in Bereiche äquivalenter Elemente (Länder) auf. Zur Beschreibung dieser Aufteilung führen wir einige Begriffe ein.
Definition (Äquivalenzklasse, Faktorisierung, Repräsentantensystem)
Sei ≡ eine Äquivalenz auf A. Dann setzen wir:
| a/≡ | = { b ∈ A | a ≡ b } für alle a ∈ A,(Äquivalenzklasse von a, a modulo ≡ ) |
| A/≡ | = { a/≡ | a ∈ A }. (Faktorisierung von A, A modulo ≡ ) |
Jedes Element von a/≡ nennen wir einen Repräsentanten der Äquivalenzklasse a/≡ . Eine Teilmenge B von A heißt ein (vollständiges) Repräsentantensystem für ≡ , falls es für alle a ∈ A genau ein b ∈ B mit a ≡ b gibt.
Die Menge A zerfällt in Äquivalenzklassen (waagrechte Streifen). Die hervorgehobenen Elemente der Klassen bilden ein Repräsentantensystem.
A/≡ ist die Menge der Äquivalenzklassen (im Diagramm besitzt sie 6 Elemente)
Dass wir von Äquivalenzklassen und nicht von Äquivalenzmengen sprechen hat traditionelle Gründe.
Klammernotation
Anstelle der manchmal etwas schwerfälligen Notation a/≡ schreiben wir auch [ a ]≡ oder kurz [ a ].
Ein Element b ∈ A ist nach Definition genau dann ein Repräsentant der Klasse [ a ], wenn a ≡ b. Ein Repräsentantensystem erhalten wir, wenn wir aus jeder Klasse genau ein Element herauspicken. Anschaulich: Sind A die Schüler einer Schule, so setzen wir a ≡ b, falls die Schüler a und b in derselben Klasse sind. Für jeden Schüler a der Schule bezeichnet [ a ] seine Schulklasse. Weiter ist A/≡ die Menge aller Schulklassen. Jeder Schüler ist ein Repräsentant seiner Klasse. Ein Repräsentantensystem können wir uns als Klassensprecherversammlung vorstellen: Jede Klasse schickt ihren Klassensprecher. Prinzipiell können wir beliebige Repräsentanten auswählen, in vielen Fällen steht aber ein wichtiger oder besonders natürlicher Repräsentant zur Verfügung (in unserem Beispiel der Klassensprecher). In der Mathematik werden diese ausgezeichneten Elemente traditionell als kanonische Repräsentanten bezeichnet. „Kanonisch“ bedeutet hier „sich aufdrängend, erste Wahl, besonders einfach, allgemeinen Prinzipien folgend, maßgeblich“.
Bei der Mengenkomprehension
A/≡ = { a/≡ | a ∈ A }
werden in der Regel viele Klassen mehrfach aufgesammelt. Dies stört nicht, da es in einer Menge auf Wiederholungen nicht ankommt. Mit Hilfe eines vollständigen Repräsentantensystems B lassen sich Wiederholungen vermeiden. Es gilt
A/≡ = { [ a ] | a ∈ A } = { [ a ] | a ∈ B }.
Die Menge A kann unendlich sein, die Menge B aber endlich. Hat die Menge B genau n Elemente, so auch A/≡ .
Beispiele
(1) | Sei A = { 1, 2, 3, 4 } und ≡ = { (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (3, 4), (4, 3) }. Dann gilt [ 1 ] = [ 2 ] = { 1, 2 } und [ 3 ] = [ 4 ] = { 3, 4 }. Weiter ist A/≡ = { [ a ] | a ∈ A } = { [ 1 ], [ 2 ], [ 3 ], [ 4 ] } = { { 1, 2 }, { 3, 4 } }. Die Mengen { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 } sind alle möglichen Repräsentantensysteme. Kanonische Repräsentanten drängen sich nicht auf, allenfalls würden wir das System { 1, 3 } wegen seiner kleinstmöglichen Repräsentanten bevorzugen. Es gilt A/≡ = { [ 1 ], [ 3 ] } = { [ 1 ], [ 4 ] } = { [ 2 ], [ 3 ] } = { [ 2 ], [ 4 ] }. |
(2) | Seien m ≥ 1 und ≡ m die Kongruenz modulo m. Dann gilt für alle a ∈ ℤ: [ a ] = { …, a − 2m, a − m, a, a + m, a + 2m, … } = { a + dm | d ∈ ℤ } Die Menge { 0, …, m − 1 } gilt als das kanonische Repräsentantensystem von ≡ m. Allgemein ist jedes vollständige Restsystem geeignet. Für m = 5 sind zum Beispiel { 0, 1, 2, 3, 4 }, { − 2, − 1, 0, 1, 2 }, { 5, 11, 17, 23, 29 } vollständige Repräsentantensysteme. Es gilt ℤ/≡ 5 = { [ a ] | a ∈ ℤ } = { [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ] } = { [ − 2 ], [ −1 ], [ 0 ], [ 1 ], [ 2 ] } = { [ 5 ], [ 11 ], [ 17 ], [ 23 ], [ 29 ] }. |
(3) | Sei G = (E, K) ein Graph, und sei ∼ die Erreichbarkeitsrelation auf G. Dann gilt für alle a ∈ E [ a ] = a/∼ = { b ∈ E | b ist erreichbar von a in G }, d. h. [ a ] ist die Zusammenhangskomponente der Ecke a. Die Faktorisierung E/∼ ist die Menge der Zusammenhangskomponenten des Graphen. G ist genau dann zusammenhängend, wenn E/∼ = { E }. Ein Repräsentantensystem wählt aus jeder Komponente des Graphen genau eine Ecke aus. Ist G ein Wald, so liefert die Auszeichnung einer Wurzel für jeden Baum von G ein Repräsentantensystem. |
(4) | Sei E eine endliche nichtleere Menge, und sei 𝒢 = { G | G ist ein Graph mit der Eckenmenge E }. Dann gilt für die Äquivalenz ≅ der Isomorphie auf 𝒢: [ G ] = { G′ ∈ 𝒢 | G ≅ G′ } für alle G ∈ 𝒢, 𝒢/≅ = { [ G ] | G ∈ 𝒢 }. Eine Äquivalenzklasse [ G ] nennen wir auch eine Isomorphieklasse. Isomorphieklassen sind auch für kleine Eckenmengen in der Regel nur schwer zu bestimmen. Gleiches gilt für Repräsentantensysteme (vgl. hierzu die Diskussion im Abschnitt über Graphentheorie). Solche Systeme stellen eine Übersicht aller Graphen mit der Eckenmenge E „bis auf Isomorphie“ dar. |
Bemerkung
Eine Äquivalenzklasse ist stets eine Menge und die Faktorisierung stets ein Mengensystem, also eine Menge von Mengen. Ist ein Element a ∈ A nur zu sich selbst äquivalent, so gilt [ a ] = { a } und nicht etwa [ a ] = a. Sind wie im dritten Beispiel eines zusammenhängenden Graphen alle Elemente zueinander äquivalent, so gilt A/≡ = { A } und nicht etwa A/≡ = A.
Die Kongruenz modulo m wird uns noch in vielen Beispielen begegnen. Wir führen deswegen noch einige Sprechweisen und Notationen ein.
Definition (Restklassen, ℤm)
Sei m ≥ 1. Eine Äquivalenzklasse [ a ] = { a + dm | d ∈ ℤ } der Kongruenz modulo m nennen wir auch eine Restklasse modulo m. Weiter setzen wir
ℤm = ℤ/≡ m = { [ 0 ], … [ m − 1 ] }.
Ein vollständiges Repräsentantensystem von ≡ m nennen wir auch ein (vollständiges) Restsystem modulo m.
Die Konstruktion lässt sich zum Beispiel wie folgt visualisieren:
Die Kongruenz modulo 7 unterteilt ℤ in 7 unendliche Äquivalenzklassen (waagrechte Streifen). Die Menge ℤ7 ist die Menge dieser Klassen und besitzt genau 7 Elemente. Ein Repräsentantensystem erhalten wir, indem wir in jeder Zeile genau ein Element auszeichnen (grüne Kreise). Die kanonische Wahl ist 0, …, 6 (mittlere Spalte).