Äquivalenzrelationen - Mathepedia (2024)

Unter der Äquivalenzklasse oder Restklasse $x|R$x∣R eines Elements $x$x verstehen wir alle $y\in A$y∈A mit $xRy$xRy. In Mengenschreibweise:

Dieses $x$x wird auch der Repräsentant der Äquivalenzklasse genannt.

Die Menge aller Äquivalenzklassen $A|R$A∣R heißt das Restesystem von $R$R nach $A$A.

Bemerkung

Satz 5410X

Zwei Äquivalenzklassen $x|R$x∣R und $y|R$y∣R sind genau dann gleich, wenn $xRy$xRy, also ihre Repräsentanten in Relation zueinander stehen:

Beweis

Sei $x|R=y|R$x∣R=y∣R, dann ist wegen der Reflexivität von $R$R: $x\in x|R$x∈x∣R und $x\in y|R$x∈y∣R damit gilt aber $xRy$xRy.

Wenn andererseits $xRy$xRy und ein beliebiges $z\in x|R$z∈x∣R, dann ist $xRz$xRz und wegen der Symmetrie auch $zRx$zRx und wegen der Transitivität $zRy$zRy und damit ist $z\in y|R$z∈y∣R. Damit haben wir $x|R\subseteq y|R$x∣R⊆y∣R gezeigt. Die Inklusion $y|R\subseteq x|R$y∣R⊆x∣R zeigt man analog. $\qed$□

Satz NZ38 (Äquivalenzklassen als Zerlegung)

Sei $R$R eine Äquivalenzrelation in $A$A. Dann gelten für das Restesystem $A|R$A∣R folgende Eigenschaften

1. Keine Äquivalenzklasse ist leer: $\forall X\in A|R: X\neq \emptyset$∀X∈A∣R:X=/​∅
2. Die Vereinigung aller Äquivalenzklassen ist die Menge $A$A selbst: $\bigcup\limits (A|R) = A$⋃(A∣R)=A
3. Je zwei verschiedene Äquivalenzklassen sind disjunkt: $X,Y\in A|R \and X\neq Y \implies X\cap Y=\emptyset$X,Y∈A∣R∧X=/​Y⟹X∩Y=∅

Ein Teilmengensystem mit diesen Eigenschaften nennt man auch eine Zerlegung oder Partition.

Beweis

Die Eigenschaften (i) und (ii) folgen unmittelbar aus der Reflexivität der Äquivalenzrelationen.

Für (iii) zeigen wir: Sind $x|R$x∣R und $y|R$y∣R zwei Äquivalenzklassen und haben sie ein Element gemeinsam, dann stimmen sie überein. Sei $z\in x|R$z∈x∣R und $z\in y|R$z∈y∣R, dann gilt $xRz$xRz und $yRz$yRz, wegen der Transitivität auch $xRy$xRy und wegen dem oben gezeigten also $x|R=y|R$x∣R=y∣R. $\qed$□

Jede Äquivalenzrelation $R$R in $A$A erzeugt eine Zerlegung der Menge $A$A. Es gilt sogar die Umkehrung. Das Ergebnis fassen wir in folgendem Satz zusammen.

Satz YP15 (Hauptsatz über Äquivalenzrelationen)

Sei $A$A eine Menge und $R$R eine Äquivalenzrelation in $A$A, dann erzeugt $R$R eine Zerlegung der Menge $A$A. Die Mengen dieser Zerlegung sind gerade die Äquivalenzklassen.

Wenn andererseits eine Zerlegung $\sb Z$Z einer Menge $A$A gegeben ist, können wir in natürlicher Weise eine Äquivalenzrelation $R_{\sb Z}$RZ​ definieren, so dass diese Zerlegung $\sb Z$Z genau aus den Restklassen $A|R$A∣R besteht.

Beweis

Den ersten Teil des Satzes haben wir schon beweisen (Satz NZ38).

Wenn $R_{\sb Z}$RZ​ eine Zerlegung von $A$A ist, definieren wir $xR_{\sb Z}y:\iff \exists Z\in \sb Z: x\in Z\and y\in Z$xRZ​y:⟺∃Z∈Z:x∈Z∧y∈Z. Zwei Elemente stehen also genau dann in Relation genau dann, wenn es eine Menge aus $\sb Z$Z gibt, zu der sie gemeinsam gehören. Wir merken an, dass dieses $Z$Z aus der Definition eindeutig bestimmt ist, da ja ${\sb Z}$Z nur aus disjunkten nicht leeren Mengen besteht, die $A$A überdecken.

Auf Grund der Definition ist klar, dass wenn $R_{\sb Z}$RZ​ eine Äquivalenzrelation ist, dann stimmen die Äquivalenzklassen mit den Mengen aus $\sb Z$Z überein.

Es bleibt zu zeigen, dass $R_{\sb Z}$RZ​ tatsächlich eine Äquivalenzrelation ist. $R_{\sb Z}$RZ​ ist reflexiv, da jedes $x\in A$x∈A auch in einem $Z\in \sb Z$Z∈Z liegen muss. Wenn $xR_{\sb Z}y$xRZ​y dann gibt es ein $Z\in \sb Z$Z∈Z mit $x,y\in Z$x,y∈Z also gilt auch $yR_{\sb Z}x$yRZ​x, womit $R_{\sb Z}$RZ​ symmetrisch ist.

Wenn $xR_{\sb Z}y$xRZ​y gibt es ein $Z_1$Z1​ mit $x,y\in Z_1$x,y∈Z1​. Gilt auch $yR_{\sb Z}z$yRZ​z, dann muss es ein $Z_2$Z2​ geben, so dass $y,z\in Z_2$y,z∈Z2​. $Z_1$Z1​ und $Z_2$Z2​ enthalten ein gemeinsames Element $y$y, daher muss wegen der Zerlegungseigenschaft $Z_1=Z_2$Z1​=Z2​ gelten. Also ist auch $xR_{\sb Z}z$xRZ​z, womit die Transitivität gezeigt ist. $\qed$□
Damit sind Zerlegungen und Äquivalenzrelationen mathematisch gesehen identische Objekte. Sie beschreiben eine Sachverhalt lediglich mit unterschiedlichen Mitteln: einerseits als Teilmengensystem und andererseits als Äquivalenzrelation, wobei bei jeder Beschreibung spezielle Eigenschaften gelten müssen.

Beispiel (Kongruenzen)

Für $a,b\in\dom Z$a,b∈Z und $n\in \dom{N^+}$n∈N+ definieren wir $aR b:\iff a\equiv b\space \mod\space n$aRb:⟺a≡bmodn. Zwei Zahlen sollen also genau dann äquivalent sein, wenn sie kongruent modulo n sind, also bei der Division durch $n$n den gleichen Rest lassen.

Man überzeugt sich leicht, dass die so definierte Relation eine Äquivalenzrelation ist (vgl. Satz 164R).

Die Äquivalenzklassen sind dann gerade alle Zahlen, die bei der Division durch $n$n den gleichen Rest lassen. Als Repräsentanten für die Klassen kann man die Zahlen $0,1,\cdots , n-1$0,1,⋯,n−1 auswählen.

Weitere Beispiele

Siehe unter

• betragsgleiche komplexe Zahlen (Bemerkung 16L3)
• halbmetrische Räume (Satz 5608K)

Jede Wissenschaft bedarf der Mathematik, die Mathematik bedarf keiner.

Jakob I. Bernoulli

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darfohne Genehmigung des Autors nicht weiterverwendet werden.

Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld•Dοrfplatz 25 • 17237 Blankеnsее•Tel.: 01734332309 (Vodafone/D2) •Email: cο@maτhepedιa.dе