Kurs:Lineare Algebra (Osnabrück 2017-2018)/Teil II/Vorlesung 45/latex
\setcounter{section}{45}
\zwischenueberschrift{Relationen}
\inputdefinition
{}
{
Es seien
\mathkor {} {X} {und} {Y} {}
Mengen. Eine \definitionswort {Relation}{} zwischen $X$ und $Y$ ist eine Teilmenge
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{ X \times Y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
D.h. bei einer Relation stehen gewisse Paare
\mathl{(x,y)}{} in der gegebenen Relation, und die anderen Paare eben nicht. Man schreibt dafür
\mavergleichskette
{\vergleichskette
{ (x,y)
}
{ \in }{ R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mathl{R (x,y)}{} oder
\mathl{xRy}{.} Bei
\mavergleichskette
{\vergleichskette
{X
}
{ = }{Y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
spricht man von einer Relation auf $X$. Aus der Analysis sind die Ordnungsrelationen bekannt.
\inputdefinition
{}
{
Eine
\definitionsverweis {Relation}{}{}
$\preccurlyeq$ auf einer Menge $I$ heißt \definitionswort {Ordnungsrelation}{} oder \definitionswort {Ordnung}{,} wenn folgende drei Bedingungen erfüllt sind.
\aufzaehlungdrei{Es ist
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt stets
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{i
}
{ = }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
} Die dabei auftretenden Relationseigenschaften heißen der Reihe nach reflexiv, transitiv, antisymmetrisch.
\zwischenueberschrift{Äquivalenzrelationen}
\inputdefinition
{}
{
Eine \definitionswort {Äquivalenzrelation}{} auf einer Menge $M$ ist eine
\definitionsverweis {Relation}{}{}
\mavergleichskette
{\vergleichskette
{ R
}
{ \subseteq }{ M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die die folgenden drei Eigenschaften besitzt
\zusatzklammer {für beliebige
\mavergleichskettek
{\vergleichskettek
{x,y,z
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}
\aufzaehlungdrei{Es ist
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {\definitionswort {reflexiv}{}} {} {.}
}{Aus
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{y
}
{ \sim }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {\definitionswort {symmetrisch}{}} {} {.}
}{Aus
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{y
}
{ \sim }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {\definitionswort {transitiv}{}} {} {.}
}
Dabei bedeutet
\mavergleichskette
{\vergleichskette
{x
}
{ \sim }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
dass das Paar
\mathl{(x,y)}{} zu $R$ gehört.
}
\inputbeispiel{}
{
Das Urbeispiel für eine \definitionsverweis {Äquivalenzrelation}{}{} ist die Gleichheit auf einer beliebigen Menge $M$. Unter der Gleichheit ist jedes Element nur mit sich selbst äquivalent.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Wildebeests_in_the_Masaai_Mara.jpg} }
\end{center}
\bildtext {Gnus bilden eine Äquivalenzklasse bezüglich der Äquivalenzrelation der Gleichartigkeit, ebenso Zebras.} }
\bildlizenz { Wildebeests in the Masaai Mara.jpg } {Demosch} {FlickreviewR} {Flickr} {cc-by-2.0} {Quelle:www.flickr.com/photos/44222307@N00/1191441866/}
\inputbeispiel{}
{
Häufig interessiert man sich gar nicht so genau für einzelne Objekte, sondern nur für bestimmte Eigenschaften davon. Objekte, die sich bezüglich einer bestimmten, genau definierten Eigenschaft gleich verhalten, kann man dann \zusatzklammer {bezüglich dieser Eigenschaft} {} {} als \definitionsverweis {äquivalent}{}{} betrachten. Offenbar handelt es sich dabei um eine Äquivalenzrelation. Wenn man sich beispielsweise nur für die Farbe von Objekten interessiert, so sind alle Objekte, die \zusatzklammer {exakt} {} {} gleichfarbig sind, zueinander äquivalent. Wenn man sich bei Tieren nicht für irgendwelche individuellen Eigenschaften interessiert, sondern nur für ihre Art, so sind gleichartige Tiere äquivalent, d.h. zwei Tiere sind genau dann äquivalent, wenn sie zur gleichen Art gehören. Studierende kann man als äquivalent ansehen, wenn sie die gleiche Fächerkombination studieren. Vektoren kann man als äquivalent ansehen, wenn sie zum Nullpunkt den gleichen Abstand besitzen, etc. Eine Äquivalenzrelation ist typischerweise ein bestimmter Blick auf bestimmte Objekte, der unter Bezug auf eine gewisse Eigenschaft gewisse Objekte als gleich ansieht.
}
Bei den zuletzt genannten \anfuehrung{alltäglichen}{} Beispielen muss man etwas vorsichtig sein, da im Allgemeinen die Eigenschaften nicht so genau definiert werden. Im Alltag spielt Ähnlichkeit eine wichtigere Rolle als Gleichheit hinsichtlich einer bestimmten Eigenschaft. Die Ähnlichkeit ist aber keine Äquivalenzrelation, da sie zwar reflexiv und symmetrisch ist, aber nicht transitiv. Wenn $A$ und $B$ zueinander \zusatzklammer {knapp} {} {} ähnlich sind und $B$ und $C$ ebenso, so kann $A$ und $C$ schon knapp unähnlich sein \zusatzklammer {ebenso: lebt in der Nachbarschaft von, ist verwandt mit, etc.} {} {.}
Die Gleichheit bezüglich einer Eigenschaft wird durch folgende mathematische Konstruktion präzisiert.
\inputbeispiel{}
{
Es seien
\mathkor {} {M} {und} {N} {}
Mengen und sei
\maabb {f} {M} {N
} {}
eine Abbildung. In einer solchen Situation hat man immer eine
\definitionsverweis {Äquivalenzrelation}{}{}
auf dem Definitionsbereich $M$ der Abbildung, und zwar erklärt man zwei Elemente
\mavergleichskette
{\vergleichskette
{ x,y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als äquivalent, wenn sie unter $f$ auf das gleiche Element abgebildet werden, wenn also
\mavergleichskette
{\vergleichskette
{f(x)
}
{ = }{f(y)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Wenn die Abbildung $f$ injektiv ist, so ist die durch $f$ auf $M$ definierte Äquivalenzrelation die Gleichheit. Wenn die Abbildung konstant ist, so sind unter der zugehörigen Äquivalenzrelation alle Elemente aus $M$ untereinander äquivalent.
}
Zu einer Abbildung
\maabb {f} {M} {N
} {}
nennt man übrigens die Menge aller Punkte
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die auf einen bestimmten Punkt
\mavergleichskette
{\vergleichskette
{ z
}
{ \in }{ N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
abgebildet werden, die \stichwort {Faser} {} über $z$. Die Äquivalenzklassen
\zusatzklammer {s.u.} {} {}
sind dann also die Fasern.
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{d
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
fixiert. Wir betrachten auf $\Z$ die
\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. Zwei Zahlen sind also zueinander äquivalent, wenn man von der einen Zahl zu der anderen durch Sprünge der Sprungweite $d$ gelangen kann. Unter Verwendung der
\definitionsverweis {Division mit Rest}{}{}
bedeutet dies, dass zwei Zahlen zueinander äquivalent sind, wenn sie bei Division durch $d$ den gleichen Rest ergeben.
}
\inputbeispiel{}
{
Wir betrachten die \stichwort {Gaußklammer} {}
\zusatzklammer {oder den \anfuehrung{floor}{}} {} {}
einer reellen Zahl, also die Abbildung
\maabbeledisp {\lfloor \,\, \rfloor} {\R} {\Z
} {t} {\lfloor t \rfloor
} {.}
Eine Zahl $t$ wird also auf die größte ganze Zahl abgebildet, die kleiner oder gleich $t$ ist
\zusatzklammer {die \anfuehrung{Vorkommazahl}{}} {} {.}
Dabei wird das gesamte ganzzahlige
\zusatzklammer {also mit ganzzahligen Intervallgrenzen} {} {}
rechtsseitig offene Intervall
\mathl{[n,n+1)}{} auf
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
abgebildet. Bezüglich dieser Abbildung sind also zwei reelle Zahlen genau dann äquivalent, wenn sie im gleichen ganzzahligen Intervall liegen.
Statt der Vorkommazahl kann man auch die \anfuehrung{Nachkommazahl}{} betrachten. Das ist die Abbildung \maabbeledisp {} {\R } { [0,1) } { t } { t-\lfloor t \rfloor } {.} Unter der durch diese Abbildung definierte Äquivalenzrelation sind zwei reelle Zahlen genau dann gleich, wenn sie die gleiche Nachkommazahl besitzen, und das ist genau dann der Fall, wenn ihre Differenz eine ganze Zahl ist.
}
\zwischenueberschrift{Äquivalenzklassen und Repräsentantensysteme}
Eine
\definitionsverweis {Äquivalenzrelation}{}{}
\mavergleichskette
{\vergleichskette
{ R
}
{ \subseteq }{ M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auf einer Menge $M$ kann auch als \stichwort {Zerlegung} {}
\zusatzklammer {\stichwort {Partition} {}} {} {}
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. Jedes Element
\mavergleichskette
{\vergleichskette
{ y
}
{ \in }{ [x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt ein \stichwort {Repräsentant} {} für die Äquivalenzklasse
\mathl{[x]}{.}
\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.
}
\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 {Ostfriesische-Inseln_2.jpg} }
\end{center}
\bildtext {Unter der Äquivalenzrelation \anfuehrung{erreichbar auf dem Landweg}{} sind Inseln und Kontinente die Äquivalenzklassen.} }
\bildlizenz { Ostfriesische-Inseln 2.jpg } {} {Godewind} {Commons} {PD} {}
\inputbeispiel{}
{
Es sei eine Situation gegeben, wo gewisse Orte \zusatzklammer {oder Objekte} {} {} von gewissen anderen Orten aus erreichbar sind oder nicht. Die Erreichbarkeit kann dabei durch die Wahl eines Verkehrsmittels oder durch eine abstraktere \zusatzklammer {Bewegungs} {} {-}Vorschrift festgelegt sein. Solche Erreichbarkeitsrelationen liefern häufig eine Äquivalenzrelation. Dass ein Ort von sich selbst aus erreichbar ist, sichert die Reflexivität. Die Symmetrie der Erreichbarkeit besagt, dass wenn man von $A$ nach $B$ kommen kann, dass man dann auch von $B$ nach $A$ kommen kann. Das ist nicht für jede Erreichbarkeit selbstverständlich, für die meisten aber schon. Die Transitivität gilt immer dann, wenn man die Bewegungsvorgänge hintereinander ausführen kann, also zuerst von $A$ nach $B$ und dann von $B$ nach $C$.
Wenn erreichbar beispielsweise dadurch gegeben ist, dass man auf dem Landweg von einem Ort zu einem anderen kommen kann, so sind zwei Ortspunkte genau dann äquivalent, wenn sie auf der gleichen Insel \zusatzklammer {oder dem gleichen Kontinent} {} {} liegen. Inseln und Kontinente sind dann die \definitionsverweis {Äquivalenzklassen}{}{.} In der Topologie spielt der Begriff des \definitionsverweis {Wegzusammenhangs}{}{} eine wichtige Rolle: Zwei Punkte sind wegzusammenhängend, wenn man sie durch einen stetigen Weg verbinden kann. Oder: Auf den ganzen Zahlen lebe eine Kolonie von Flöhen, und jeder Flohsprung geht fünf Einheiten weit \zusatzklammer {in beide Richtungen} {} {.} Wie viele Flohpopulationen gibt es, welche Flöhe können sich begegnen?
}
\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} {} {.}
}
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Visualisierung_bspl_2-10.gif} }
\end{center}
\bildtext {Visualisierung des Beispiels. Die Äquivalenzklassen bekommen verschiedene Farben.} }
\bildlizenz { Visualisierung bspl 2-10.gif } {} {TiloW} {Commons} {CC-by-sa 3.0} {}
Wir betrachten die
\definitionsverweis {Produktmenge}{}{}
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\N \times \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die wir uns als ein Punktgitter vorstellen. Wir fixieren die Sprünge
\zusatzklammer {man denke an Springmäuse, die alle diese Sprünge ausführen können} {} {}
\mathdisp {\pm (2,0) \text{ und } \pm (3,3)} { , }
und sagen, dass zwei Punkte
\mathl{P=(a,b),\, Q=(c,d) \in M}{} äquivalent sind, wenn man ausgehend von $P$ den Punkt $Q$ mit einer Folge von solchen Sprüngen erreichen kann. Dies ist eine
\definitionsverweis {Äquivalenzrelation}{}{}
\zusatzklammer {dafür ist entscheidend, dass bei den Sprüngen auch der entgegengesetzte Sprung dazu gehört} {} {.}
Typische Fragestellungen sind: Wie kann man äquivalente Felder charakterisieren, wie entscheiden, ob zwei Felder äquivalent sind oder nicht? Wie viele Äquivalenzklassen gibt es überhaupt, gibt es für sie ein schönes Repräsentantensystem?
}
\zwischenueberschrift{Quotientenmenge und kanonische 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$.
}
\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$.
}
Mit Hilfe der Quotientenmenge werden die Äquivalenzklassen zu Elementen einer neuen Menge gemacht. Durch die kanonische Projektion werden äquivalente Elemente miteinander identifiziert. Man spricht daher bei Äquivalenzrelationen auch von der \stichwort {Kunst des Identifizierens} {.} Im praktischen Umgang mit den Quotientenmengen tritt häufig die eigentliche Definition in den Hintergrund und man arbeitet eher mit den intrinsischen Eigenschaften dieser Mengen. Die folgende Aussage besagt insbesondere, dass man jede Äquivalenzrelation wie in Beispiel 45.6 erhalten kann. Äquivalent bedeutet also stets gleich unter einer geeigneten Abbildung.
\inputfaktbeweis
{Äquivalenzklassen/Partition/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}{.}}
\faktuebergang {Dann gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungfuenf{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]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{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} {.}
Dann gibt es eine eindeutig bestimmte Abbildung
\maabb {\overline{\varphi}} {M/\sim \, \, } {W
} {}
mit
\mavergleichskette
{\vergleichskette
{ \varphi
}
{ = }{ \overline{\varphi} \circ q
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungfuenf{Es 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]
}
}
{}{}{.}
}{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)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Wesentliche mathematische Konstruktionen beschreibt man mit Hilfe von Quotientenmengen bezüglich gewisser Äquivalenzrelationen auf einfacheren Mengen. Dafür geben wir zwei Beispiele.
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \R^{n+1} \setminus \{0\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Der
\mathl{\R^{n+1}}{} ist ein reeller Vektorraum, wobei die Skalarmultiplikation von
\mavergleichskette
{\vergleichskette
{ \lambda
}
{ \in }{ \R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ \R^{n+1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathl{\lambda \cdot x}{} bezeichnet wird. Es sei weiter
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ R
}
{ =} { { \left\{ (x,y) \in M \times M \mid \text{ es gibt ein } \lambda \in \R \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
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Zur 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 { reell-projektiver Raum} {}
\zusatzklammer {der reellen Dimension $n$} {} {}
und wird mit ${\mathbb P}^{n}_{\R}$ bezeichnet.
}
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Construction_blackboard _integers.jpg} }
\end{center}
\bildtext {} }
\bildlizenz { Construction blackboard integers.jpg } {Construction blackboard integers} {Darapti} {Commons} {CC-by-sa 3.0} {}
Es sei $\N$ die Menge der natürlichen Zahlen und
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \N \times \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die
\definitionsverweis {Produktmenge}{}{}
mit der komponentenweisen Addition\zusatzfussnote {Passende Interpretationen für die Paare in diesem Kontext sind beispielsweise: Das Paar $(a,b)$ repräsentiert das Ergebnis eines Fußballspieles, wobei $a$ die Toranzahl der Heimmannschaft und $b$ die Toranzahl der Gastmannschaft repräsentiert, oder: Das Paar $(a,b)$ repräsentiert das Alter eines menschlichen Paares, wobei $a$ für das Alter der Frau und $b$ für das Alter des Mannes steht. Der Übergang zu den Äquivalenzklassen bedeutet dann, sich nur noch für die Tordifferenz bzw. den Altersunterschied zu interessieren, nicht mehr für das genaue Ergebnis bzw. das Alter der einzelnen Personen. Man kann auch das Paar als eine Schrittfolge aus $a$ Schritten nach rechts und $b$ Schritten nach links ansehen} {.} {.}
Wir erklären auf $M$ eine
\definitionsverweis {Relation}{}{}
durch
\mathdisp {(a,b) \sim (c,d), \text{ falls } a+d =b+c} { . }
Dies ist bei
\mavergleichskette
{\vergleichskette
{a
}
{ \leq }{c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann der Fall, wenn es ein
\mavergleichskette
{\vergleichskette
{ e
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {nämlich
\mavergleichskettek
{\vergleichskettek
{ e
}
{ = }{ c-a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
mit
\mavergleichskettedisp
{\vergleichskette
{ (c,d)
}
{ =} { (a,b)+ (e,e)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt. D.h. die beiden Paare unterscheiden sich um ein Diagonalelement, also um ein Paar, wo beide Komponenten übereinstimmen. Diese Relation ist eine Äquivalenzrelation auf $M$, siehe
Aufgabe 45.22.
Wenn man
\mathl{\N \times \N}{} als ein quadratisches Gitter anordnet
\zusatzklammer {das ist ein \anfuehrung{diskretes Koordinatensystem}{}} {} {,}
so sind die Äquivalenzklassen durch die Punkte auf einer zur Diagonalen parallelen \anfuehrung{diskreten Geraden}{} gegeben. Die Punkte
\mathl{(a,b)}{} mit
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind äquivalent zu
\mathl{(a-b,0)}{,} sie haben also einen Repräsentanten, bei dem die zweite Komponente $0$ ist. Die Punkte
\mathl{(a,b)}{} mit
\mavergleichskette
{\vergleichskette
{a
}
{ \leq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind äquivalent zu
\mathl{(0, b-a)}{,} sie haben also einen Repräsentanten, bei dem die erste Komponente $0$ ist. Die Punkte
\mathl{(a,a)}{} sind zu
\mathl{(0,0)}{} äquivalent. Den Repräsentanten einer Äquivalenzklasse, bei dem mindestens eine Komponente $0$ ist, nennen wir den \stichwort {Standardvertreter} {} dieser Äquivalenzklasse. Die Standardvertreter sind die diskreten Punkte des begrenzenden Viertelkreuzes; zu einem Punkt ergibt sich der Standardvertreter, wenn man parallel zur Diagonalen in Richtung der Halbachsen wandert, bis man auf einer der Halbachsen landet. Zwei Punkte sind genau dann äquivalent, wenn sie den gleichen Standardvertreter besitzen.
Wir bezeichnen nun die
\definitionsverweis {Quotientenmenge}{}{,}
also die Menge der Äquivalenzklassen unter dieser Äquivalenzrelation, als
\definitionswortenp{Menge der ganzen Zahlen}{} und bezeichnen sie mit $\Z$. Jede ganze Zahl hat dann genau einen Standardvertreter der Form
\mavergleichskette
{\vergleichskette
{ n
}
{ \defeq }{ (n,0)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
der Form
\mavergleichskette
{\vergleichskette
{ 0
}
{ \defeq }{ (0,0)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder der Form
\mavergleichskette
{\vergleichskette
{ -n
}
{ \defeq }{ (0,n)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Eine natürliche Zahl $n$ fassen wir von nun an als die ganze Zahl
\mathl{(n,0)}{} auf.
Wir wollen nun zwei ganze Zahlen, also zwei solche Äquivalenzklassen
\mathkor {} {[(a,b)]} {und} {[(c,d)]} {}
miteinander \anfuehrung{addieren}{,} also eine Verknüpfung $\oplus$ auf $\Z$ einführen. Der naheliegende Ansatz ist, diese Verknüpfung mittels der komponentenweisen Addition als
\mavergleichskettedisp
{\vergleichskette
{ [(a,b)] \oplus [(c,d)]
}
{ \defeq} {[ (a+c, b+d) ]
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
zu definieren. Hier tritt das Problem der \stichwort {Wohldefiniertheit} {} auf, denn die Verknüpfung wird erklärt unter Bezug auf Repräsentanten, und es ist nicht von vornherein klar, dass unterschiedliche Repräsentanten zum gleichen Ergebnis führen. Wenn also
\mavergleichskette
{\vergleichskette
{ (a,b)
}
{ \sim }{ (a',b')
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ (c,d)
}
{ \sim }{ (c',d')
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind, so muss man überprüfen, dass
\mavergleichskettedisp
{\vergleichskette
{ (a+c,b+d)
}
{ \sim} { (a'+c', b'+d')
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und damit
\mavergleichskette
{\vergleichskette
{ [ (a+c, b+d) ]
}
{ = }{[ (a'+c', b'+d') ]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Dies ist der Fall, siehe
Aufgabe 45.23.
Man kann weiterhin zeigen, dass die so definierte Verknüpfung auf $\Z$
\definitionsverweis {assoziativ}{}{}
und
\definitionsverweis {kommutativ}{}{}
ist, dass
\mathl{[(0,0)]}{} das
\definitionsverweis {neutrale Element}{}{}
der Verknüpfung ist und dass es zu jedem Element
\mathl{[(a,b)]}{} ein
\definitionsverweis {inverses Element}{}{}
gibt, nämlich
\mathl{[(b,a)]}{.}
Wir definieren nun eine Multiplikation auf $\Z$ durch
\mavergleichskettedisp
{\vergleichskette
{ [(a,b)] \cdot [(c,d)]
}
{ \defeq} {[(ac+bd, ad+bc)]
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dies ist wieder wohldefiniert und man kann zeigen, dass die Multiplikation assoziativ und kommutativ ist mit
\mavergleichskette
{\vergleichskette
{ 1
}
{ = }{ [(1,0)]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als neutralem Element und dass das Distributivgesetz gilt.
}