Logo

Mathepedia

Unterstützen Sie die Mathepedia!

Jetzt

Mathepedia auf Facebook

Wurzelzieher Blog

Mengenlehre


Äquivalenzrelationen

Eine Relation R ist eine Äquivalenzrelation in A genau dann, wenn sie reflexiv, symmetrisch und transitiv ist.
Unter der Äquivalenzklasse oder Restklasse x | R eines Elements x verstehen wir alle wFormel mit xRy. In Mengenschreibweise:
wFormel
Dieses x wird auch der Repräsentant der Äquivalenzklasse genannt.
Die Menge aller Äquivalenzklassen A | R heißt das Restesystem von R nach A.
wFormel

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

Satz 5410X

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

Beweis

Sei x | R = y | R, dann ist wegen der Reflexivität von R: wFormel und wFormel damit gilt aber xRy.
Wenn andererseits xRy und ein beliebiges wFormel, dann ist xRz und wegen der Symmetrie auch zRx und wegen der Transitivität zRy und damit ist wFormel. Damit haben wir wFormel gezeigt. Die Inklusion wFormel zeigt man analog. wFormel

Satz 5410Y (Äquivalenzklassen als Zerlegung)

Sei R eine Äquivalenzrelation in A. Dann gelten für das Restesystem A | R folgende Eigenschaften
  1. Keine Äquivalenzklasse ist leer: wFormel
  2. Die Vereinigung aller Äquivalenzklassen ist die Menge A selbst: wFormel
  3. Je zwei verschiedene Äquivalenzklassen sind disjunkt: wFormel
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 und y | R zwei Äquivalenzklassen und haben sie ein Element gemeinsam, dann stimmen sie überein. Sei wFormel und wFormel, dann gilt xRz und yRz, wegen der Transitivität auch xRy und wegen dem oben gezeigten also x | R = y | R. wFormel
Jede Äquivalenzrelation R in A erzeugt eine Zerlegung der Menge A. Es gilt sogar die Umkehrung. Das Ergebnis fassen wir in folgendem Satz zusammen.

Satz 5410Z (Hauptsatz über Äquivalenzrelationen)

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

Beweis

Den ersten Teil des Satzes haben wir schon beweisen (Satz 5410Y).
Wenn wFormel eine Zerlegung von A ist, definieren wir wFormel. Zwei Elemente stehen also genau dann in Relation genau dann, wenn es eine Menge aus wFormel gibt, zu der sie gemeinsam gehören. Wir merken an, dass dieses Z aus der Definition eindeutig bestimmt ist, da ja wFormel nur aus disjunkten nicht leeren Mengen besteht, die A überdecken.
Auf Grund der Definition ist klar, dass wenn wFormel eine Äquivalenzrelation ist, dann stimmen die Äquivalenzklassen mit den Mengen aus wFormel überein.
Es bleibt zu zeigen, dass wFormel tatsächlich eine Äquivalenzrelation ist. wFormel ist reflexiv, da jedes wFormel auch in einem wFormel liegen muss. Wenn wFormel dann gibt es ein wFormel mit wFormel also gilt auch wFormel, womit wFormel symmetrisch ist.
Wenn wFormel gibt es ein Z1 mit wFormel. Gilt auch wFormel, dann muss es ein Z2 geben, so dass wFormel. Z1 und Z2 enthalten ein gemeinsames Element y, daher muss wegen der Zerlegungseigenschaft Z1 = Z2 gelten. Also ist auch wFormel, womit die Transitivität gezeigt ist. wFormel

 

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 wFormel und wFormel definieren wir wFormel. Zwei Zahlen sollen also genau dann äquivalent sein, wenn sie kongruent modulo n sind, also bei der Division durch 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 den gleichen Rest lassen. Als Repräsentanten für die Klassen kann man die Zahlen wFormel auswählen.
Für n = 2 sind die Äquivalenzklassen genau die geraden und die ungeraden natürlichen Zahlen.

Weitere Beispiele

Siehe unter

Im großen Garten der Geometrie kann sich jeder nach seinem Geschmack einen Strauß pflücken.

David Hilbert

 

 

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: 23.01.2014 13:52:36 (559 ms; 203 M)
C: 24.04.2014 00:22:42 (38 ms; 150 M)