Yacas Reloaded - Freies Computer Algebra System

Inhalt

Grundlagen der Mathematik

Bezeichnungen

Elementarmathematik

Logik

Mengenlehre

Teilmengen

Mengenoperationen

Potenzmenge

Tupel und Produktmenge

Abbildungen und Funktionen

Gleichmächtigkeit

Permutationen

Relationen

Äquivalenzrelationen

Beispiel Hyperbeln

Teilweise Ordnungen

Relationenalgebra

Zermelo-Fraenkel-

Mengenlehre

Multimengen

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

Äquivalenzrelationen

Neu: Das Wurzelzieher Mathepedia Forum.

Jetzt registrieren und mit anderen Nutzern über Mathematik diskutieren!

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 mit xRy. In Mengenschreibweise:

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

Die Menge aller Äquivalenzklassen A | R heißt das Restesystem von R nach 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 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

Beweis

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

Wenn andererseits xRy und ein beliebiges , dann ist xRz und wegen der Symmetrie auch zRx und wegen der Transitivität zRy und damit ist . Damit haben wir gezeigt. Die Inklusion zeigt man analog.

Satz 5410Y (Äquivalenzklassen als Zerlegung)

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

Keine Äquivalenzklasse ist leer:
Die Vereinigung aller Äquivalenzklassen ist die Menge A selbst:
Je zwei verschiedene Äquivalenzklassen sind disjunkt:

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 und , dann gilt xRz und yRz, wegen der Transitivität auch xRy und wegen dem oben gezeigten also x | R = y | R.

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 einer Menge A gegeben ist, können wir in natürlicher Weise eine Äquivalenzrelation definieren, so dass diese Zerlegung genau aus den Restklassen A | R besteht.

Beweis

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

Wenn eine Zerlegung von A ist, definieren wir . Zwei Elemente stehen also genau dann in Relation genau dann, wenn es eine Menge aus gibt, zu der sie gemeinsam gehören. Wir merken an, dass dieses Z aus der Definition eindeutig bestimmt ist, da ja nur aus disjunkten nicht leeren Mengen besteht, die A überdecken.

Auf Grund der Definition ist klar, dass wenn eine Äquivalenzrelation ist, dann stimmen die Äquivalenzklassen mit den Mengen aus überein.

Es bleibt zu zeigen, dass tatsächlich eine Äquivalenzrelation ist. ist reflexiv, da jedes auch in einem liegen muss. Wenn dann gibt es ein mit also gilt auch , womit symmetrisch ist.

Wenn gibt es ein Z₁ mit . Gilt auch , dann muss es ein Z₂ geben, so dass . Z₁ und Z₂ enthalten ein gemeinsames Element y, daher muss wegen der Zerlegungseigenschaft Z₁ = Z₂ gelten. Also ist auch , womit die Transitivität gezeigt ist.

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 und definieren wir . 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 auswählen.

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

Weitere Beispiele

Siehe unter

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

An Archimedes wird man sich erinnern, wenn Aischylos vergessen ist - weil zwar die Sprachen sterben, nicht aber die mathematischen Ideen.

Godfrey Harold Hardy

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: