Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 11/latex
\setcounter{section}{11}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller35.jpg} }
\end{center}
\bildtext {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.} }
\bildlizenz { Waeller35.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
\zwischenueberschrift{Äquivalenzklassen und Repräsentantensysteme}
Eine Äquivalenzrelation
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{ M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auf einer Menge $M$ kann auch als Zerlegung der Menge $M$ aufgefasst werden. Hierzu ist der Begriff der \stichwort { Äquivalenzklasse} {} nützlich.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{ M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Äquivalenzrelation}{}{}
und
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskettedisp
{\vergleichskette
{ [x]
}
{ \defeq} { { \left\{ y \in M \mid (x,y) \in R \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die \definitionswort {Ä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
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die die Gestalt
\mavergleichskette
{\vergleichskette
{S
}
{ = }{ [x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für ein
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
besitzt, heißt Äquivalenzklasse. Jedes Element
\mavergleichskette
{\vergleichskette
{ y
}
{ \in }{[x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt ein \stichwort {Repräsentant} {} für die Äquivalenzklasse
\mathl{[x]}{.} Insbesondere ist $x$ selbst ein Repräsentant für die Klasse
\mathl{[x]}{,} doch ist dies keineswegs der einzige oder der \anfuehrung{beste}{} Repräsentant.
\inputdefinition
{}
{
Es sei $\sim$ eine
\definitionsverweis {Äquivalenzrelation}{}{}
auf einer Menge $M$. Eine Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt ein \definitionswort {Repräsentantensystem}{} für die Äquivalenzrelation, wenn es für jede
\definitionsverweis {Äquivalenzklasse}{}{}
genau ein Element in $T$ aus dieser Klasse gibt.
}
\inputbeispiel{}
{
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 \definitionsverweis {Ä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 \definitionsverweis {Repräsentantensystem}{}{} für die Waschverträglichkeit.
}
\inputbemerkung
{}
{
Wir betrachten in einigen Beispielen von
\definitionsverweis {Äquivalenzrelationen}{}{}
die
\definitionsverweis {Äquivalenzklassen}{}{.}
Wenn die Äquivalenzrelation die Gleichheit ist, so sind alle Äquivalenzklassen einelementig und die Äquivalenzklasse zu $x$ ist einfach die einelementige Menge
\mavergleichskette
{\vergleichskette
{ [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 $\Q$ gegeben ist, besteht die Äquivalenzklasse zu
\mathl{{ \frac{ a }{ b } }}{} aus allen anderen Bruchdarstellungen dieser Zahl, also beispielsweise aus
\mathl{{ \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
\maabb {f} {M} {N
} {}
im Sinne von
Lemma 10.10
festgelegt ist, so sind die Äquivalenzklassen die nichtleeren Fasern der Abbildung. Die Äquivalenzklasse zu
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
besteht aus dem Urbild von
\mathl{f(x)}{,} ist also gleich
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{K
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus
\mathl{\{x,-x\}}{}
\zusatzklammer {wobei diese beiden Zahlen nicht unbedingt, wie etwa bei
\mavergleichskettek
{\vergleichskettek
{x
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
verschieden sein müssen} {} {.}
Wenn $K$ angeordnet ist, so kann man die nichtnegativen Elemente $K_{\geq 0}$ als ein übersichtliches
\definitionsverweis {Repräsentantensystem}{}{}
heranziehen.
In
Beispiel 10.12
bei der durch die Gaußklammer gegebenen Äquivalenzrelation besteht die Äquivalenzklasse zu $x$ aus dem halboffenen Intervall
\mavergleichskettedisp
{\vergleichskette
{[ \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 $\Z$ gegeben.
Bei der durch das Betrachten des Bruchanteils
\zusatzklammer {der Nachkommazahl} {} {}
gegebenen Äquivalenzrelation auf $K$ besteht die Äquivalenzklasse zu $x$ aus der Menge
\mathl{x + \Z}{,} also aus allen Zahlen, die man von $x$ aus mit einem ganzzahligen Schritt erreichen kann. Die Menge der Zahlen zwischen
\mathkor {} {0} {und} {1} {}
einschließlich der $0$ und ausschließlich der $1$, also der Zahlen aus dem
\definitionsverweis {halboffenen Intervall}{}{}
\mathl{[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.
}
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{d
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
fixiert. Wir bestimmen auf $\Z$ die
\definitionsverweis {Äquivalenzklassen}{}{}
zur
\definitionsverweis {Äquivalenzrelation}{}{}
$\sim$, bei der zwei Zahlen
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{\Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als äquivalent betrachtet werden, wenn ihre Differenz
\mathl{a-b}{} ein Vielfaches von $d$ ist. Zu jeder Zahl
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{\Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
kann man einfach die zugehörige Äquivalenzklasse finden, sie besteht aus allen Zahlen der Form
\mavergleichskettedisp
{\vergleichskette
{ a + \Z d
}
{ =} { { \left\{ a+ nd \mid n \in \Z \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
In jeder Äquivalenzklasse gibt es ein Element
\zusatzklammer {einen Vertreter, einen Repräsentanten} {} {}
zwischen
\mathkor {} {0} {und} {d-1} {,}
da ja insbesondere $a$ zu seinem Rest bei der Division durch $d$ äquivalent ist. Andererseits sind bei
\mavergleichskettedisp
{\vergleichskette
{0
}
{ \leq} {r
}
{ <} {s
}
{ \leq} {d-1
}
{ } {
}
}
{}{}{}
die Äquivalenzklassen zu $r$ und zu $s$ verschieden. Es ist nämlich
\mavergleichskettedisp
{\vergleichskette
{(r + \Z d ) \cap (s+ \Z d)
}
{ =} { \emptyset
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
da aus
\mavergleichskettedisp
{\vergleichskette
{r+nd
}
{ =} {s+md
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
sofort
\mavergleichskettedisp
{\vergleichskette
{s-r
}
{ =} { (n-m)d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
folgt, was wegen
\mavergleichskettedisp
{\vergleichskette
{0
}
{ <} { s-r
}
{ <} {d
}
{ } {
}
{ } {
}
}
{}{}{}
nicht sein kann.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Concentric circles isotropy.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Concentric circles isotropy.svg } {} {Tampert} {Commons} {CC-by-sa 3.0} {}
\inputbeispiel{}
{
In der Ebene $E$ sei ein bestimmter Punkt $M$ markiert. Wir betrachten die
\definitionsverweis {Äquivalenzrelation}{}{,}
bei der zwei Punkte
\mathkor {} {P} {und} {Q} {}
als äquivalent gelten, wenn sie zu $M$ den gleichen Abstand besitzen. Dies wird durch
\mavergleichskettedisp
{\vergleichskette
{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
\maabbeledisp {} {E} {\R_{\geq 0}
} {P} { d(P,M)
} {,}
interpretieren kann. Die Äquivalenzklasse zu einem Punkt $P$ besteht aus allen Punkten der Ebene, die in ihrem Abstand zu $M$ mit
\mathl{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
\mathl{\{M\}}{} als Kreis mit Radius $0$ mitzählen muss
\zusatzklammer {man kann sich darüber streiten, ob das ein Kreis ist, jedenfalls ist diese einpunktige Menge hier eine Äquivalenzklasse} {} {.}
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {ParalleleGeradenKlassen.png} }
\end{center}
\bildtext {Drei Äquivalenzklassen für die durch die Parallelität gegebene Äquivalenzrelation.} }
\bildlizenz { ParalleleGeradenKlassen.png } {Mgausmann} {} {Commons} {CC-by-sa 4.0} {}
\inputbeispiel{}
{
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 \mathkor {} {G_1} {zu} {G_2} {} parallel und \mathkor {} {G_2} {zu} {G_3} {} parallel ist, so ist auch \mathkor {} {G_1} {zu} {G_3} {} parallel. Die \definitionsverweis {Ä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.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Chess Board.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Chess Board.svg } {} {Nevit} {Commons} {gemeinfrei} {}
\inputbeispiel{}
{
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 \definitionsverweis {Ä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 \zusatzklammer {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 \zusatzklammer {das ist nicht die Farbe der Figur} {} {.}
}
\zwischenueberschrift{Quotientenmenge und kanonische Abbildung}
\inputbeispiel{}
{
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 \zusatzklammer {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.
}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{ M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Äquivalenzrelation}{}{.}
Dann heißt
\mavergleichskettedisp
{\vergleichskette
{ M/R
}
{ \defeq} { { \left\{ [x] \mid x \in M \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die \definitionswort {Quotientenmenge}{} von $R$.
}
Die Quotientenmenge ist also einfach die Menge der Äquivalenzklassen. Wenn man die Äquivalenzrelation mit $\sim$ bezeichnet, so schreibt man
\mathl{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 \anfuehrung{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
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für eine Äquivalenzrelation hat, so ergibt sich eine bijektive Abbildung
\maabb {} {T} {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 \anfuehrung{Richtung}{} einer Geraden, u.s.w.
Im oben angeführten
Beispiel 11.5
besteht die Quotientenmenge aus den Restklassen
\mathl{[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 $\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.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Äquivalenzrelation}{}{}
und $M/R$ die
\definitionsverweis {Quotientenmenge}{}{.}
Die Abbildung
\maabbeledisp {q_R} {M } {M/R
} {x} { [x]
} {,}
heißt \definitionswort {kanonische Projektion}{} von $R$.
}
Man spricht auch von der \stichwort {Identifizierungsabbildung} {,} da unter dieser Abbildung äquivalente Elemente auf das gleiche Element, ihre Klasse, abgebildet werden.
\inputfaktbeweis
{Äquivalenzklassen/Partition/Quotientenmenge/Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $M$ eine Menge und $\sim$ eine
\definitionsverweis {Äquivalenzrelation}{}{}
auf $M$ mit den
\definitionsverweis {Äquivalenzklassen}{}{}
$[x]$ und der
\definitionsverweis {Quotientenmenge}{}{}
\mathl{M/\sim}{.} Dann gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungvier{Es ist
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann, wenn
\mavergleichskette
{\vergleichskette
{ [x]
}
{ = }{ [y]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, und dies gilt genau dann, wenn
\mavergleichskette
{\vergleichskette
{ [x] \cap [y]
}
{ \neq }{\emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \bigcup_{[x] \in M/\sim} [x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist eine
\definitionsverweis {disjunkte Vereinigung}{}{.}
}{Die
\definitionsverweis {kanonische Projektion}{}{}
\maabbeledisp {q} {M} {M/\sim
} {x} { [x]
} {,}
ist
\definitionsverweis {surjektiv}{}{.}
}{Es ist
\mavergleichskette
{\vergleichskette
{q^{-1}([x])
}
{ = }{[x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungvier{Seien
\mathkor {} {x} {und} {y} {}
äquivalent und
\mavergleichskette
{\vergleichskette
{u
}
{ \in }{[x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{u
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und nach der Transitivität auch
\mavergleichskette
{\vergleichskette
{y
}
{ \sim }{u
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also
\mavergleichskette
{\vergleichskette
{u
}
{ \in }{[y]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Damit stimmen die Äquivalenzklassen überein. Die Implikation von der Mitte nach rechts ist klar, da wegen
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Äquivalenzklassen nicht leer sind. Es sei nun
\mavergleichskette
{\vergleichskette
{ [x] \cap [y]
}
{ \neq }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
und sei $z$ ein Element im Durchschnitt. Dann ist
\mathkor {} {x \sim z} {und} {y \sim z} {}
und wegen der Transitivität ist
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Wegen der Reflexivität ist
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{[x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und daher ist
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \bigcup_{[x]\in M/\sim} [x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wegen Teil (1) ist die Vereinigung disjunkt.
}{Die Surjektivität ist klar aufgrund der Definition der Quotientenmenge, und da $x$ auf die Klasse $[x]$ geschickt wird.
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{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]
}
}
{}{}{.}
}
Bei der Eigenschaft (2) sagt man auch, dass die Äquivalenzrelation eine \stichwort {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 \stichwort {universelle Eigenschaft} {} der Quotientenmenge.
\inputfaktbeweis
{Äquivalenzrelation/Quotientenmenge/Universelle Eigenschaft/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $M$ eine Menge und $\sim$ eine
\definitionsverweis {Äquivalenzrelation}{}{}
auf $M$ mit der
\definitionsverweis {Quotientenmenge}{}{}
\mathl{M/\sim}{.} Es sei
\maabb {\varphi} {M} {W
} {}
eine Abbildung mit
\mavergleichskette
{\vergleichskette
{ \varphi(x)
}
{ = }{\varphi(y)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mathkor {} {x,y \in M} {mit} {x \sim y} {.}}
\faktfolgerung {Dann gibt es eine eindeutig bestimmte Abbildung
\maabb {\overline{\varphi}} {M/\sim \, \, } {W
} {}
mit
\mavergleichskette
{\vergleichskette
{ \varphi
}
{ = }{ \overline{\varphi} \circ q
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Sei
\mavergleichskette
{\vergleichskette
{ [x]
}
{ \in }{ M/\sim
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben. Die einzige Möglichkeit für $\overline{\varphi}$ ist
\mavergleichskette
{\vergleichskette
{ \overline{\varphi}([x])
}
{ \defeq }{\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
\mavergleichskette
{\vergleichskette
{[x]
}
{ = }{[y]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist nach der Voraussetzung an $\varphi$ aber
\mavergleichskette
{\vergleichskette
{ \varphi(x)
}
{ = }{\varphi(y)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\inputbemerkung
{}
{
Zu einer Abbildung
\maabb {f} {M} {N
} {}
und der zugehörigen
\definitionsverweis {Äquivalenzrelation}{}{}
$\sim$ im Sinne von
Lemma 10.10
gibt es nach
Lemma 11.13
eine eindeutig bestimmte Abbildung
\maabbdisp {\psi} {M/\sim} {N
} {}
mit
\mavergleichskettedisp
{\vergleichskette
{f
}
{ =} { \psi \circ q
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese ist sogar injektiv.
}
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und $K$ ein
\definitionsverweis {Körper}{}{.}
Wir setzen
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ K^{n+1} \setminus \{0\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Der $K^{n+1}$ ist ein Vektorraum, wobei die Skalarmultiplikation von
\mavergleichskette
{\vergleichskette
{ \lambda
}
{ \in }{K
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{ K^{n+1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{\lambda \cdot x}{} bezeichnet wird. Es sei weiter
\mavergleichskettedisp
{\vergleichskette
{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
\mavergleichskette
{\vergleichskette
{\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
\definitionsverweis {Äquivalenzrelation}{}{}
vorliegt, sieht man so. Die Reflexivität folgt aus
\mavergleichskette
{\vergleichskette
{x
}
{ = }{1x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Zum Nachweis der Symmetrie sei
\mathl{xRy}{,} d.h. es gibt ein
\mavergleichskette
{\vergleichskette
{\lambda
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{\lambda x
}
{ = }{ y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann gilt aber auch
\mavergleichskette
{\vergleichskette
{y
}
{ = }{ \lambda^{-1}x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
da ja $\lambda$ ein Inverses besitzt. Zum Nachweis der Transitivität sei
\mathkor {} {xRy} {und} {yRz} {}
angenommen, d.h. es gibt
\mavergleichskette
{\vergleichskette
{ \lambda , \delta
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathkor {} {\lambda x=y} {und} {\delta y =z} {.}
Dann ist insgesamt
\mavergleichskette
{\vergleichskette
{z
}
{ = }{\delta y
}
{ = }{(\delta \lambda) x
}
{ }{}
{ }{}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ \delta \lambda
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Die
\definitionsverweis {Äquivalenzklassen}{}{}
zu dieser Äquivalenzrelation sind die einzelnen Geraden durch den Nullpunkt
\zusatzklammer {aber ohne den Nullpunkt} {} {.}
Die
\definitionsverweis {Quotientenmenge}{}{}
heißt \stichwort {projektiver Raum} {} über $K$
\zusatzklammer {der Dimension $n$} {} {}
und wird mit ${\mathbb P}^{n}_{K}$ bezeichnet.
}