6.5 Äquivalenzrelationen und Äquivalenzklassen
Was ist eine Äquivalenzrelation?
Zwei verschiedene Objekte können hinsichtlich eines bestimmten Merkmals übereinstimmen: beim Geburtsjahr, beim Betrag oder beim Rest einer Division. Eine Äquivalenzrelation beschreibt eine solche Gleichwertigkeit.
Definition 6.14 (Äquivalenzrelation). Eine Relation \(T\subseteq M\times M\) heißt Äquivalenzrelation, wenn sie reflexiv, symmetrisch und transitiv ist.
Statt \((x,y)\in T\) schreiben wir dann auch \(x\sim y\) und sagen: „\(x\) ist äquivalent zu \(y\)“.
Die drei Bedingungen entsprechen grundlegenden Regeln einer Gleichwertigkeit.
Die drei Eigenschaften lassen sich wie folgt deuten:
- Jedes Element ist zu sich selbst äquivalent.
- Äquivalenz gilt in beiden Richtungen.
- Äquivalenz überträgt sich über ein Zwischenelement.
Klassen und Vertreter
Zu einem Element sammeln wir alle Elemente, die nach der gewählten Beziehung gleichwertig sind. Dadurch entsteht eine ganze Teilmenge von \(M\).
Definition 6.15 (Äquivalenzklasse und Quotientenmenge). Sei \(T\) eine Äquivalenzrelation auf \(M\). Die Äquivalenzklasse von \(x\in M\) ist \[ [x]_T=\{y\in M\mid (x,y)\in T\}. \] Jedes Element dieser Klasse heißt Vertreter der Klasse. Die Menge aller Äquivalenzklassen heißt Quotientenmenge: \[ M\mathbin{/}T=\{[x]_T\mid x\in M\}. \] Ist die Relation klar, schreiben wir kurz \([x]\).
Die Elemente der Quotientenmenge sind Mengen, keine einzelnen Vertreter. Aus \(x\neq y\) folgt daher nicht \([x]\neq[y]\). Die Schreibweise \(M\mathbin{/}T\) bezeichnet eine Klassenbildung, keinen Zahlenbruch. Ist klar welche Äquivalenzrelation gemeint ist, schreibt man für die Quotientenmenge auch \(T\mathbin{/}\sim\).
Auch der Betrag kann das Merkmal sein, nach dem Elemente zusammengefasst werden.
Beispiel: Klassen nach dem Quadrat
Auf \(M=\{-3,-2,0,2,3\}\) sei \(x\sim y\iff x^2=y^2\). Beweisen Sie, dass eine Äquivalenzrelation vorliegt und bestimmen Sie die Quotientenmenge.
Klassen sind gleich oder disjunkt
Zwei Äquivalenzklassen können sich nicht nur teilweise überlappen. Schon ein gemeinsames Element erzwingt, dass sie übereinstimmen.
Satz 6.4 (Zerlegung in Äquivalenzklassen). Für eine Äquivalenzrelation auf \(M\) gilt:
- \(x\in[x]\) für jedes \(x\in M\).
- \(x\sim y\iff[x]=[y]\).
- Verschiedene Äquivalenzklassen sind disjunkt
- Die Vereinigung aller Äquivalenzklassen ergibt \(M\).
Die Äquivalenzklassen bilden eine Partition von \(M\): eine Zerlegung in paarweise disjunkte, nichtleere Teilmengen.
Diese vier Relationseigenschaften erklären genau, warum diese Zerlegung funktioniert.
Beweis
Beweis.
- Reflexivität liefert \(x\in[x]\).
- Ist \(x\sim y\) und \(z\in[x]\), so folgt aus \(y\sim x\) und \(x\sim z\) die Beziehung \(y\sim z\). Somit ist \([x]\subseteq[y]\); vertauscht man \(x,y\), erhält man Gleichheit. Gilt umgekehrt \([x]=[y]\), so liegt \(y\in[y]=[x]\), also \(x\sim y\).
- Liegt \(z\) in \([x]\cap[y]\), so folgt aus \(x\sim z\) und \(z\sim y\), dass \(x\sim y\) und damit \([x]=[y]\). Verschiedene Klassen sind daher disjunkt.
- Da jedes \(x\in M\) in seiner eigenen Klasse liegt, überdecken die Klassen ganz \(M\).
\(\square\)
Aus einer Zerlegung eine Relation gewinnen
Die Konstruktion lässt sich umkehren: Zuerst werden Gruppen festgelegt; dann erklären wir Elemente derselben Gruppe für äquivalent.
Satz 6.5 (Äquivalenzrelation einer Partition). Sei \((M_i)_{i\in I}\) eine Familie nichtleerer, paarweise disjunkter Teilmengen mit \(\bigcup_{i\in I}M_i=M\). Dann ist \[ x\sim y\iff\exists i\in I:\ x\in M_i\land y\in M_i \] eine Äquivalenzrelation. Ihre Äquivalenzklassen sind genau die Mengen \(M_i\).
Entscheidend für die Transitivität ist, dass kein Element zwei verschiedenen Teilen der Partition angehören kann.
Beweis
Beweis. Jedes Element gehört zu einem Teil \(M_i\), also ist die Relation reflexiv. Die Zugehörigkeit zum selben Teil ist symmetrisch. Sind \(x,y\in M_i\) und \(y,z\in M_j\), dann liegt \(y\) im Schnitt. Wegen der paarweisen Disjunktheit muss \(i=j\) gelten. Somit liegen \(x,z\) im selben Teil, und die Relation ist transitiv. Für \(x\in M_i\) ist nach Definition \([x]=M_i\). \(\square\)
Restklassen als wichtiges Beispiel
Die Parität ist der Spezialfall einer allgemeinen Beziehung: Wir vergleichen Reste bei Division durch eine feste positive ganze Zahl.
Definition 6.16 (Kongruenz modulo m). Sei \(m\in\mathbb N\) mit \(m\geq1\). Für \(x,y\in\mathbb Z\) heißt \[ x\equiv y\pmod m\iff m\mid(x-y), \] dass \(x\) und \(y\) kongruent modulo \(m\) sind. Dabei bedeutet \(m\mid(x-y)\), dass \(x-y=km\) für ein \(k\in\mathbb Z\) gilt.
Das Vorzeichen eines Vielfachen und die Summe zweier Vielfacher ändern nichts an der Teilbarkeit durch \(m\).
Satz 6.6 (Kongruenz ist eine Äquivalenzrelation). Kongruenz modulo \(m\) ist eine Äquivalenzrelation auf \(\mathbb Z\). Ihre genau \(m\) Klassen sind \[ [r]=\{r+km\mid k\in\mathbb Z\},\qquad r=0,\ldots,m-1. \] Die Quotientenmenge ist \(\{[0],[1],\ldots,[m-1]\}\).
Wir zeigen zuerst die Äquivalenzeigenschaften, bestimmen dann die Klassen und begründen schließlich ihre Anzahl.
Beweis
Beweis. 1. Kongruenz modulo \(m\) ist eine Äquivalenzrelation.
- Reflexivität: Für jedes \(x\in\mathbb Z\) gilt \(x-x=0=0\cdot m\). Also ist \(x\equiv x\pmod m\).
- Symmetrie: Aus \(x\equiv y\pmod m\) folgt \(x-y=km\) für ein \(k\in\mathbb Z\). Dann gilt \(y-x=(-k)m\), also \(y\equiv x\pmod m\).
- Transitivität: Seien \(x\equiv y\pmod m\) und \(y\equiv z\pmod m\). Dann gibt es \(k,\ell\in\mathbb Z\) mit \(x-y=km\) und \(y-z=\ell m\). Daher ist \[ x-z=(x-y)+(y-z)=(k+\ell)m, \] also \(x\equiv z\pmod m\).
2. Die Klasse von \(r\) ist \([r]=\{r+km\mid k\in\mathbb Z\}\).
Nach der Definition einer Äquivalenzklasse gilt \[ \begin{aligned} x\in[r] &\iff r\equiv x\pmod m\\ &\iff m\mid(r-x)\\ &\iff x=r+km\text{ für ein }k\in\mathbb Z. \end{aligned} \] Damit ist die angegebene Darstellung der Klassen bewiesen.
3. Es gibt genau \(m\) Klassen; die Quotientenmenge ist \(\{[0],\ldots,[m-1]\}\).
- Diese Klassen erfassen alle ganzen Zahlen: Die Division mit Rest liefert für jedes \(x\in\mathbb Z\) eine Darstellung \(x=qm+r\) mit \(q\in\mathbb Z\) und \(0\leq r<m\). Nach Teil 2 liegt \(x\) daher in \([r]\).
- Die aufgeführten Klassen sind verschieden: Gilt \([r]=[s]\) für \(r,s\in\{0,\ldots,m-1\}\), so ist \(r\equiv s\pmod m\). Also ist \(r-s\) ein Vielfaches von \(m\). Wegen \(|r-s|<m\) ist nur \(r-s=0\) möglich, also \(r=s\).
Somit sind \([0],[1],\ldots,[m-1]\) genau die \(m\) verschiedenen Äquivalenzklassen und bilden die Quotientenmenge. \(\square\)
Bei negativen Zahlen hilft die Darstellung als Rest plus ganzzahliges Vielfaches.
Beispiel: Rest modulo fünf
Zu welcher Klasse gehören \(-8\) und \(17\) modulo \(5\)?
Geraden nach ihrer Richtung zusammenfassen
Nicht nur Zahlen lassen sich in Klassen einteilen. Bei Geraden kann die Richtung das gemeinsame Merkmal sein.
Beispiel: Parallelität einschließlich identischer Geraden
Auf der Menge aller Geraden einer Ebene erklären wir \(g\sim h\), wenn \(g\) und \(h\) dieselbe Richtung haben. Identische Geraden gelten hier als parallel.
Diese Beziehung ist reflexiv, symmetrisch und transitiv. \([g]\) besteht aus allen Geraden derselben Richtung wie \(g\). Die Quotientenmenge beschreibt die unorientierten Geradenrichtungen, einschließlich der vertikalen Richtung.
Würde „parallel“ nur verschiedene Geraden ohne Schnittpunkt bezeichnen, fehlte die Reflexivität. Eine gewöhnliche reelle Steigung erfasst zudem keine vertikalen Geraden; die Beschreibung durch Richtungen ist vollständiger.
Zusammenfassung
- Äquivalenzrelationen sind reflexiv, symmetrisch und transitiv.
- Äquivalenzklassen sind gleich oder disjunkt und überdecken die Grundmenge.
- Eine Quotientenmenge enthält Klassen; Vertreter sind einzelne Elemente dieser Klassen.
- Partitionen und Äquivalenzrelationen bestimmen einander.
- Kongruenz modulo \(m\geq1\) zerlegt \(\mathbb Z\) in genau \(m\) Restklassen.