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

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 erst mal ein Nickerchen um zu regenerieren.

Äquivalenzklassen und Repräsentantensysteme

Eine Äquivalenzrelation ${}R\subseteq M\times M$ auf einer Menge ${}M$ kann auch als Zerlegung der Menge ${}M$ aufgefasst werden. Hierzu ist der Begriff der Äquivalenzklasse nützlich.

Definition Referenznummer erstellen

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation und ${}x\in M$. Dann ist

${}[x]:={\left\{y\in M\mid (x,y)\in R\right\}}\,$

die Äquivalenzklasse von ${}x$ bezüglich ${}R$.

In Worten: ${}[x]$ ist die Teilmenge aller Elemente von ${}M$, die zu ${}x$ äquivalent sind, also einfach die Faser zu ${}x$. Jede Teilmenge ${}S\subseteq M$, die die Gestalt ${}S=[x]$ für ein ${}x\in M$ besitzt, heißt Äquivalenzklasse. Jedes Element ${}y\in [x]$ heißt ein Repräsentant für die Äquivalenzklasse ${}[x]$. Insbesondere ist ${}x$ selbst ein Repräsentant für die Klasse ${}[x]$, doch ist dies keineswegs der einzige oder der „beste“ Repräsentant.

Definition Referenznummer erstellen

Es sei ${}\sim$ eine Äquivalenzrelation auf einer Menge ${}M$. Eine Teilmenge ${}T\subseteq M$ heißt ein Repräsentantensystem für die Äquivalenzrelation, wenn es für jede Äquivalenzklasse genau ein Element in ${}T$ aus dieser Klasse gibt.

Beispiel Beispiel 11.3 ändern

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 ${}x$ besteht aus allen zu ${}x$ waschverträglichen Kleidungsstücken, also aus allen Kleidungsstücken, die zusammen mit ${}x$ 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   Referenznummer erstellen

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

Bei der Äquivalenzrelation auf der Menge der Bruchterme, die durch die Wertegleichheit in ${}\mathbb {Q}$ gegeben ist, besteht die Äquivalenzklasse zu ${}{\frac {a}{b}}$ aus allen anderen Bruchdarstellungen dieser Zahl, also beispielsweise aus ${}{\frac {a}{b}},{\frac {2a}{2b}},{\frac {3a}{3b}},\ldots$. Ein Repräsentantensystem liegt in der Menge aller gekürzten Brüche vor.

Wenn eine Äquivalenzrelation auf ${}M$ durch eine Abbildung ${}f\colon M\rightarrow N$ im Sinne von Lemma 10.10 festgelegt ist, so sind die Äquivalenzklassen die nichtleeren Fasern der Abbildung. Die Äquivalenzklasse zu ${}x\in M$ besteht aus dem Urbild von ${}f(x)$, ist also gleich

${}f^{-1}(f(x))={\left\{y\in M\mid f(y)=f(x)\right\}}\,.$

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 ${}x\in K$ aus ${}\{x,-x\}$ (wobei diese beiden Zahlen nicht unbedingt, wie etwa bei ${}x=0$, verschieden sein müssen). Wenn ${}K$ angeordnet ist, so kann man die nichtnegativen Elemente ${}K_{\geq 0}$ als ein übersichtliches Repräsentantensystem heranziehen.

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

${}[\left\lfloor x\right\rfloor ,\left\lfloor x\right\rfloor +1[={\left\{y\in K\mid y\geq x{\text{ und }}y<x+1\right\}}\,.$

Ein besonders einfaches Repräsentantensystem ist durch die Menge der ganzen Zahlen ${}\mathbb {Z}$ gegeben.

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

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

Beispiel Beispiel 11.5 ändern

Es sei ${}d\in \mathbb {N}$ fixiert. Wir bestimmen auf ${}\mathbb {Z}$ die Äquivalenzklassen zur Äquivalenzrelation ${}\sim$, bei der zwei Zahlen ${}a,b\in \mathbb {Z}$ als äquivalent betrachtet werden, wenn ihre Differenz ${}a-b$ ein Vielfaches von ${}d$ ist. Zu jeder Zahl ${}a\in \mathbb {Z}$ kann man einfach die zugehörige Äquivalenzklasse finden, sie besteht aus allen Zahlen der Form

${}a+\mathbb {Z} d={\left\{a+nd\mid n\in \mathbb {Z} \right\}}\,.$

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

${}0\leq r<s\leq d-1\,$

die Äquivalenzklassen zu ${}r$ und zu ${}s$ verschieden. Es ist nämlich

${}(r+\mathbb {Z} d)\cap (s+\mathbb {Z} d)=\emptyset \,,$

da aus

${}r+nd=s+md\,$

sofort

${}s-r=(n-m)d\,$

folgt, was wegen

${}0<s-r<d\,$

nicht sein kann.

Beispiel Beispiel 11.6 ändern

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

${}d(P,M)=d(Q,M)\,$

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

$E\longrightarrow \mathbb {R} _{\geq 0},\,P\longmapsto d(P,M),$

interpretieren kann. Die Äquivalenzklasse zu einem Punkt ${}P$ besteht aus allen Punkten der Ebene, die in ihrem Abstand zu ${}M$ mit ${}d(P,M)$ übereinstimmen. Dies ist genau der Kreis mit Mittelpunkt ${}M$ durch den Punkt ${}P$. Die Äquivalenzklassen sind also die konzentrischen Kreise um den Mittelpunkt ${}M$, wobei man hier den Punkt ${}\{M\}$ als Kreis mit Radius ${}0$ 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 Referenznummer erstellen

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 ${}G_{1}$ zu ${}G_{2}$ parallel und ${}G_{2}$ zu ${}G_{3}$ parallel ist, so ist auch ${}G_{1}$ zu ${}G_{3}$ parallel. Die Äquivalenzklasse zu einer Geraden ${}G$ besteht aus allen zu ${}G$ parallelen Geraden, diese bilden eine parallele Geradenschar. Wir fixieren einen Punkt ${}M$ in der Ebene. Dann gibt es zu jeder Geraden ${}G$ eine dazu parallele Gerade ${}G'$, die durch den Punkt ${}M$ verläuft. Man kann also jede Äquivalenzklasse durch eine Gerade durch den Punkt ${}M$ repräsentieren, und zwar eindeutig, da parallele Geraden, die durch einen Punkt verlaufen, übereinstimmen müssen. Die Menge der Geraden durch ${}M$ bildet also ein Repräsentantensystem für die Äquivalenzrelation der Parallelität.

Beispiel Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation. Dann heißt

${}M/R:={\left\{[x]\mid x\in M\right\}}\,$

die Quotientenmenge von ${}R$.

Die Quotientenmenge ist also einfach die Menge der Äquivalenzklassen. Wenn man die Äquivalenzrelation mit ${}\sim$ bezeichnet, so schreibt man ${}M/\sim$ 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 ${}T\subseteq M$ für eine Äquivalenzrelation hat, so ergibt sich eine bijektive Abbildung ${}T\rightarrow Q$ 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 ${}[0],[1],\ldots ,[d-1]$, wobei die Bezeichnungen des einfachsten Repräsentantensystems übernommen werden. Die konzentrischen Kreise um den Punkt ${}M$ aus Beispiel 11.6 kann man mit ihrem Radius identifizieren, d.h. die Quotientenmenge steht in einer natürlichen Korrespondenz zu ${}\mathbb {R} _{\geq 0}$. 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 ${}M$, die ein Repräsentantensystem für die Parallelität ist, in einem weiteren Schritt mit den Punkten auf einem halboffenen Halbkreis um ${}M$ 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 Referenznummer erstellen

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation und ${}M/R$ die Quotientenmenge. Die Abbildung

$q_{R}\colon M\longrightarrow M/R,\,x\longmapsto [x],$

heißt kanonische Projektion von ${}R$.

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

Lemma Lemma 11.12 ändern

Es sei ${}M$ eine Menge und ${}\sim$ eine Äquivalenzrelation auf ${}M$ mit den Äquivalenzklassen ${}[x]$ und der Quotientenmenge ${}M/\sim$. Dann gelten folgende Aussagen.

1. Es ist ${}x\sim y$ genau dann, wenn ${}[x]=[y]$ ist, und dies gilt genau dann, wenn ${}[x]\cap [y]\neq \emptyset$.
2. ${}M=\bigcup _{[x]\in M/\sim }[x]$ ist eine disjunkte Vereinigung.
3. Die kanonische Projektion

   $q\colon M\longrightarrow M/\sim ,\,x\longmapsto [x],$

   ist surjektiv.

4. Es ist ${}q^{-1}([x])=[x]$.

Beweis

1. Seien ${}x$ und ${}y$ äquivalent und ${}u\in [x]$. Dann ist ${}x\sim u$ und nach der Transitivität auch ${}y\sim u$, also ${}u\in [y]$. Damit stimmen die Äquivalenzklassen überein. Die Implikation von der Mitte nach rechts ist klar, da wegen ${}x\sim x$ Äquivalenzklassen nicht leer sind. Es sei nun ${}[x]\cap [y]\neq \emptyset$, und sei ${}z$ ein Element im Durchschnitt. Dann ist ${}x\sim z$ und ${}y\sim z$ und wegen der Transitivität ist ${}x\sim y$.
2. Wegen der Reflexivität ist ${}x\in [x]$ und daher ist ${}M=\bigcup _{[x]\in M/\sim }[x]$. Wegen Teil (1) ist die Vereinigung disjunkt.
3. Die Surjektivität ist klar aufgrund der Definition der Quotientenmenge, und da ${}x$ auf die Klasse ${}[x]$ geschickt wird.
4. Es ist

   ${}q^{-1}([x])={\left\{y\in M\mid q(y)=[x]\right\}}={\left\{y\in M\mid [y]=[x]\right\}}={\left\{y\in M\mid y\sim x\right\}}=[x]\,.$

$\Box$

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 Lemma 11.13 ändern

Es sei ${}M$ eine Menge und ${}\sim$ eine Äquivalenzrelation auf ${}M$ mit der Quotientenmenge ${}M/\sim$. Es sei ${}\varphi \colon M\rightarrow W$ eine Abbildung mit ${}\varphi (x)=\varphi (y)$ für alle ${}x,y\in M$ mit ${}x\sim y$.

Dann gibt es eine eindeutig bestimmte Abbildung ${}{\overline {\varphi }}\colon M/\sim \,\,\rightarrow W$ mit ${}\varphi ={\overline {\varphi }}\circ q$.

Beweis

Sei ${}[x]\in M/\sim$ gegeben. Die einzige Möglichkeit für ${}{\overline {\varphi }}$ ist ${}{\overline {\varphi }}([x]):=\varphi (x)$ zu setzen. Es muss aber gezeigt werden, dass diese Abbildung überhaupt wohldefiniert ist, also unabhängig von der Wahl des Repräsentanten ist. Es sei hierzu ${}[x]=[y]$, also ${}x\sim y$. Dann ist nach der Voraussetzung an ${}\varphi$ aber ${}\varphi (x)=\varphi (y)$.

$\Box$

Bemerkung   Bemerkung 11.14 ändern

Zu einer Abbildung ${}f\colon M\rightarrow N$ und der zugehörigen Äquivalenzrelation ${}\sim$ im Sinne von Lemma 10.10 gibt es nach Lemma 11.13 eine eindeutig bestimmte Abbildung

$\psi \colon M/\sim \longrightarrow N$

mit

${}f=\psi \circ q\,.$

Diese ist sogar injektiv.

Beispiel Referenznummer erstellen

Es sei ${}n\in \mathbb {N}$ und ${}K$ ein Körper. Wir setzen ${}M=K^{n+1}\setminus \{0\}$. Der ${}K^{n+1}$ ist ein Vektorraum, wobei die Skalarmultiplikation von ${}\lambda \in K$ und ${}x\in K^{n+1}$ mit ${}\lambda \cdot x$ bezeichnet wird. Es sei weiter

${}R={\left\{(x,y)\in M\times M\mid {\text{ es gibt ein }}\lambda \in K\setminus \{0\}{\text{ mit }}\lambda \cdot x=y\right\}}\,.$

Zwei Punkte werden also als äquivalent erklärt, wenn sie durch Skalarmultiplikation mit einem Skalar ${}\lambda \neq 0$ 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 ${}x=1x$ für jedes ${}x\in M$. Zum Nachweis der Symmetrie sei ${}xRy$, d.h. es gibt ein ${}\lambda \neq 0$ mit ${}\lambda x=y$. Dann gilt aber auch ${}y=\lambda ^{-1}x$, da ja ${}\lambda$ ein Inverses besitzt. Zum Nachweis der Transitivität sei ${}xRy$ und ${}yRz$ angenommen, d.h. es gibt ${}\lambda ,\delta \neq 0$ mit ${}\lambda x=y$ und ${}\delta y=z$. Dann ist insgesamt ${}z=\delta y=(\delta \lambda )x$ mit ${}\delta \lambda \neq 0$. Die Äquivalenzklassen zu dieser Äquivalenzrelation sind die einzelnen Geraden durch den Nullpunkt (aber ohne den Nullpunkt). Die Quotientenmenge heißt projektiver Raum über ${}K$ (der Dimension ${}n$) und wird mit ${}{\mathbb {P} }_{K}^{n}$ bezeichnet.