Kurs:Vorkurs Mathematik (Osnabrück 2009)/Vorlesung 3/latex
\setcounter{section}{3}
\zwischenueberschrift{Relationen}
Sei $P$ eine Menge von Personen und $E$ eine Menge von Eigenschaften, die eine Person haben kann oder auch nicht, und zwar sollen hier nur solche Eigenschaften betrachtet werden, wo es nur die beiden Möglichkeiten des Zukommens oder des Nichtzukommens gibt. Die Gesamtinformation, welche der beteiligten Personen welche Eigenschaft besitzt, kann man dann auf verschiedene Arten ausdrücken. Man kann beispielsweise eine Liste von allen zutreffenden Person-Eigenschafts-Paaren erstellen, also \einrueckung{(Anna, klug), (Hans, schön), (Berta, schön), (Hans, lustig), (Anna, lustig)} oder man kann zu jeder Person die ihr zukommenden Eigenschaften auflisten, also \einrueckung{Anna: klug, lustig} \einrueckung{Berta: schön}\einrueckung{Hans: schön, lustig} oder umgekehrt zu einer Eigenschaft die Personen auflisten, die diese Eigenschaft erfüllen, also \einrueckung{Schön: Berta, Hans} \einrueckung{Klug: Anna} \einrueckung{Lustig: Anna, Hans}
Man kann auch das ganze in eine Tabelle schreiben, wo die eine Leiste die Personen und die andere Leiste die Eigenschaften repräsentiert, und dann diejenigen Kreuzungspunkte, die eine zutreffende Beziehung repräsentieren, ankreuzen, also
\tabelleviervier {\zeileundvier {} {Anna} {Berta} {Hans} }
{\zeileundvier {Schön} {} {x} {x} }
{\zeileundvier {Klug} {x} {} {} }
{\zeileundvier {Lustig} {x} {} {x} }
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {AnnaBertaHans.png} }
\end{center}
\bildtext {} }
\bildlizenz { AnnaBertaHans.png } {} {MGausmann} {Commons} {CC-by-da 4.0} {}
Eine weitere Möglichkeit besteht darin, die Information durch ein Verbindungsdiagramm auszudrücken, bei dem Person und Eigenschaft genau dann durch eine Strecke oder eine Kurve verbunden werden, wenn die Eigenschaft zutrifft.
Der mathematische Begriff, um Beziehungen zwischen den Elementen von zwei Mengen zu beschreiben, heißt Relation:
\inputdefinition
{}
{
Es seien \mathkor {} {M} {und} {N} {}
Mengen. Eine \definitionswort {Relation}{} $R$ zwischen den Mengen
\mathkor {} {M} {und} {N} {}
ist eine
\definitionsverweis {Teilmenge}{}{}
der
\definitionsverweis {Produktmenge}{}{}
\mathl{M \times N}{,} also
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{ M \times N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Statt $(x,y) \in R$ schreibt man häufig auch $R(x,y)$ oder $xRy$ und sagt, dass \anfuehrung{ $x$ in Relation $R$ zu $y$ steht.}{} Typische mathematische Relationen sind: ist gleich, ist größer als, ist Teilmenge von, ist disjunkt zu, usw.
Wenn
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{ M \times N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Relation ist, so heißt für jedes
\mathl{m \in M}{} die Menge\zusatzfussnote {In einer solchen Situation sagt man manchmal: \anfuehrung{für jedes feste $m$}{} oder \anfuehrung{für jedes beliebige, aber feste $m$.}{} Damit deutet man an, dass es in
\mathl{N_m={ \left\{ y \in N \mid R(m,y) \right\} }}{} zwischen den beiden Variablen
\mathkor {} {m} {und} {y} {}
einen Unterschied gibt, da in der Gesamtdefinition $m$ zwar variabel, innerhalb der Menge aber fest ist, wohingegen $y$ auch innerhalb der Menge variabel ist} {} {}
\mavergleichskettedisp
{\vergleichskette
{ N_m
}
{ =} { { \left\{ y \in N \mid R(m,y) \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die \stichwort {Faser} {} durch $m$ und für jedes
\mathl{n \in M}{} heißt die Menge
\mavergleichskettedisp
{\vergleichskette
{ M_n
}
{ =} { { \left\{ x \in M \mid R(x,n) \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die Faser durch $n$.
\inputbeispiel{
}
{
Es sei $S$ die Menge der Städte und $A$ die Menge der Autobahnen. Dann ist die Beziehung \anfuehrung{liegt an}{} eine Relation $L$ zwischen
\mathkor {} {S} {und} {A} {.}\zusatzfussnote {Hier wird die Relation inhaltlich erklärt und es wird ihr zugleich sozusagen im Vorbeigehen die Bezeichnung $L$ gegeben} {} {} Zwischen einer Stadt
\mavergleichskette
{\vergleichskette
{s
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und einer Autobahn
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bedeutet
\mathdisp {sLa \text{ oder } L(s,a)} { }
einfach, dass die konkrete Stadt $s$ an der Autobahn $a$ liegt. Zu $s$ ist dann die Menge
\mavergleichskettedisp
{\vergleichskette
{A_s
}
{ =} { { \left\{ a \in A \mid L(s,a) \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die Menge der Autobahnen, an denen $s$ liegt, und zu
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{S_a
}
{ =} { { \left\{ s \in S \mid L(s,a) \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die Teilmenge der Städte, an denen die Autobahn $a$ vorbeifährt. Für $s=\text{Osnabr}\ddot {\rm u}\text{ck}$ ergibt sich also
\mavergleichskettedisp
{\vergleichskette
{ A_{\text{Osnabr}\ddot {\rm u}\text{ck} }
}
{ =} { \{A1,A30,A33\}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und für die $A1$ ergibt sich
\mavergleichskettedisp
{\vergleichskette
{ S_{A1}
}
{ =} {\{\ldots, \text{Hamburg}, \text{Bremen}, \text{Osnabr}\ddot {\rm u}\text{ck}, \ldots \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Relation wird vollständig beschrieben, wenn man zu jeder Stadt die daran vorbeiführenden Autobahnen oder aber wenn man zu jeder Autobahn die daran liegenden Städte aufführt. Genauso gut kann man die Relation durch eine Tabelle ausdrücken mit einer Leitzeile für die Autobahnen und einer Leitspalte für die Städte, und wo im Kreuzungspunkt
\mathl{(s,a)}{} ein Kreuz gemacht wird genau dann, wenn
\mathl{L(s,a)}{} gilt. Die Aussage
\mathdisp {\forall s (\exists a L(s,a))} { }
bedeutet, dass jede Stadt an einer Autobahn liegt
\zusatzklammer {wohl falsch} {} {}
und die Aussage
\mathdisp {\forall a (\exists s L(s,a))} { }
bedeutet, dass jede Autobahn an mindestens einer Stadt vorbeiführt
\zusatzklammer {wohl wahr} {} {.}\zusatzfussnote {Hier werden die Variablen ohne expliziten Bezug auf eine Menge, in der sie sich bewegen dürfen, angegeben. Dies steckt aber implizit in der Variablenbenennung drin, das $s$ soll auf Stadt und das $a$ auf Autobahn hindeuten} {} {}
}
\inputbeispiel{}
{
Es sei $M$ eine Menge und $P$ die
\definitionsverweis {Potenzmenge}{}{}
von $M$. Dann wird auf
\mathl{M \times P}{} die \stichwort {Inzidenzrelation} {} $I$ erklärt durch
\mathdisp {I(x,T) \text{ genau dann, wenn } x \in T} { . }
Die Inzidenzrelation drückt also aus, ob ein Element $x$ zu einer bestimmten Teilmenge $T$ gehört oder nicht. Die Faser zu einem Element besteht aus sämtlichen Teilmengen, die dieses Element enthalten, und die Faser zu einer Teilmenge besteht aus allen Elementen dieser Teilmenge.
}
\inputbeispiel{}
{
Es sei
\mavergleichskette
{\vergleichskette
{E
}
{ = }{\R^2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die reelle Ebene und $G$ die Menge aller Geraden in der Ebene. Die
\definitionsverweis {Produktmenge}{}{}
\mathdisp {E \times G} { }
besteht aus allen Paaren
\mathl{(P,g)}{,} wobei $P$ ein Punkt der Ebene und $g$ eine Gerade ist. Es gibt mehrere Möglichkeiten, eine Gerade zu beschreiben, und damit auch mehrere Möglichkeiten, ein solches Paar zu beschreiben. Beispielsweise ist
\mathdisp {((2,-5), { \left\{ (u,v) \mid 4u-3v = 6 \right\} })} { }
ein Paar, wobei der Punkt vorne durch die beiden Koordinaten und die Gerade hinten durch eine Geradengleichung angegeben wird. Bei einem solchen Paar besteht keine Bedingung zwischen dem Punkt und der Geraden.
Die \stichwort {Inzidenzrelation} {} zwischen Punkten und Geraden wird ausgedrückt durch
\mavergleichskettedisp
{\vergleichskette
{I
}
{ =} { { \left\{ (P,g) \in E \times G \mid P \text{ liegt auf } g \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Statt \anfuehrung{liegt auf}{} kann man auch einfach
\mavergleichskette
{\vergleichskette
{P
}
{ \in }{g
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schreiben.
}
\zwischenueberschrift{Relationen auf einer Menge}
Im obigen Beispiel gab es einerseits Personen und andererseits Eigenschaften, die diese Personen haben konnten oder nicht. Die beiden beteiligten Mengen hatten also eine unterschiedliche Funktion. Wenn man aber z.B. zwischenmenschliche Beziehungen ausdrücken möchte, so stimmen die beiden Mengen überein, und es ergeben sich neuartige strukturelle Möglichkeiten, da ein Element sowohl vorne als auch hinten stehen kann. Betrachten wir in der studentischen Dreier-WG die Relation \anfuehrung{kann gut leiden}{.} Die zugehörige Relationstabelle sieht vielleicht so aus.
\tabelleviervier {\zeileundvier {} {Anna} {Berta} {Hans} }
{\zeileundvier {Anna} {} {x} {x} }
{\zeileundvier {Berta} {x} {x} {} }
{\zeileundvier {Hans} {x} {x} {x} }
Hier ist zunächst wichtig, die Bedeutung der Spalte und der Zeile festzulegen; sagen wir, dass die Tabelle so zu verstehen ist, dass in der Leitspalte das grammatische Subjekt und in der Leitzeile das grammatische Objekt steht. Damit besagt die Tabelle, dass Hans alle Personen der WG gut leiden kann, dass Berta sich und Anna gut leiden kann, aber nicht Hans, und dass Anna ihre beiden Mitbewohner gut leiden kann, aber nicht sich selbst. Die Relation ist also weder \anfuehrung{reflexiv}{,} da sich Anna nicht gut leiden kann, noch \anfuehrung{symmetrisch}{,} da Hans zwar Berta gut leiden kann, aber nicht umgekehrt.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Relacion_binaria_11.svg} }
\end{center}
\bildtext {Ein Pfeildiagramm ist eine Möglichkeit, eine Relation darzustellen.} }
\bildlizenz { Relación binaria 11.svg } {} {HiTe} {Commons} {PD} {}
\inputdefinition
{}
{
Eine \definitionswort {Relation}{} $R$ auf einer Menge $M$ ist eine Teilmenge der Produktmenge
\mathl{M \times M}{,} also
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Wenn ein Paar
\mathl{(x,y)}{} zu $R$ gehört, so sagt man auch, dass $x$ und $y$ in der Relation $R$ stehen. Statt
\mathl{(x,y) \in R}{} verwendet man häufig suggestivere Schreibweisen wie
$xRy,\, x \sim y$ oder $x \leq y$.
Dabei werden manche Symbole nur verwendet, wenn die Relation gewisse zusätzliche Eigenschaften erfüllt. Die wichtigsten Eigenschaften fasst die folgende Definition zusammen
\zusatzklammer {die bei zwei verschiedenen Mengen keinen Sinn ergeben} {} {.}
\inputdefinition
{}
{
Es sei $M$ eine Menge und
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Relation}{}{}
auf $M$. Man nennt $R$
\auflistungvier{\definitionswort {reflexiv}{,} wenn
\mavergleichskette
{\vergleichskette
{(x,x)
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt für alle
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{\definitionswort {transitiv}{,} wenn für beliebige
\mavergleichskette
{\vergleichskette
{x,y,z
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus
\mathkor {} {(x,y) \in R} {und aus} {(y,z) \in R} {}
stets
\mavergleichskette
{\vergleichskette
{(x,z)
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt.
}{\definitionswort {symmetrisch}{,} wenn für beliebige
\mavergleichskette
{\vergleichskette
{x,y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus
\mavergleichskette
{\vergleichskette
{(x,y)
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auch
\mavergleichskette
{\vergleichskette
{(y,x)
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt.
}{\definitionswort {antisymmetrisch}{,} wenn für beliebige
\mavergleichskette
{\vergleichskette
{x,y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus
\mathkor {} {(x,y) \in R} {und} {(y,x) \in R} {}
die Gleichheit
\mavergleichskette
{\vergleichskette
{x
}
{ = }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt.
}
}
Wir besprechen nun verschiedene mathematische Relationen, die mit diesen Eigenschaften definiert werden können.
\zwischenueberschrift{Ordnungsrelationen}
Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie
\mathl{\geq, \leq,\preccurlyeq, \subseteq}{} verwendet.
\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
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
Eine Menge mit einer fixierten Ordnung darauf heißt \stichwort {geordnete Menge} {.} Wenn zusätzlich gilt, dass für je zwei Elemente \mathkor {} {x \preccurlyeq y} {oder} {y \preccurlyeq x} {} gilt, so spricht man von einer \stichwort {total geordneten Menge} {.}
\inputbeispiel{}
{
Die reellen Zahlen $\R$ \zusatzklammer {ebenso die rationalen Zahlen und die ganzen Zahlen} {} {} sind \definitionsverweis {total geordnet}{}{} durch die \stichwort {Größergleichrelation} {} $\geq$. Dies gehört zum Begriff des angeordneten Körpers, der nicht nur verlangt, dass eine totale Ordnung erklärt ist, sondern auch, dass diese mit den algebraischen Operationen verträglich ist. Die strikte \stichwort {Größerrelation} {} $>$ ist keine Ordnungsrelation, da sie nicht reflexiv ist. Der Körper der komplexen Zahlen ${\mathbb C}$ ist nicht angeordnet \zusatzklammer {und lässt sich auch nicht anordnen} {} {.}
}
\inputbeispiel{}
{
Wir betrachten die positiven ganzen Zahlen $\N_+$ zusammen mit der Teilbarkeitsbeziehung. Man sagt, dass eine Zahl $k$ die Zahl $n$ teilt, geschrieben
\mathdisp {k {{|}} n} { , }
wenn es eine weitere natürliche Zahl $m$ mit
\mavergleichskette
{\vergleichskette
{n
}
{ = }{km
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt. Die Bezeichnung ist nicht sonderlich glücklich gewählt, da ein symmetrisches Symbol für eine nichtsymmetrische Relation verwendet wird. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets
\mathl{n{{|}}n}{} ist, wie
\mavergleichskette
{\vergleichskette
{m
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zeigt. Die Transitivität sieht man so: sei
\mathkor {} {k {{|}} n} {und} {n{{|}}m} {}
mit
\mathkor {} {n =ak} {und} {m=bn} {.}
Dann ist
\mavergleichskette
{\vergleichskette
{m
}
{ = }{bn
}
{ = }{bak
}
{ }{
}
{ }{
}
}
{}{}{}
und daher $k{{|}}m$. Die Antisymmetrie folgt so: Aus
\mathkor {} {n=ak} {und} {k=bn} {}
folgt
\mavergleichskette
{\vergleichskette
{n
}
{ = }{(ab)n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Da wir uns auf positive natürliche Zahlen beschränken, folgt
\mavergleichskette
{\vergleichskette
{ab
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und daraus
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ = }{1
}
{ }{
}
{ }{
}
}
{}{}{.}
Also ist
\mavergleichskette
{\vergleichskette
{k
}
{ = }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Einfache Beispiele wie \mathkon { 2 } { und } { 3 }{ } zeigen, dass hier keine
\definitionsverweis {totale Ordnung}{}{}
vorliegt, da weder $2$ von $3$ noch umgekehrt geteilt wird.
}
\inputbeispiel{}
{
Es sei $M$ eine beliebige Menge und
\mavergleichskette
{\vergleichskette
{ R
}
{ = }{ \mathfrak {P} \, (M )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die
\definitionsverweis {Potenzmenge}{}{}
davon. Dann sind die Elemente aus
\mavergleichskette
{\vergleichskette
{ R
}
{ = }{ \mathfrak {P} \, ( M )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzgs {also die Teilmengen von $M$} {}
durch die Inklusionsbeziehung $\subseteq$
\definitionsverweis {geordnet}{}{.}
Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus
\mavergleichskette
{\vergleichskette
{T_1
}
{ \subseteq }{T_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{T_2
}
{ \subseteq }{T_3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Inklusion
\mavergleichskette
{\vergleichskette
{T_1
}
{ \subseteq }{T_3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen
\mathl{T_1, T_2}{} sind genau dann gleich, wenn
\mathkor {} {T_1 \subseteq T_2} {und umgekehrt} {T_2 \subseteq T_1} {}
gilt.
}
\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.
}
\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$.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Wildebeests_in_the_Masaai_Mara.jpg} }
\end{center}
\bildtext {Gnus bilden eine Äquivalenzklasse bzgl. 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 (knapp) ähnlich sind und $B$ und $C$ ebenso, so kann $A$ und $C$ schon knapp unähnlich sein (ebenso: lebt in der Nachbarschaft von, ist verwandt mit, etc.).
\inputbeispiel{}
{
Es sei $M$ die Menge aller \stichwort {Dreiecke} {} \zusatzklammer {in der reellen Ebene} {} {.} Zwei Dreiecke \mathkor {} {D_1} {und} {D_2} {} heißen \stichwort {kongruent} {,} wenn es eine \zusatzklammer {eventuell uneigentliche} {} {} \stichwort {Bewegung} {} gibt, die das eine Dreieck in das andere Dreieck überführt. Eine Bewegung soll dabei die Längen und die Winkel erhalten. Eine solche Bewegung setzt sich zusammen aus einer Verschiebung, einer Achsenspiegelung und einer Drehung \zusatzklammer {in beliebiger Reihenfolge, beliebig oft angewendet} {} {.} Die Kongruenz von Dreiecken ist eine Äquivalenzrelation. Ein Dreieck ist zu sich selbst kongruent, da es durch die identische Bewegung in sich überführt wird. Wenn $D_1$ durch eine bestimmte Bewegung $\beta$ in $D_2$ überführt wird, so wird durch die entgegengesetzte Bewegung, also $\beta^{-1}$, das zweite Dreieck $D_2$ in $D_1$ überführt. Die Kongruenz ist also symmetrisch. Wenn drei Dreiecke $D_1,D_2,D_3$ gegeben sind, wobei $D_1$ zu $D_2$ und $D_2$ zu $D_3$ kongruent sind, so gibt es eine Bewegung $\beta$, die $D_1$ in $D_2$ überführt, und eine Bewegung $\gamma$, die $D_2$ in $D_3$ überführt. Dann hat die Gesamtbewegung $\gamma \circ \beta$ die Eigenschaft, dass sie insgesamt $D_1$ in $D_3$ überführt. Ebenso ist die \stichwort {eigentliche Kongruenz} {,} bei der nur eigentliche Bewegungen \zusatzklammer {also keine Achsenspiegelungen} {} {} erlaubt sind, eine Äquivalenzrelation.
}
\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?
}