Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 11

Aus Wikiversity
Zur Navigation springen Zur Suche springen
So gerne Vorli als Vorlesungshund arbeitet, hinterher ist sie doch ganz schön ausgepowert von all der Energie, die sie zum Fließen gebracht hat. Da braucht sie erstmal ein Nickerchen um zu regenerieren.




Äquivalenzklassen und Repräsentantensysteme

Eine Äquivalenzrelation auf einer Menge kann auch als Zerlegung der Menge aufgefasst werden. Hierzu ist der Begriff der Äquivalenzklasse nützlich.


Definition  

Sei eine Äquivalenzrelation und . Dann ist

die Äquivalenzklasse von bezüglich .

In Worten: ist die Teilmenge aller Elemente von , die zu äquivalent sind, also einfach die Faser zu . Jede Teilmenge , die die Gestalt für ein besitzt, heißt Äquivalenzklasse. Jedes Element heißt ein Repräsentant für die Äquivalenzklasse . Insbesondere ist selbst ein Repräsentant für die Klasse , doch ist dies keineswegs der einzige oder der „beste“ Repräsentant.


Definition  

Es sei eine Äquivalenzrelation auf einer Menge . Eine Teilmenge heißt ein Repräsentantensystem für die Äquivalenzrelation, wenn es für jede Äquivalenzklasse genau ein Element aus aus dieser Klasse gibt.


Beispiel  

Wir knüpfen an Beispiel 10.5 an. Die gesamte Wäsche haben wir gemäß der Waschverträglichkeit sortiert und es haben sich dabei verschiedene Haufen ergeben, wobei zwei Kleidungsstücke genau dann auf dem gleichen Haufen gelandet sind, wenn sie zueinander waschverträglich sind. Die Haufen sind also die Äquivalenzklassen. Die Äquivalenzklasse zu einem bestimmten Kleidungsstück besteht aus allen zu waschverträglichen Kleidungsstücken, also aus allen Kleidungsstücken, die zusammen mit auf dem gleichen Haufen liegen. Wenn wir aus jedem Haufen ein bestimmtes Kleidungsstück auswählen, so haben wir ein Repräsentantensystem für die Waschverträglichkeit.


Bemerkung  

Wir betrachten in einigen Beispielen von Äquivalenzrelationen die Äquivalenzklassen. Wenn die Äquivalenzrelation die Gleichheit ist, so sind alle Äquivalenzklassen einelementig und die Äquivalenzklasse zu ist einfach die einelementige Menge . Im anderen Extremfall, wenn alle Elemente zueinander äquivalent sind, so gibt es nur eine einzige Äquivalenzklasse, nämlich die Gesamtmenge .

Bei der Äquivalenzrelation auf der Menge der Bruchterme, die durch die Wertegleichheit in gegeben ist, besteht die Äquivalenzklasse zu aus allen anderen Bruchdarstellungen dieser Zahl, also beispielsweise aus . Ein Repräsentantensystem liegt in der Menge aller gekürzten Brüche vor.

Wenn eine Äquivalenzrelation auf durch eine Abbildung im Sinne von Lemma 10.10 festgelegt ist, so sind die Äquivalenzklassen die nichtleeren Fasern der Abbildung. Die Äquivalenzklasse zu besteht aus dem Urbild von , ist also gleich

Um ein Repräsentantensystem zu erhalten, muss man aus jeder Faser ein Element auswählen. Im Allgemeinen gibt es hier kein besonders einfaches Repräsentantensystem.

In Beispiel 10.11 besteht die Äquivalenzklasse zu aus (wobei diese beiden Zahlen nicht unbedingt, wie etwa bei , verschieden sein müssen). Wenn angeordnet ist, so kann man die nichtnegativen Elemente als ein übersichtliches Repräsentantensystem heranziehen.

In Beispiel 10.12 bei der durch die Gaußklammer gegebenen Äquivalenzrelation besteht die Äquivalenzklasse zu aus dem halboffenen Intervall

Ein besonders einfaches Repräsentantensystem ist durch die Menge der ganzen Zahlen gegeben.

Bei der durch das Betrachten des Bruchanteils (der Nachkommazahl) gegebenen Äquivalenzrelation auf besteht die Äquivalenzklasse zu aus der Menge , also aus allen Zahlen, die man von aus mit einem ganzzahligen Schritt erreichen kann. Die Menge der Zahlen zwischen und einschließlich der und ausschließlich der , also der Zahlen aus dem halboffenen Intervall , ist ein Repräsentantensystem.

In Beispiel 10.13, der Erreichbarkeitsrelation auf dem Landweg, besteht die Äquivalenzklasse zu aus der Insel bzw. dem Kontinent, auf der bzw. dem der Punkt liegt.



Beispiel  

Es sei fixiert. Wir bestimmen auf die Äquivalenzklassen zur Äquivalenzrelation , bei der zwei Zahlen als äquivalent betrachtet werden, wenn ihre Differenz ein Vielfaches von ist. Zu jeder Zahl kann man einfach die zugehörige Äquivalenzklasse finden, sie besteht aus allen Zahlen der Form

In jeder Äquivalenzklasse gibt es ein Element (einen Vertreter, einen Repräsentanten) zwischen und , da ja insbesondere zu seinem Rest bei der Division durch äquivalent ist. Andererseits sind bei

die Äquivalenzklassen zu und zu verschieden. Es ist nämlich

da aus

sofort

folgt, was wegen

nicht sein kann.


Concentric circles isotropy.svg

Beispiel  

In der Ebene sei ein bestimmter Punkt markiert. Wir betrachten die Äquivalenzrelation, bei der zwei Punkte und als äquivalent gelten, wenn sie zu den gleichen Abstand besitzen. Dies wird durch

ausgedrückt. Dies ist eine Äquivalenzrelation, wie man direkt überprüfen kann und was auch aus Lemma 10.10 folgt, da man ja die Situation mittels der Abbildung

interpretieren kann. Die Äquivalenzklasse zu einem Punkt besteht aus allen Punkten der Ebene, die in ihrem Abstand zu mit übereinstimmen. Dies ist genau der Kreis mit Mittelpunkt durch den Punkt . Die Äquivalenzklassen sind also die konzentrischen Kreise um den Mittelpunkt , wobei man hier den Punkt als Kreis mit Radius mitzählen muss (man kann sich darüber streiten, ob das ein Kreis ist, jedenfalls ist diese einpunktige Menge hier eine Äquivalenzklasse).


Drei Äquivalenzklassen für die durch die Parallelität gegebene Äquivalenzrelation.

Beispiel  

Auf der Menge aller Geraden in der Ebene kann man die Parallelität als Äquivalenzrelation auffassen. Eine Gerade ist zu sich selbst parallel, die Relation ist offenbar symmetrisch und wenn zu parallel und zu parallel ist, so ist auch zu parallel. Die Äquivalenzklasse zu einer Geraden besteht aus allen zu parallelen Geraden, diese bilden eine parallele Geradenschar. Wir fixieren einen Punkt in der Ebene. Dann gibt es zu jeder Geraden eine dazu parallele Gerade , die durch den Punkt verläuft. Man kann also jede Äquivalenzklasse durch eine Gerade durch den Punkt repräsentieren, und zwar eindeutig, da parallele Geraden, die durch einen Punkt verlaufen, übereinstimmen müssen. Die Menge der Geraden durch bildet also ein Repräsentantensystem für die Äquivalenzrelation der Parallelität.


Chess Board.svg

Beispiel  

Beim Schach darf ein Läufer diagonal in jede Richtung beliebig weit ziehen. Zwei Felder heißen läuferäquivalent, wenn man von dem einen Feld mit endlich vielen Läuferzügen zu dem anderen Feld gelangen kann. Das ist eine Äquivalenzrelation. Da sich bei einem Diagonalzug die Farbe des Feldes nicht ändert, bleibt ein Läufer, der auf einem weißen Feld steht, stets auf einem weißen Feld. Zugleich kann ein Läufer, der auf einem weißen Feld steht, jedes weiße Feld (grundsätzlich, ohne Beachtung von anderen Figuren in einer Stellung) erreichen. Deshalb gibt es zwei Äquivalenzklassen: die weißen Felder und die schwarzen Felder, und entsprechend spricht man von weißfeldrigen Läufern und schwarzfeldrigen Läufern (das ist nicht die Farbe der Figur).




Quotientenmenge und kanonische Abbildung

Beispiel  

Wir knüpfen an Beispiel 10.5 und Beispiel 11.3 an. Die Wäsche liegt in verschiedenen waschgangverträglichen Haufen vor. Für den weiteren Ablauf (beispielsweise in welcher Reihenfolge gewaschen wird) kommt es auf die Einzelsachen nicht mehr an, sondern nur noch auf die einzelnen Haufen. Es ist daher sinnvoll, die entstandene Situation dadurch zu erfassen, dass man die Menge der Haufen bildet. Jeder Haufen wird zu genau einem Element in dieser Haufenmenge. Das Sortieren kann man dann auffassen als eine Abbildung von der Wäschemenge in die Haufenmenge, wobei jedem Wäschestück der zugehörige Haufen zugeordnet wird. Bei diesem Übergang werden waschgangverträgliche Sachen miteinander identifiziert. Dies ist die Grundidee der Quotientenmenge und der kanonischen Abbildung.



Definition  

Sei eine Äquivalenzrelation. Dann heißt

die Quotientenmenge von .

Die Quotientenmenge ist also einfach die Menge der Äquivalenzklassen. Wenn man die Äquivalenzrelation mit bezeichnet, so schreibt man für die Quotientenmenge. Das Konzept Quotientenmenge ist nicht einfach, allein schon deshalb, da es nach Definition eine Menge von Mengen, nämlich der Äquivalenzklassen ist. Von der Handhabung und der Vorstellung her betrachtet man aber diese Äquivalenzklassen eher als neue „Punkte“ in einer neuen Menge, die eben erst durch die Konstruktion entsteht. Auch die Beziehung zu einem Repräsentantensystem ist nicht ganz einfach. Wenn man ein Repräsentantensystem für eine Äquivalenzrelation hat, so ergibt sich eine bijektive Abbildung zwischen dem Repräsentantensystem und der Quotientenmenge. Diese kann zu Verwechslungen führen. Wichtig ist, dass ein Repräsentantensystem von einer Wahl abhängt und nur selten kanonisch ist, während die Quotientenmenge nicht von Wahlen abhängt. Wenn es allerdings ein besonders einfaches Repräsentantensystem gibt, so übernimmt man die Bezeichnungen für die Elemente wiederum auch als Bezeichnungen für die Elemente der Quotientenmenge.

Man muss aber auch sagen, dass die Abstraktion, die in der Quotientenmenge zum Ausdruck kommt, in vielen Kontexten anzutreffen ist. Beispielsweise gibt es die Menge der Tiere und die Menge der Tierarten. Hinter Tierart steckt doch eine andere Idee als die Menge der zu unter diese Tierart fallenden Einzeltiere oder die Idee, aus jeder Tierart einen Vertreter auszuwählen. Die Menge aller geraden und die Menge aller ungeraden Zahlen wird durch das Eigenschaftspaar gerade oder ungerade deutlicher gemacht. Entsprechend führt die Parallelität zur Idee der „Richtung“ einer Geraden, u.s.w.

Im oben angeführten Beispiel 11.5 besteht die Quotientenmenge aus den Restklassen , wobei die Bezeichnungen des einfachsten Repräsentantensystems übernommen werden. Die konzentrischen Kreise um den Punkt aus Beispiel 11.6 kann man mit ihrem Radius identifizieren, d.h. die Quotientenmenge steht in einer natürlichen Korrespondenz zu . Auch dies ist eine wichtige Beobachtung, dass die Quotientenmenge häufig eine neue Struktur besitzt oder in einer natürlichen Beziehung zu einem anderen mathematischen Gebilde steht, was von der Ausgangsmenge her nicht unmittelbar ersichtlich ist. So kann man auch die Menge der Geraden durch einen Punkt , die ein Repräsentantensystem für die Parallelität ist, in einem weiteren Schritt mit den Punkten auf einem halboffenen Halbkreis um identifizieren, um eine geometrische gehaltvolle Interpretation der Quotientenmenge zu erhalten. Die Quotientenmenge zur Äquivalenzrelation des Läufers besteht nur aus den Feldfarben weiß und schwarz.


Definition  

Sei eine Äquivalenzrelation und die Quotientenmenge. Die Abbildung

heißt kanonische Projektion von .

Man spricht auch von der Identifizierungsabbildung, da unter dieser Abbildung äquivalente Elemente auf das gleiche Element, ihre Klasse, abgebildet werden.



Lemma  

Es sei eine Menge und eine Äquivalenzrelation auf mit den Äquivalenzklassen und der Quotientenmenge . Dann gelten folgende Aussagen.

  1. Es ist genau dann, wenn ist, und dies gilt genau dann, wenn .
  2. ist eine disjunkte Vereinigung.
  3. Die kanonische Projektion

    ist surjektiv.

  4. Es ist .

Beweis  

  1. Seien und äquivalent und . Dann ist und nach der Transitivität auch , also . Damit stimmen die Äquivalenzklassen überein. Die Implikation von der Mitte nach rechts ist klar, da wegen Äquivalenzklassen nicht leer sind. Sei nun , und sei ein Element im Durchschnitt. Dann ist und und wegen der Transitivität ist .
  2. Wegen der Reflexivität ist und daher ist . Wegen Teil (1) ist die Vereinigung disjunkt.
  3. Die Surjektivität ist klar aufgrund der Definition der Quotientenmenge, und da auf die Klasse geschickt wird.
  4. Es ist


Bei der Eigenschaft (2) sagt man auch, dass die Äquivalenzrelation eine Partition der Menge bewirkt. Die Eigenschaft (4) bedeutet insbesondere, dass man zu jeder Äquivalenzrelation eine Abbildung, nämlich die kanonische Abbildung in die Quotientenmenge, angeben kann, derart, dass Elemente genau dann äquivalent sind, wenn sie unter der Abbildung den gleichen Wert besitzen. Damit ist gezeigt, dass man jede Äquivalenzrelation als eine Äquivalenzrelation zu einer Abbildung im Sinne von Lemma 10.10 erhalten kann.

Die folgende Aussage beschreibt die universelle Eigenschaft der Quotientenmenge.



Lemma  

Es sei eine Menge und eine Äquivalenzrelation auf mit der Quotientenmenge . Es sei eine Abbildung mit für alle mit .

Dann gibt es eine eindeutig bestimmte Abbildung mit .

Beweis  

Sei gegeben. Die einzige Möglichkeit für ist zu setzen. Es muss aber gezeigt werden, dass diese Abbildung überhaupt wohldefiniert ist, also unabhängig von der Wahl des Repräsentanten ist. Sei hierzu , also . Dann ist nach der Voraussetzung an aber .


Bemerkung  

Zu einer Abbildung und der zugehörigen Äquivalenzrelation im Sinne von Lemma 10.10 gibt es nach Lemma 11.13 eine eindeutig bestimmte Abbildung

mit

Diese ist sogar injektiv.



Beispiel  

Sei und ein Körper. Wir setzen . Der ist ein Vektorraum, wobei die Skalarmultiplikation von und mit bezeichnet wird. Sei weiter

Zwei Punkte werden also als äquivalent erklärt, wenn sie durch Skalarmultiplikation mit einem Skalar ineinander überführt werden können. Ebenso könnte man sagen, dass zwei Punkte als äquivalent gelten, wenn sie dieselbe Gerade durch den Nullpunkt definieren.

Dass wirklich eine Äquivalenzrelation vorliegt, sieht man so. Die Reflexivität folgt aus für jedes . Zum Nachweis der Symmetrie sei , d.h. es gibt ein mit . Dann gilt aber auch , da ja ein Inverses besitzt. Zum Nachweis der Transitivität sei und angenommen, d.h. es gibt mit und . Dann ist insgesamt mit . Die Äquivalenzklassen zu dieser Äquivalenzrelation sind die einzelnen Geraden durch den Nullpunkt (aber ohne den Nullpunkt). Die Quotientenmenge heißt projektiver Raum über (der Dimension ) und wird mit bezeichnet.



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)