Äquivalenzrelationen

Eine Relation RR ist eine Äquivalenzrelation in AA genau dann, wenn sie reflexiv, symmetrisch und transitiv ist.
Unter der Äquivalenzklasse oder Restklasse x∣Rx|R eines Elements xx verstehen wir alle y∈Ay\in A mit xRyxRy. In Mengenschreibweise:
x∣R:={y∈A∣ xRy}x|R:=\{y\in A| \space xRy\}
Dieses xx wird auch der Repräsentant der Äquivalenzklasse genannt.
Die Menge aller Äquivalenzklassen A∣RA|R heißt das Restesystem von RR nach AA.
A∣R:={x∣R ∣ x∈A}A|R:=\{x|R\space | \space x\in A\}
 
 

Bemerkung

Auf die Reflexivität kann in obiger Definition nicht verzichtet werden. Eine symmetrische und transitive Relation muss nicht notwendigerweise reflexiv sein. Es folgt zwar aus xRyxRy wegen der Symmetrie sofort yRxyRx und mit der Transitivität auch xRxxRx. Dieser Schluss ist aber nur dann korrekt, wenn es ein yy mit xRyxRy gibt.

Satz 5410X

Zwei Äquivalenzklassen x∣Rx|R und y∣Ry|R sind genau dann gleich, wenn xRyxRy, also ihre Repräsentanten in Relation zueinander stehen:
x∣R=y∣R  ⟺  xRyx|R=y|R\iff xRy.

Beweis

Sei x∣R=y∣Rx|R=y|R, dann ist wegen der Reflexivität von RR: x∈x∣Rx\in x|R und x∈y∣Rx\in y|R damit gilt aber xRyxRy.
Wenn andererseits xRyxRy und ein beliebiges z∈x∣Rz\in x|R, dann ist xRzxRz und wegen der Symmetrie auch zRxzRx und wegen der Transitivität zRyzRy und damit ist z∈y∣Rz\in y|R. Damit haben wir x∣R⊆y∣Rx|R\subseteq y|R gezeigt. Die Inklusion y∣R⊆x∣Ry|R\subseteq x|R zeigt man analog. □\qed

Satz NZ38 (Äquivalenzklassen als Zerlegung)

Sei RR eine Äquivalenzrelation in AA. Dann gelten für das Restesystem A∣RA|R folgende Eigenschaften
  1. Keine Äquivalenzklasse ist leer: ∀X∈A∣R:X≠∅\forall X\in A|R: X\neq \emptyset
  2. Die Vereinigung aller Äquivalenzklassen ist die Menge AA selbst: ⋃(A∣R)=A\bigcup\limits (A|R) = A
  3. Je zwei verschiedene Äquivalenzklassen sind disjunkt: X,Y∈A∣R∧X≠Y  ⟹  X∩Y=∅X,Y\in A|R \and X\neq Y \implies X\cap Y=\emptyset
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∣Rx|R und y∣Ry|R zwei Äquivalenzklassen und haben sie ein Element gemeinsam, dann stimmen sie überein. Sei z∈x∣Rz\in x|R und z∈y∣Rz\in y|R, dann gilt xRzxRz und yRzyRz, wegen der Transitivität auch xRyxRy und wegen dem oben gezeigten also x∣R=y∣Rx|R=y|R. □\qed
Jede Äquivalenzrelation RR in AA erzeugt eine Zerlegung der Menge AA. Es gilt sogar die Umkehrung. Das Ergebnis fassen wir in folgendem Satz zusammen.

Satz YP15 (Hauptsatz über Äquivalenzrelationen)

Sei AA eine Menge und RR eine Äquivalenzrelation in AA, dann erzeugt RR eine Zerlegung der Menge AA. Die Mengen dieser Zerlegung sind gerade die Äquivalenzklassen.
Wenn andererseits eine Zerlegung Z\sb Z einer Menge AA gegeben ist, können wir in natürlicher Weise eine Äquivalenzrelation RZR_{\sb Z} definieren, so dass diese Zerlegung Z\sb Z genau aus den Restklassen A∣RA|R besteht.

Beweis

Den ersten Teil des Satzes haben wir schon beweisen (Satz NZ38).
Wenn RZR_{\sb Z} eine Zerlegung von AA ist, definieren wir xRZy:  ⟺  ∃Z∈Z:x∈Z∧y∈ZxR_{\sb Z}y:\iff \exists Z\in \sb Z: x\in Z\and y\in Z. Zwei Elemente stehen also genau dann in Relation genau dann, wenn es eine Menge aus Z\sb Z gibt, zu der sie gemeinsam gehören. Wir merken an, dass dieses ZZ aus der Definition eindeutig bestimmt ist, da ja Z{\sb Z} nur aus disjunkten nicht leeren Mengen besteht, die AA überdecken.
Auf Grund der Definition ist klar, dass wenn RZR_{\sb Z} eine Äquivalenzrelation ist, dann stimmen die Äquivalenzklassen mit den Mengen aus Z\sb Z überein.
Es bleibt zu zeigen, dass RZR_{\sb Z} tatsächlich eine Äquivalenzrelation ist. RZR_{\sb Z} ist reflexiv, da jedes x∈Ax\in A auch in einem Z∈ZZ\in \sb Z liegen muss. Wenn xRZyxR_{\sb Z}y dann gibt es ein Z∈ZZ\in \sb Z mit x,y∈Zx,y\in Z also gilt auch yRZxyR_{\sb Z}x, womit RZR_{\sb Z} symmetrisch ist.
Wenn xRZyxR_{\sb Z}y gibt es ein Z1Z_1 mit x,y∈Z1x,y\in Z_1. Gilt auch yRZzyR_{\sb Z}z, dann muss es ein Z2Z_2 geben, so dass y,z∈Z2y,z\in Z_2. Z1Z_1 und Z2Z_2 enthalten ein gemeinsames Element yy, daher muss wegen der Zerlegungseigenschaft Z1=Z2Z_1=Z_2 gelten. Also ist auch xRZzxR_{\sb Z}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∈Za,b\in\dom Z und n∈N+n\in \dom{N^+} definieren wir aRb:  ⟺  a≡b mod   naR b:\iff a\equiv b\space \mod\space n. Zwei Zahlen sollen also genau dann äquivalent sein, wenn sie kongruent modulo n sind, also bei der Division durch nn 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 nn den gleichen Rest lassen. Als Repräsentanten für die Klassen kann man die Zahlen 0,1,⋯ ,n−10,1,\cdots , n-1 auswählen.
Für n=2n=2 sind die Äquivalenzklassen genau die geraden und die ungeraden natürlichen Zahlen.

Weitere Beispiele

Siehe unter

Jede Wissenschaft bedarf der Mathematik, die Mathematik bedarf keiner.

Jakob I. Bernoulli

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne 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е
Datenschutzerklärung

 

Mengenlehre