3.14 Relationen *
3.14.1 Definition
Die Definitionen aus diesem Abschnitt kann man zunächst überspringen. Thematisch gehören sie aber dennoch ins Grundlagenkapitel und sind daher hier einsortiert. Zum Teil kommen die Begriffe in den Ergänzungen vor, jedenfalls implizit. In der Linearen Algebra 2 werden wir dann noch einmal darauf zurückkommen.
Sofern man von einer Relation zwischen \(X\) und \(Y\) keine weiteren Eigenschaften kennt, ist der Begriff eher uninteressant (und es gäbe keinen Grund, dafür eine eigene Bezeichnung einzuführen). Der Sinn der Sache ist, Relationen zu betrachten, die durch zusätzliche Eigenschaften besonders ausgezeichnet sind. Dabei gibt es mehrere Arten von Eigenschaften, die es zu betrachten lohnt.
Ein wichtiges Beispiel haben wir bereits gesehen: Eine Abbildung \(X\to Y\) ist eine Relation zwischen \(X\) und \(Y\) mit der Eigenschaft, dass für jedes \(x\in X\) genau ein \(y\in Y\) existiert, so dass \((x, y)\in R\).
In den folgenden beiden Abschnitten betrachten wir bestimmte Relationen zwischen einer Menge \(X\) und sich selbst, also Teilmengen von \(X\times X\). Einerseits die Äquivalenzrelationen, die dazu dienen, Objekte zusammenzufassen, die zwar nicht unbedingt gleich, aber doch gleichartig sind, was gewisse Eigenschaften angeht. Andererseits (partielle) Ordnungen, die beschreiben, wie man Elemente einer Menge vergleichen und anordnen kann.
3.14.2 Äquivalenzrelationen
Sei \(R\subseteq X\times X\) eine Relation. Oft wählt man ein Symbol, zum Beispiel \(\sim \) und definiert \(x\sim y\) als \((x,y )\in R\). Wir sagen dann auch, dass \(\sim \) eine Relation auf \(X\) sei.
Sei \(\sim \) eine Relation auf einer Menge \(X\).
Die Relation \(\sim \) heißt reflexiv, wenn für alle \(x\in X\) gilt: \(x\sim x\).
Die Relation \(\sim \) heißt symmetrisch, wenn für alle \(x, y\in X\) genau dann \(x\sim y\) gilt, wenn \(y\sim x\) gilt.
Die Relation \(\sim \) heißt transitiv, wenn für alle \(x, y, z\in X\) mit \(x\sim y\) und \(y\sim z\) gilt, dass \(x\sim z\).
Die Relation \(\sim \) heißt eine Äquivalenzrelation, wenn sie reflexiv, symmetrisch und transitiv ist.
Ist \(X\) eine Menge, so ist Gleichheit \(=\) eine Äquivalenzrelation.
Sei \(X\subset \mathbb Z\times \mathbb Z\) die Menge aller Paare von ganzen Zahlen \((a, b)\) mit \(b\ne 0\). Wir definieren für \((a, b), (c, d)\in X\):
Dies ist offenbar eine Relation zwischen \(X\) und \(X\). Es ist nicht schwierig nachzuprüfen, dass es sich um eine Äquivalenzrelation handelt. (Sie sollten das zur Übung tun.) Siehe Beispiel 3.72 für die Fortsetzung dieses Beispiels. Wenn Ihnen dieses Beispiel ziemlich künstlich vorkommt, dann ist das in Ordnung, aber Sie sollten gerade dann auch Beispiel 3.72 bis zum Ende lesen.
Sei \(\sim \) eine Äquivalenzrelation auf \(X\). Wir sagen dann, \(y\in X\) sei äquivalent zu \(x\), wenn \(x\sim y\) gilt. Für \(x\in X\) nennen wir
die Menge aller Elemente, die bezüglich \(\sim \) in Relation zu \(x\) stehen, die Äquivalenzklasse von \(x\). Oft schreibt man \([x]\) für die Äquivalenzklasse von \(x\).
Sei \(X=\mathbb Z\) die Menge der ganzen Zahlen. Wir definieren für \(x, y\in \mathbb Z\):
Dies ist offenbar eine Relation zwischen \(\mathbb Z\) und \(\mathbb Z\). Man prüft leicht nach, dass es sich um eine Äquivalenzrelation handelt. (Sie sollten das zur Übung tun.) Oft schreibt man \(x\equiv y\mod 3\) statt \(x\sim y\).
In diesem Fall gibt es drei Äquivalenzklassen: Erstens die Teilmenge von \(\mathbb Z\), die aus allen Zahlen besteht, die durch \(3\) teilbar sind; zweitens die Teilmenge aller Zahlen, die bei Division durch \(3\) Rest \(1\) haben. Und drittens die Teilmenge derjenigen Zahlen, die bei Division durch \(3\) Rest \(2\) haben. Die Äquivalenzklassen für diese spezielle Äquivalenzrelation nennt man auch Restklassen modulo \(3\).
Siehe Beispiel 3.73 für die Fortsetzung dieses Beispiels.
Aus Reflexivität, Symmetrie und Transitivität der Äquivalenzrelation folgt, dass je zwei Elemente einer Äquivalenzklasse zueinander äquivalent sind. Außerdem gilt: Ist \(y\) in der Äquivalenzklasse von \(x\) enthalten und gilt \(y\sim z\), so liegt auch \(z\) in der Äquivalenzklasse von \(x\); das ist einfach eine Umformulierung der Transitivität.
Sei \(\sim \) eine Äquivalenzrelation auf \(X\). Seien \(A, B \subseteq X\) Äquivalenzklassen. Dann gilt entweder \(A = B\) oder \(A\cap B = \emptyset \).
Mit anderen Worten: Zwei Äquivalenzklassen sind entweder gleich (die gleiche Teilmenge von \(X\)) oder disjunkt.
Wir zeigen, dass aus \(A\cap B\ne \emptyset \) folgt, dass \(A = B\). Sei dazu \(x\in A\cap B\). Ist dann \(y\in A\), so folgt \(x\sim y\) (denn \(x, y\in A\)) und damit \(y\in B\) (denn \(x\in B\) und \(B\) ist eine Äquivalenzklasse).
Ist \(A\subseteq X\) eine Äquivalenzklasse (bezüglich \(\sim \)) und ist \(x\in A\), so nennt man \(x\) einen Repräsentanten der Äquivalenzklasse. Dann gilt \(A = \{ y\in X;\ y\sim x\} \).
Wir bezeichnen mit \(X/{\sim }\) die Menge aller Äquivalenzklassen. Dies ist also eine Menge, deren Elemente Teilmengen von \(X\) sind. Die Abbildung \(X\to X/{\sim }\), \(x\mapsto [x]\), die jedes Element von \(X\) auf seine Äquivalenzklasse abbildet, bezeichnet man auch als die kanonische Projektion. Per Definition ist diese Abbildung surjektiv, aber in aller Regel nicht injektiv: Denn für \(x\sim y\) gilt ja \([x]=[y]\), also haben äquivalente Elemente \(x\) und \(y\) dasselbe Bild unter dieser Abbildung.
Um eine Abbildung \(f\) von der Menge \(X/{\sim }\) in eine Menge \(Y\) zu definieren, gibt man \(f([x])\) oft an, indem man \(x\) verwendet. Weil für \(x\sim y\) aber \([x] = [y]\) gilt und deswegen \(f([x]) = f([y])\) gelten muss, ist das problematisch. Wenn die »Formel« für \(f([x])\) wirklich von \(x\) abhängt und für \(y\) mit \(y\sim x\) ein anderes Ergebnis liefern würde, dann hätten wir gar keine Zuordnung definiert. Siehe Beispiel 3.72 für Beispiele. Wenn die gegebene Vorschrift für alle Elemente der Äquivalenzklasse dasselbe Ergebnis liefert, also unabhängig ist von der Wahl des Repräsentanten der Äquivalenzklasse, dann sagt man, die Vorschrift sei wohldefiniert. Oft sagt man auch, die Abbildung sei wohldefiniert.
Wir nehmen wieder die Notation von Beispiel 3.69 auf. Wir hatten eine Äquivalenzrelation \(\sim \) auf der Menge aller Paare \((a,b)\) von ganzen Zahlen mit \(b\ne 0\) definiert. Wir bezeichnen mit \(Q\) die Menge der Äquivalenzklassen, also \(Q = \left.\left(\mathbb Z\times (\mathbb Z\setminus \{ 0\} \right) \middle / \sim \right.\). Wir wollen als erstes die im vorherigen Absatz angesprochene Problematik (Stichwort »wohldefiniert«) aufgreifen.
Betrachten wir die Vorschrift \([(a,b)] \mapsto a+b\). Definiert diese eine Abbildung \(f\colon Q\to \mathbb Z\)? Nein, denn die Vorschrift ist nicht wohldefiniert! Es gilt nämlich zum Beispiel \((1,1) \sim (2,2)\), also \([(1,1)] = [(2,2)]\), aber nicht \(1+1 = 2+2\).
Die Vorschrift \([(a,b)] \mapsto \frac ab\) ist hingegen wohldefiniert, denn wenn \((a,b) \sim (c,d)\), dann bedeutet das \(ad = cb\), also tatsächlich \(\frac ab = \frac cd\). Wir erhalten so eine Abbildung \(i\colon Q\to \mathbb Q\).
Die folgende Vorschrift ist ein anderes Beispiel für eine wohldefinierte Zuordnung, und zwar ordnen wir jedem Paar von Elementen in \(Q\) ein neues Element in \(Q\) zu:
Wir haben hier die Wohldefiniertheit schon vorweggenommen und so getan, als hätten wir schon eine Abbildung \(Q\times Q\to Q\) in der Hand. Wir müssen sie aber natürlich überprüfen. Sei also \([(a,b)] = [(a^\prime , b^\prime )]\), das bedeutet \(ab^\prime = ba^\prime \), und \([(c,d)] = [(c^\prime , d^\prime )]\), das heißt \(cd^\prime = dc^\prime \). Dann gilt tatsächlich \([(ac, bd)] = [(a^\prime c^\prime , b^\prime d^\prime )]\), denn das heißt ja genau, dass \((ac, bd) \sim (a^\prime c^\prime , b^\prime , d^\prime )\), und wir haben
In ähnlicher Weise definieren wir eine Abbildung \(A\colon Q\times Q\longrightarrow Q\):
Wieder muss man überprüfen, dass diese Vorschrift wohldefiniert ist, also dass im Fall \([(a,b)] = [(a^\prime , b^\prime )]\), das bedeutet \(ab^\prime = ba^\prime \), und \([(c,d)] = [(c^\prime , d^\prime )]\) auch \([(ad+bc, bd)] = [(a^\prime d^\prime +b^\prime c^\prime , b^\prime d^\prime )]\) gilt. Führen Sie diese Rechnung durch.
Um das Beispiel abzuschließen, führen wir noch die Notationen
ein, wir betrachten also \(M\) und \(A\) als Multiplikation und Addition auf der Menge \(Q\).
Wir kommen nun noch einmal auf die Abbildung \(i\colon Q\to \mathbb Q\) zurück. Sie hat die folgenden Eigenschaften:
\(i\) ist bijektiv,
\(i([(a,b)] + [(c,d)]) = i([(ad+bc, bd)]) = \frac{ad+bc}{bd} = \frac ab + \frac cd = i([(a,b)]) + i([(c,d)])\)
\(i([(a,b)] \cdot [(c,d)]) = i([(ac, bd)]) = \frac{ac}{bd} = \frac ab \cdot \frac cd = i([(a,b)]) \cdot i([(c,d)])\)
Zur ersten Aussage: Die Surjektivität ist klar, denn jedes Element von \(\mathbb Q\) hat die Form \(\frac ab\) für geeignete ganze Zahlen \(a\) und \(b\ne 0\), und \(\frac ab = i[(a,b)]\). Zur Injektivität: Wenn \(i([a,b]) = i([c,d])\), also \(\frac ab = \frac cd\), dann gilt \(ad = bc\). Das bedeutet aber \((a,b)\sim (c,d)\), also \([(a,b)] = [(c,d)]\).
Das bedeutet, dass die Abbildung \(i\) eine Identifikation von \(Q\) und \(\mathbb Q\) erlaubt, die mit Addition und Multiplikation verträglich ist. Eine andere Sichtweise ist, dass wir eine Konstruktion der rationalen Zahlen ausgehend von den ganzen Zahlen kennengelernt haben, denn wenn wir \(\mathbb Q\) noch nicht kennen würden, ist die Menge \(Q\) mit den Rechenoperationen, die wir definiert haben, ein vollwertiger Ersatz.
Wir nehmen wieder die Notation von Beispiel 3.70 auf.
Die Ausführungen hier sind etwas skizzenhaft. Betrachten Sie das Beispiel als erweiterte Übungsaufgabe und/oder melden Sie sich, wenn Sie gerne weitere Details hätten.
Wie üblich bezeichnen wir die Äquivalenzklasse von \(x\) mit \([x]\). Wir hatten schon festgestellt, dass \(\left.\mathbb Z\middle / \sim \right. = \{ [0], [1], [2] \} \) gilt. (Die eckigen Klammern haben hier eine andere Bedeutung als in Abschnitt 3.13.)
Eine interessante Beobachtung ist, dass man mit Restklassen modulo \(3\) (das war unser Name für die Äquivalenzklassen in diesem Beispiel) ähnlich rechnen kann wie ganzen Zahlen: Für alle \(x,x^\prime , y, y^\prime \in \mathbb Z\) mit \(x\sim x^\prime \) und \(y\sim y^\prime \) gilt
also
Ähnlich wie in Beispiel 3.72 (aber sogar noch einfacher) haben wir also eine wohldefinierte Addition und Multiplikation auf der Menge der Äquivalenzklassen, die gegeben ist durch
Wir dürfen also, salopp gesagt, die Rechenzeichen \(+\) und \(\cdot \) beliebig in die oder aus den eckigen Klammern ziehen.
Ein paar Beispielrechnungen:
|
\([10] = [1]\) |
denn \(10\) hat bei Division durch \(3\) Rest \(1\), |
|
\([100] = [1]\) |
denn \(100\) hat bei Division durch \(3\) Rest \(1\), |
|
oder wir rechnen \([100] = [10 \cdot 10] = [10] \cdot [10] = [1] \cdot [1] = [1\cdot 1] = [1]\), |
|
|
\([10^i] = [1]\) |
für alle \(i\in \mathbb N\), mit einem ähnlichen Argument, |
und
denn
Die letzte Rechnung lässt sich offensichtlich auf beliebige natürliche Zahlen verallgemeineren und zeigt: Eine natürliche Zahl hat denselben Rest bei Division durch \(3\) wie ihre Quersumme (die Summe aller ihrer Ziffern).
Insbesondere haben wir das bekannte Kriterium für Teilbarkeit durch \(3\) bewiesen: Eine natürliche Zahl ist genau dann durch \(3\) teilbar, wenn ihre Quersumme durch \(3\) teilbar ist.
Können Sie diese Betrachtungen auf den Fall \(n=9\) übertragen? Was ist zum Beispiel im Fall \(n=7\) anders?
Vergleiche Abschnitt 4.2.1.
Zum Schluss wollen wir noch zwei etwas andere Sichtweisen auf den Begriff der Äquivalenzrelation angeben (was hoffentlich unterstreicht, dass es sich vom Prinzip her um etwas sehr einfaches handelt).
Ist \(f\colon X\to Y\) eine (surjektive) Abbildung, so wird durch
eine Äquivalenzrelation auf \(X\) definiert. Umgekehrt hat jede Äquivalenzrelation diese Form, denn man kann für \(f\) die kanonische Projektion auf die Menge aller Äquivalenzklassen verwenden.
Ist \(\sim \) eine Äquivalenzrelation, so bilden die Äquivalenzklassen eine Familie von paarweise disjunkten Teilmengen von \(X\), deren Vereinigung ganz \(X\) ist.
Ist umgekehrt eine solche Darstellung von \(X = \bigcup _{i\in I} X_i\) als Vereinigung von paarweise disjunkten nicht-leeren Teilmengen \(X_i\) gegeben, so können wir eine Äquivalenzrelation auf \(X\) definieren durch
3.14.3 Partielle und totale Ordnungen
Sei \(X\) eine Menge und \(\preceq \) eine Relation zwischen \(X\) und sich selbst.
Ein wichtiger Punkt (und das soll durch das Wort partiell betont werden) ist, dass es in der Situation der Definition Elemente \(x, y\) geben kann, für die weder \(x\preceq y\) noch \(y\preceq x\) gilt. In der Situation des Beispiels ist das in der Tat klar: Sind \(A, B\subseteq M\) Teilmengen, dann kann es passieren, dass weder \(A\subseteq B\) noch \(B\subseteq A\) gilt.
Sei \(X\) eine Menge und \(\preceq \) eine Relation zwischen \(X\) und sich selbst.
Mit anderen Worten: Eine totale Ordnung ist eine partielle Ordnung, bezüglich derer je zwei Elemente stets »vergleichbar« sind, d.h. in Relation stehen (in der einen oder anderen Reihenfolge).
Die übliche \(\le \)-Relation ist eine totale Ordnung auf der Menge der reellen Zahlen (und ebenso auf \(\mathbb Q\), \(\mathbb Z\), \(\mathbb N\)).
Sei \(\preceq \) eine partielle Ordnung auf \(X\).
Ein Element \(x\in X\) heißt minimales Element (bezüglich \(\preceq \)), wenn für alle \(y\in X\) mit \(y\preceq x\) gilt: \(y=x\).
Ein Element \(x\in X\) heißt kleinstes Element (bezüglich \(\preceq \)), wenn für alle \(y\in X\) gilt: \(x\preceq y\).
Ein Element \(x\in X\) heißt maximales Element (bezüglich \(\preceq \)), wenn für alle \(y\in X\) mit \(x\preceq y\) gilt: \(y=x\).
Ein Element \(x\in X\) heißt größtes Element (bezüglich \(\preceq \)), wenn für alle \(y\in X\) gilt: \(y\preceq x\).
Im allgemeinen muss es weder minimale noch maximale Elemente (und erst recht kein kleinstes oder größtes Element) geben; betrachten Sie zum Beispiel die \(\le \)-Ordnung auf \(\mathbb Z\).
Wenn es ein kleinstes Element (bezüglich einer partiellen Ordnung) gibt, dann ist dieses eindeutig bestimmt (und ist ein minimales Element). Wenn es ein eindeutig bestimmtes minimales Element gibt, dann ist dieses das kleinste Element. Entsprechendes gilt für maximale Elemente und das größte Element.
Wenn \(\preceq \) eine totale Ordnung ist, dann fallen die Begriffe des minimalen Elements und des kleinsten Elements zusammen; ebenso die Begriffe des maximalen und des größten Elements.
Wir betrachten auf \(\mathbb N\) die Relation \(d\, |\, n\) der Teilbarkeit. Dies ist eine partielle Ordnung. Für alle \(n\in \mathbb N\) gilt \(1\, |\, n\), also ist \(1\) das kleinste Element in \(\mathbb N\) bezüglich der Teilbarkeitsordnung. Weil \(n\, |\, 0\) für alle \(n\) gilt, ist \(0\) das größte Element in \(\mathbb N\) für diese partielle Ordnung!
Für natürliche Zahlen \(a, b\) ist \(ggT(a,b)\) das größte Element (bezüglich Teilbarkeit) der Menge aller positiven gemeinsamen Teiler von \(a\) und \(b\). Mit dieser Beschreibung ist es nicht notwendig, den Fall \(a=b=0\) gesondert zu betrachten.
Um das zu beweisen, müssen wir zeigen, dass jeder gemeinsame Teiler \(d\) von \(a\) und \(b\) auch ein Teiler von \(\operatorname{ggT}(a,b)\) ist. Das folgt aus Lemma 3.53, das besagt, dass wir \(\operatorname{ggT}(a,b) = xa+yb\) schreiben können (mit ganzen Zahlen \(x\) und \(y\)).
In der Menge \(\{ 2, 3, 5, 7, 11, \dots \} \) der Primzahlen ist jedes Element gleichzeitig minimal und maximal bezüglich Teilbarkeit. Es gibt weder ein kleinstes noch ein größtes Element.