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

Einführendes BeispielBearbeiten

 
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).

DefinitionenBearbeiten

ÄquivalenzrelationBearbeiten

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:

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.

ÄquivalenzklasseBearbeiten

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 MengeBearbeiten

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 ÄquivalenzrelationBearbeiten

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.