Logo Mathepedia Mathepedia auf Facebook
Wurzelzieher Blog
 

Mengenlehre


Äquivalenzrelationen

Eine Relation \(\displaystyle R\) ist eine Äquivalenzrelation in \(\displaystyle A\) genau dann, wenn sie reflexiv, symmetrisch und transitiv ist.

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

\(\displaystyle x|R:=\{y\in A| \space xRy\}\)

Dieses \(\displaystyle x\) wird auch der Repräsentant der Äquivalenzklasse genannt.

Die Menge aller Äquivalenzklassen \(\displaystyle A|R\) heißt das Restesystem von \(\displaystyle R\) nach \(\displaystyle A\).

\(\displaystyle 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 \(\displaystyle xRy\) wegen der Symmetrie sofort \(\displaystyle yRx\) und mit der Transitivität auch \(\displaystyle xRx\). Dieser Schluss ist aber nur dann korrekt, wenn es ein \(\displaystyle y\) mit \(\displaystyle xRy\) gibt.

Satz 5410X

Zwei Äquivalenzklassen \(\displaystyle x|R\) und \(\displaystyle y|R\) sind genau dann gleich, wenn \(\displaystyle xRy\), also ihre Repräsentanten in Relation zueinander stehen

\(\displaystyle x|R=y|R\iff xRy\).

Beweis

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

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

Satz 5410Y (Äquivalenzklassen als Zerlegung)

Sei \(\displaystyle R\) eine Äquivalenzrelation in \(\displaystyle A\). Dann gelten für das Restesystem \(\displaystyle A|R\) folgende Eigenschaften

  1. Keine Äquivalenzklasse ist leer: \(\displaystyle \forall X\in A|R: X\neq \emptyset\)
  2. Die Vereinigung aller Äquivalenzklassen ist die Menge \(\displaystyle A\) selbst: \(\displaystyle \bigcup\limits (A|R) = A\)
  3. Je zwei verschiedene Äquivalenzklassen sind disjunkt: \(\displaystyle 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 \(\displaystyle x|R\) und \(\displaystyle y|R\) zwei Äquivalenzklassen und haben sie ein Element gemeinsam, dann stimmen sie überein. Sei \(\displaystyle z\in x|R\) und \(\displaystyle z\in y|R\), dann gilt \(\displaystyle xRz\) und \(\displaystyle yRz\), wegen der Transitivität auch \(\displaystyle xRy\) und wegen dem oben gezeigten also \(\displaystyle x|R=y|R\). \(\displaystyle \qed\)

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

Satz 5410Z (Hauptsatz über Äquivalenzrelationen)

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

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

Beweis

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

Wenn \(\displaystyle R_{\sb Z}\) eine Zerlegung von \(\displaystyle A\) ist, definieren wir \(\displaystyle xR_{\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 \(\displaystyle \sb Z\) gibt, zu der sie gemeinsam gehören. Wir merken an, dass dieses \(\displaystyle Z\) aus der Definition eindeutig bestimmt ist, da ja \(\displaystyle {\sb Z}\) nur aus disjunkten nicht leeren Mengen besteht, die \(\displaystyle A\) überdecken.

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

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

Wenn \(\displaystyle xR_{\sb Z}y\) gibt es ein \(\displaystyle Z_1\) mit \(\displaystyle x,y\in Z_1\). Gilt auch \(\displaystyle yR_{\sb Z}z\), dann muss es ein \(\displaystyle Z_2\) geben, so dass \(\displaystyle y,z\in Z_2\). \(\displaystyle Z_1\) und \(\displaystyle Z_2\) enthalten ein gemeinsames Element \(\displaystyle y\), daher muss wegen der Zerlegungseigenschaft \(\displaystyle Z_1=Z_2\) gelten. Also ist auch \(\displaystyle xR_{\sb Z}z\), womit die Transitivität gezeigt ist. \(\displaystyle \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 \(\displaystyle a,b\in\dom Z\) und \(\displaystyle n\in \dom{N^+}\) definieren wir \(\displaystyle aR 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 \(\displaystyle 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 \(\displaystyle n\) den gleichen Rest lassen. Als Repräsentanten für die Klassen kann man die Zahlen \(\displaystyle 0,1,\cdots , n-1\) auswählen.

Für \(\displaystyle n=2\) sind die Äquivalenzklassen genau die geraden und die ungeraden natürlichen Zahlen.

Weitere Beispiele

Siehe unter

Es gibt keinen Königsweg zur Mathematik.

Euklid

Copyright- und Lizenzinformationen: Diese Seite ist urheberlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Wurzelzieher Mathеpеdιa  •  Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
 
G: 31.01.2015 13:00:21 (416 ms; 219 M)
C: 27.03.2015 12:54:55 (88 ms; 380 M)