Zum Inhalt springen

Äquivalenzrelation – Serlo „Mathe für Nicht-Freaks“

Aus Wikibooks

Einführendes Beispiel

[Bearbeiten]
Eine Drehung um 90° hat dasselbe Ergebnis wie eine Drehung um 450°.

Oftmals verhalten sich verschiedene Objekte in bestimmten Aspekten gleich oder besitzen gleiche, beziehungsweise sehr ähnliche Eigenschaften. So ist das Ergebnis einer Drehung von dasselbe wie bei einer Drehung von . Exemplare von Büchern derselben ISB-Nummer besitzen denselben Inhalt und Autor. In diesem Kapitel wirst du die mathematischen Werkzeuge kennen lernen, mit denen du solche Äquivalenzen zwischen Objekten einer Grundmenge sauber beschreiben kannst.

Menge mit acht Buchexemplaren und eingezeichneter Äquivalenzrelation „ und besitzen dieselbe ISB-Nummer“ als Pfeildiagramm.

Eine Beziehung, die die Gleichwertigkeit zwischen Objekten unter bestimmten Aspekten ausdrückt, wird Äquivalenzrelation genannt. Wir werden sehen, dass folgende Relation auf der Grundmenge aller bisher gedruckter Buchexemplare eine Äquivalenzrelation ist:

und besitzen dieselbe ISB-Nummer.

Frage: Welche Eigenschaften besitzt diese Relation?

Die Relation ist

  • reflexiv: Für jedes Buchexemplar gilt: und besitzen dieselbe ISB-Nummer. Sprich: ein Buchexemplar hat immer dieselbe ISB-Nummer wie es selbst.
  • nicht irreflexiv: Weil die Grundmenge nicht leer ist, gibt es mindestens ein Buchexemplar . Dieses steht mit sich selbst in Relation, weil die Relation reflexiv ist, und damit ist die Relation nicht irreflexiv.
  • symmetrisch: Wenn und dieselbe ISB-Nummer besitzen, dann besitzen auch und dieselbe ISB-Nummer.
  • nicht antisymmetrisch: Es gibt mindestens zwei verschiedene Buchexemplare und , die dieselbe ISB-Nummer besitzen. Für diese beiden Exemplare steht zwar in Relation zu und in Relation zu , aber es ist .
  • transitiv: Wenn die Buchexemplare und dieselbe ISB-Nummer besitzen und die Buchexemplare und dieselbe ISB-Nummer besitzen, dann besitzen auch und dieselbe ISB-Nummer.
  • nicht linear: Nehme zwei verschiedene Buchexemplare und , so dass beide eine verschiedene ISB-Nummer haben. Dann steht weder mit noch mit in Relation. Damit ist die Relation nicht linear.

Wir werden sehen, dass die Eigenschaften der Reflexivität, Symmetrie und Transitivität der obigen Relation, genau diejenigen sind, die hinreichend und notwendig für eine Äquivalenzrelation sind.

Menge von acht Buchexemplaren, die durch die Äquivalenzrelation „ und besitzen dieselbe ISB-Nummer“ in Äquivalenzklassen zerlegt wurde.

Es gibt eine weitere Möglichkeit, Äquivalenzrelationen zu beschreiben: Die Möglichkeit, die Grundmenge in verschiedene disjunkte Teilmengen zu zerlegen. Nehmen wir wieder das obige Beispiel mit den Büchern. Stell dir vor, wir fassen alle Exemplare in eine Menge zusammen, die dieselbe ISB-Nummer besitzen. Es kommen also genau dann zwei Bücher und in dieselbe Menge, wenn sie dieselbe ISB-Nummer besitzen, wenn also in Relation zu steht. Eine so entstandene Teilmenge werden wir später Äquivalenzklasse nennen.

Das Ergebnis ist eine Zerlegung der Grundmenge aller gedruckter Buchexemplare in disjunkte Teilmengen. Jede dieser Teilmengen steht für ein konkretes Schriftwerk eines Autors. Denn jede ISB-Nummer bezeichnet eindeutig ein solches Schriftwerk und jede Teilmenge enthält genau diejenigen Exemplare, die dieselbe ISB-Nummer besitzen. Man kann diese Teilmengen nun als neue Objekte betrachten. Dadurch erhältst du die Menge aller Schriftwerke. Jedes Schriftwerk ist dabei als Menge, nämlich der Menge aller Exemplare dieses Schriftwerks, modelliert. Durch eine Zerlegung einer Menge mit Hilfe einer Äquivalenzrelation können also neue Objekte modelliert werden (dies ist eine gängige Vorgehensweise in der Mathematik).

Definitionen

[Bearbeiten]

Äquivalenzrelation

[Bearbeiten]

Eine Äquivalenzrelation ist folgendermaßen definiert:

Definition (Äquivalenzrelation)

Eine Äquivalenzrelation ist eine homogene, binäre Relation auf einer Grundmenge, die folgende Eigenschaften besitzt:

  • reflexiv: "Für jedes Element aus der Grundmenge gilt: "
  • symmetrisch: "Für je zwei Elemente aus der Grundmenge gilt: "
  • transitiv: "Für je drei Elemente aus der Grundmenge gilt: und "


Zwei Elemente, die bezüglich einer Äquivalenzrelation in Relation stehen, heißen äquivalent. Wenn zwei Elemente und äquivalent zueinander bezüglich einer Äquivalenzrelation sind, schreibt man oft oder einfach anstatt der sonst üblichen Schreibweise beziehungsweise .

Verständnisfrage: Was musst du tun, wenn du entscheiden sollst, ob eine Relation eine Äquivalenzrelation ist oder nicht?

Um zu entscheiden, ob eine Relation eine Äquivalenzrelation ist, musst du folgende Fragen beantworten:

Entscheidungsbaum zum Nachweis von Äquivalenzrelationen
Entscheidungsbaum zum Nachweis von Äquivalenzrelationen

Verständnisfrage: Welche der folgenden Relationen ist eine Äquivalenzrelation?

  1. und gehen in dieselbe Klasse“ auf der Menge aller Schüler einer Schule
  2. “ auf der Menge der ganzen Zahlen
  3. und sind ungerade“ auf der Menge
  4. und besitzen denselben Rest bei der Division durch zwei“ auf der Menge
  5. “ auf einer beliebigen, nicht leeren Grundmenge

Antwort:

  1. Äquivalenzrelation
  2. keine Äquivalenzrelation (die Relation ist nicht symmetrisch – so ist zwar , aber nicht auch )
  3. keine Äquivalenzrelation (die Relation ist nicht reflexiv – beispielsweise steht 2 nicht mit sich selbst in Relation)
  4. Äquivalenzrelation
  5. Äquivalenzrelation

Verständnisfrage: Wie viele totale Äquivalenzrelationen auf einer Grundmenge gibt es? (Eine Relation ist total, wenn für jeweils zwei Elemente und mindestens ein Element mit einem anderen in Relation steht. Sprich es gilt oder .)

Sei eine Äquivalenzrelation auf der Grundmenge . Seien beliebig. Da total ist, steht in Relation zu oder in Relation zu . Sei oBdA . Auf Grund der Symmetrie ist dann aber auch . Damit steht jedes Element mit jedem anderen Element in Relation.

Es gibt also genau eine totale Äquivalenzrelation auf einer Grundmenge , nämlich , bei der jedes Element mit jedem anderen in Relation steht.

Äquivalenzklasse

[Bearbeiten]

Im obigen Beispiel haben wir durch die Äquivalenzrelation die Grundmenge in disjunkte Teilmengen zerlegt, indem wir alle Buchexemplare in einer Teilmenge zusammengefasst haben, die in Relation steht. Eine solche Teilmenge wird Äquivalenzklasse genannt und mit bezeichnet:

Definition (Äquivalenzklasse)

Eine Äquivalenzklasse ist die Menge aller Elemente der Grundmenge , die zum Element äquivalent sind:

Wenn du die Relation explizit angeben musst, kannst du auch schreiben. Es ist dann

Das Element in der Schreibweise nennt man Repräsentant oder Vertreter. Ist unsere obige Definition für Äquivalenzklassen korrekt im Sinne, dass wenn und äquivalent zueinander sind? Dies beantwortet der folgende Satz:

Satz

Ist , dann ist .

Beweis

Sei . Zu zeigen ist, dass und ist. Sei also beliebig. Es gilt damit . Da außerdem ist, folgt aus der Transitivität der Äquivalenzrelation, dass auch ist. Dies bedeutet aber . Da beliebig war, ist .

Dass auch ist, kannst du analog beweisen.

Es gilt auch die Umkehrung des obigen Satzes:

Satz

Aus folgt .

Beweis

Sei . Damit ist , also für alle . Nun ist , da aufgrund der Reflexivität der Äquivalenzrelation. Daraus folgt, dass und somit nach Definition ist.

Zusammen ergeben die vorherigen beiden Sätze folgenden wichtigen Satz:

Satz (Zusammenhang zwischen Äquivalenz der Repräsentanten und der Äquivalenzklassen)

Für Äquivalenzklassen und deren Vertreter gilt folgender Zusammenhang:

Greift man aus jeder Äquivalenzklasse ein Element heraus, so erhält man ein Vertretersystem:

Definition (Vertretersystem, Repräsentantensystem)

Ist eine Äquivalenzrelation auf , so ist ein Vertretersystem (oder Repräsentantensystem) eine Teilmenge von , die aus jeder Äquivalenzklasse von genau ein Element enthält.

Verständnisfrage: Wie sehen die Äquivalenzklassen der folgenden Äquivalenzrelationen aus? Gib ein mögliches Vertretersystem an.

  1. und gehen in dieselbe Klasse“ auf der Menge aller Schüler einer Schule
  2. und besitzen denselben Rest bei der Division durch zwei“ auf der Menge
  3. “ auf einer beliebigen, nicht leeren Grundmenge

Antwort:

  1. Die Menge der Äquivalenzklassen ist die Menge aller Klassen der Schule. Dabei ist jede Klasse als Menge aller Schüler modelliert, die diese Klasse besuchen. Ein mögliches Vertretersystem ist die Menge aller Klassensprecher.
  2. Es gibt zwei Äquivalenzklassen: Die Menge aller Zahlen, die restlos durch 2 geteilt werden können, und die Menge aller Zahlen, die bei Division durch 2 den Rest 1 lassen. Damit zerfällt die Grundmenge in die Menge der geraden und in die Menge der ungeraden Zahlen. Ein Vertretersystem ist z.B.
  3. Jede Äquivalenzklasse ist einelementig. Die Grundmenge zerfällt also in die Menge (Beachte, dass dies eine Menge von einelementigen Mengen ist. Die Zerlegungsmenge ist ungleich der Grundmenge). Das einzige Vertretersystem ist selbst.

Zerlegung einer Menge

[Bearbeiten]

Oft haben wir bereits von der Zerlegung einer Menge gesprochen (welche in der Mengenlehre auch Partition genannt wird). Eine Zerlegung ist eine Aufteilung einer Grundmenge in verschiedene Teilmengen, so dass jedes Element aus der Grundmenge in genau einer Teilmenge enthalten ist. Eine Zerlegung kann man also als eine Menge von Teilmengen der Grundmenge auffassen. Damit garantiert ist, dass jedes Element der Grundmenge in genau einer Teilmenge enthalten ist, müssen zusätzliche Bedingungen erfüllt sein, die in der folgenden Definition zusammengefasst sind:

Definition (Zerlegung einer Menge)

Eine Zerlegung einer Menge ist eine Menge von Teilmengen von (also ), welche folgende Bedingungen erfüllt:

  • Die Vereinigung aller Mengen von ergibt die Menge :
  • Alle Mengen von sind paarweise disjunkt:
  • Alle Mengen von sind nicht leer:

Im nächsten Abschnitt werden wir den Zusammenhang zwischen Äquivalenzrelation und der durch ihr definierten Zerlegung genauer untersuchen. Alternativ kann die Zerlegung durch folgende Aussagen charakterisiert werden:

  • ,
  • ,
  • .

Zusammenhang zwischen Äquivalenzrelationen und der Zerlegung einer Menge

[Bearbeiten]

Wollen wir nun den Zusammenhang zwischen Äquivalenzrelationen und der Zerlegung einer Menge untersuchen. Im einführenden Beispiel haben wir gesehen, dass eine Äquivalenzrelation eine Zerlegung der Grundmenge definiert, indem man alle äquivalenten Elemente in einer Teilmenge, der Äquivalenzklasse, zusammenfasst. Eine solche Zerlegung einer Menge durch eine Äquivalenzrelation wird mit bezeichnet und in bestimmten Kontexten der Mathematik Quotientenraum oder Faktorraum genannt. Die Zerlegung der Grundmenge ist also:

Doch ist dies wirklich eine Zerlegung im Sinne der obigen Definition? Beweisen wir es:

Satz (Äquivalenzrelationen induzieren eine Zerlegung)

Sei eine Äquivalenzrelation auf der Grundmenge . Dann ist die Menge aller Äquivalenzklassen eine Zerlegung der Grundmenge.

Beweis (Äquivalenzrelationen induzieren eine Zerlegung)

Um zu zeigen, dass eine Zerlegung von ist, müssen wir folgende Behauptungen beweisen:

Beweisschritt:

Es ist genau dann , wenn und wenn ist.

Beweisschritt:

Jede Äquivalenzklasse ist nach Definition eine Teilmenge von . Damit ist auch die Vereinigung aller Äquivalenzklassen eine Teilmenge von .

Beweisschritt:

Sei beliebig. Da auf Grund der Reflexivität von das Element in Relation zu sich selbst steht, ist . Nun ist und damit

Da beliebig war, ist .

Beweisschritt:

Seien mit . Dann ist und für ein .

Widerspruchsbeweis: Sei . Dann gibt es ein mit und . Damit ist und . Aus der Transitivität folgt und damit aus dem Satz über den Zusammenhang zwischen Äquivalenzklassen und der Äquivalenz der Repräsentanten des vorherigem Abschnitts. Jedoch ist ein Widerspruch zu Annahme , so dass sein muss.

Beweisschritt:

Sei beliebig. Dann ist für ein . Wegen der Reflexivität von der Äquivalenzrelation ist und damit . Daraus folgt, dass insbesondere ist.

Doch wie sieht es umgekehrt aus? Kannst du aus einer vorgegebenen Partition einer Menge so eine Äquivalenzrelation definieren, dass ist?

Frage: Wie kann eine solche Äquivalenzrelation aussehen?

Damit die induzierte Menge der Äquivalenzrelation gleich der Partitionsmenge sein kann, muss für alle gelten:

Damit gibt es nur einen möglichen Kandidaten einer Äquivalenzrelation:

Satz (Jede Zerlegung induziert eine Äquivalenzrelation)

Sei eine Menge und eine Zerlegung dieser Menge. Dann gibt es genau eine Äquivalenzrelation , die diese Zerlegung induziert, für die also ist. Diese Äquivalenzrelation ist definiert durch:

Beweis (Jede Zerlegung induziert eine Äquivalenzrelation)

Sei eine Menge und eine Zerlegung dieser Menge.

Beweisschritt: Existenz einer Äquivalenzrelation, die diese Zerlegung induziert

Wir definieren die Relation über folgende Definition:

Beweisschritt: ist eine Äquivalenzrelation

Beweisschritt: ist reflexiv

Sei beliebig. Da die Vereinigung aller Mengen von die Grundmenge ergibt, gibt es eine Menge mit . Damit ist

Beweisschritt: ist symmetrisch

Sei beliebig. Es ist

Beweisschritt: ist transitiv

Sei mit und . Dann gibt es ein und ein mit und . Damit ist , da sowohl ein Element von als auch ein Element von ist. Da eine Partition ist, muss sein. Daraus folgt und damit .

Beweisschritt:

Sei und beliebig.

Beweisschritt:

Sei beliebig, also . Dann gibt es ein mit . Da und ist, ist . Daraus folgt , weil verschiedene Mengen von disjunkt sind. Damit ist , was zu beweisen war.

Beweisschritt:

Sei beliebig. Damit ist sowohl als auch ein Element von und damit . Daraus folgt . Da beliebig war, ist .

Aus den Behauptungen (2.1) und (2.2) folgt, dass ist.

Beweisschritt:

Beweisschritt:

Sei beliebig. Da ist, gibt es ein mit . Aus der Behauptung (2) folgt, dass und damit ist.

Beweisschritt:

Sei beliebig. Da alle Mengen aus nach Definition nicht leer sind, gibt es ein mit . Aus Behauptung (2) folgt, dass und damit ist.

Die Behauptung (3) folgt direkt aus Behauptung (3.1) und (3.2).

Beweisschritt: Eindeutigkeit dieser Äquivalenzrelation

Sei eine weitere Äquivalenzrelation mit . Sei beliebig. Es gilt dann

Induzierte Äquivalenzrelation

[Bearbeiten]

Hinweis

Wir benutzen hier den Begriff der Funktion, der erst später definiert wird.

Das Nachrechnen, dass eine gegebene Relation wirklich eine Äquivalenzrelation ist, benutzt oft ein Standardschema, was wir in diesem Satz zusammenfassen:

Satz

Seien nichtleere Mengen und eine Abbildung.

Auf sei eine Äquivalenzrelation gegeben. Wir definieren für die Relation .

Dann ist eine Äquivalenzrelation. Diese nennen wir "die durch induzierte Äquivalenzrelation".

Beweis

Wir müssen die drei Eigenschaften einer Äquivalenzrelation nachprüfen. Seien also

Beweisschritt: Reflexivität

, da reflexiv ist. Das ist nach Definition von äquivalent zu , also ist reflexiv.

Beweisschritt: Symmetrie

Gelte für und . Wir zeigen .

Also ist symmetrisch.

Beweisschritt: Transitivität

Sei und . Wir zeigen, dass .

Also ist transitiv.

Damit ist eine Äquivalenzrelation auf .

Hinweis

Die häufigste Anwendung ist die, wo auf der Menge die Relation die Gleichheit "" ist. Ist dann noch surjektiv, so ist keine Urbildmenge für leer und die Äquivalenzklassen in sind gerade die Urbilder der Elemente von . In diesem Fall kann man den Beweis schneller führen, wenn man nachrechnet, dass die Urbilder der Elemente von eine Zerlegung der Menge erzeugen.

Beispiel (Induzierte Äquivalenzrelation in )

Wähle , und die Funktion, die jeder natürlichen Zahl den Rest bei der Division durch 3 zuordnet. Dann besteht aus den Äquivalenzklassen

(Rest 0)

(Rest 1)

(Rest 2)

Beispiel (Induzierte Äquivalenzrelation im )

Seien und . Außerdem definiere mit . Die Funktion ist wegen sicher surjektiv. Die Äquivalenzklassen sind Geraden parallel zu der Urspungsgeraden , auf denen den konstanten Wert hat.

Warum sind Äquivalenzklassen interessant?

[Bearbeiten]

In vielen Fällen betrachtet man Äquivalenzklassen auf einer Menge mit einer durch einer oder mehrere Verknüpfungen definierten Struktur, wie Gruppe oder Vektorraum.

Dort betrachtet man Äquivalenzrelationen, wo man die Verknüpfungen der Grundmenge auf die Äquivalenzklassen "transportieren" kann. Als Teaser: wenn man in dem letzten Beispiel irgendeinen Vektor des mit zu einen beliebigen anderen Vektor mit addiert, erhält man immer einen Vektor der Klasse mit , egal, welche Vektoren man nimmt.

Genauso landet man immer in der Klasse mit , wenn man einen beliebigen Vektor der Klasse mit mit multipliziert.

Das wird später im Kapitel Faktorraum genauer untersucht.