Relationen – Analysis

1.6 Relationen

In diesem Abschnitt besprechen wir Relationen auf Mengen. Mit Relationen werden wir im Gegensatz zum vorherigen Abschnitt in der Lage sein, zum Beispiel die Menge der rationalen Zahlen formal korrekt aus den ganzen Zahlen (und mit etwas mehr Arbeit auch aus den natürlichen Zahlen) zu konstruieren.

Definition 1.58 (Relationen).

Seien $X$ und $Y$ Mengen. Eine Relation auf $X \times Y$ ist eine Teilmenge $ℛ \subseteq X \times Y$ . Wir schreiben auch $x ℛ y$ falls $(x, y) \in ℛ$ und verwenden oft Symbole wie $<, ≪, \leq, ≅, \equiv, \sim$ für Relationen. Falls $X = Y$ ist, dann sprechen wir auch von einer Relation auf $X$ . Wenn $\sim$ (resp. $≅$ , …) eine Relation ist, dann schreiben wir auch „ $x ≁ y$ “ (resp. „ $x ≇ y$ “, …) für „ $\neg (x \sim y)$ “ (resp. „ $\neg (x ≅ y)$ “, …).

Zum Beispiel sind $<$ und $\leq$ Relationen auf $ℕ$ , die wir mittels der Addition auf $ℕ$ folgendermassen definieren könnten: Wir schreiben $m < n$ für $m, n \in ℕ$ falls es ein $k \in ℕ$ mit $m + k = n$ gibt, und wir schreiben $m \leq n$ falls $m = n$ oder $m < n$ gilt.

Übung 1.59 (Eine bekannte Relation).

In einem gewissen Sinne haben wir schon eine gewisse Klasse von Relationen betrachtet. Seien $X, Y$ Mengen und sei $𝒢$ eine Relation auf $X \times Y$ , die die folgende Eigenschaft erfüllt:

\begin{array}{l} \forall x \in X \exists! y \in Y : x 𝒢 y \end{array}

Wie nennen wir eine solche Relation gemeinsam mit $X$ und $Y$ ? Welches Symbol verwenden wir statt dem Symbol $𝒢$ in diesem Zusammenhang?

Des Weiteren beschreibt die folgende Definition eine wichtige Klasse von Relationen:

Definition 1.60 (Äquivalenzrelationen).

Eine Relation $\sim$ auf $X$ ist eine Äquivalenzrelation, falls folgende drei Eigenschaften erfüllt sind:

•

Reflexivität:

\forall x \in X : x \sim x

•

Symmetrie:

\forall x, y \in X : x \sim y \Rightarrow y \sim x

•

Transitivität:

\forall x, y, z \in X : ((x \sim y) \land (y \sim z)) \Rightarrow x \sim z

Äquivalenzrelationen sind oft durch eine Gleichheit in gewissen Aspekten definiert und sollten als eine Form von einer Gleichheit angesehen werden. In der Tat bezieht sich der Ausdruck „das Gleiche“ in der deutschen Sprache auf eine Art „Äquivalenzrelation“ (die je nach Zusammenhang verschieden sein kann), wohingegen der Ausdruck „dasselbe“ nur für „ein und dasselbe“ Objekt verwendet werden sollte.

Beispiel 1.61 (Beispiele von Äquivalenzrelationen).

(i): Das einfachste Beispiel einer Äquivalenzrelation auf einer beliebigen Menge $X$ ist die Gleichheit, also die Relation $ℛ = {(x, y) \in X^{2} ∣ x = y}$ .
(ii): Ein weiteres allgemeines Beispiel ist die sogenannte triviale Relation $ℛ = X^{2}$ , bezüglich der je zwei Elemente in $X$ äquivalent sind.
(iii): Wir betrachten ein Beispiel in der ebenen (euklidschen) Geometrie. Sei $X$ die Menge der Geraden in der Ebene. Zu zwei Geraden $G_{1}, G_{2}$ schreiben wir $\begin{array}{l} G_{1} \sim G_{2} \Leftrightarrow G_{1} und G_{2} sind parallel . \end{array}$
Dies definiert eine Äquivalenzrelation auf $X$ (wieso?).
(iv): Äquivalenzrelationen werden in anderen Wissenschaften oder auch im Alltag häufig verwendet. Beispielsweise kann man auf der Menge aller Lebewesen eine Äquivalenzrelation definieren, in dem man zwei Lebewesen für äquivalent erklärt, wenn sie zur selben Art (oder Gattung oder Familie) gehören.

Übung 1.62 (Zwei weitere Beispiele).

In dieser Übungen möchten wir zwei weitere Beispiele von Äquivalenzrelationen besprechen. Sei $X$ eine Menge.

(i): (Quetschen einer Teilmenge) Sei $A \subseteq X$ eine Teilmenge. Zeigen Sie, dass die Relation gegeben durch $\begin{array}{l} x \sim_{A} y : \Leftrightarrow (x, y \in A) \lor (x = y) \end{array}$
für $x, y \in X$ eine Äquivalenzrelation auf $X$ definiert.
(ii): (Äquivalenz über eine Abbildung) Sei $f : X \to Y$ eine Abbildung in eine weitere Menge $Y$ . Wir definieren eine Relation auf $X$ durch $\begin{array}{l} x_{1} \sim_{f} x_{2} : \Leftrightarrow f (x_{1}) = f (x_{2}) \end{array}$
für alle $x_{1}, x_{2} \in X$ . Zeigen Sie, dass $\sim$ eine Äquivalenzrelation auf $X$ definiert.

Übung 1.63 (Ein falscher Beweis).

In dieser Aufgabe behaupten wir fälschlicherweise, dass jede symmetrische und transitive Relation $\sim$ auf einer Menge $X$ auch reflexiv ist (d.h. eine Äquivalenzrelation ist). Finden Sie den Fehler in folgendem „Beweis“ :

Sei $x \in X$ ein Element. Sei $y \in X$ , so dass $x \sim y$ . Wegen Symmetrie der Relation gilt also auch $y \sim x$ . Folglich gilt unter Verwendung der Transitivität der Relation $(x \sim y) \land (y \sim x) \Rightarrow x \sim x$ , was zu zeigen war.

Finden Sie ein Beispiel einer Relation, die symmetrisch und transitiv, aber nicht reflexiv ist.

Übung 1.64 (Beispiele allgemeiner Relationen).

Finden Sie eine Relation auf den natürlichen Zahlen $ℕ$ , die von den Eigenschaften einer Äquivalenzrelation

•

nur die Symmetrie,

•

nur die Transitivität,

•

die Reflexivität und die Transitivität, aber nicht die Symmetrie

erfüllt.

Wie schon erwähnt ist eine Äquivalenzrelation gewissermassen eine Form von Gleichheit. Dies lässt sich auch formalisieren:

Definition 1.65 (Äquivalenzklassen und die Quotientenmenge).

Sei $\sim$ eine Äquivalenzrelation auf einer Menge $X$ . Dann wird für $x \in X$ die Menge

\begin{array}{l} {[x]}_{\sim} = {y \in X ∣ y \sim x} \end{array}

die Äquivalenzklasse von $x$ genannt. Weiters ist

\begin{array}{l} X / \sim = {{[x]}_{\sim} ∣ x \in X} \end{array}

der Quotient (oder die Quotientenmenge) von $X$ modulo $\sim$ . Ein Element $x \in X$ wird auch Repräsentant seiner Äquivalenzklasse ${[x]}_{\sim}$ genannt.

Anschaulich gesprochen geben wir äquivalente Elemente von $X$ in ein und denselben Topf und nicht äquivalente Elemente in verschiedene Töpfe. In diesem Bild besteht die Äquivalenzklasse eines Elements aus allen Elementen, die im gleichen Topf sind. Der Quotient modulo $\sim$ wiederum ist die Menge der Töpfe. Die Begriffe der Äquivalenzrelation und der Partition in Definition 1.51 sind auf folgende Weise eng verwandt.

Proposition 1.66 (Korrespondenz zwischen Äquivalenzrelationen und Partitionen).

Sei $X$ eine Menge. Dann entsprechen Äquivalenzrelationen auf $X$ und Partitionen von $X$ einander im folgenden Sinne: Für eine gegebene Äquivalenzrelation $\sim$ auf $X$ ist die Menge

\begin{array}{l} 𝒫_{\sim} = {{[x]}_{\sim} ∣ x \in X} \end{array}

eine Partition von $X$ . Umgekehrt definiert für eine Partition $𝒫$ von $X$

\begin{array}{l} x \sim_{𝒫} y \Leftrightarrow \exists P \in 𝒫 : x \in P \land y \in P \end{array}

für $x, y \in X$ eine Äquivalenzrelation auf $X$ . Des Weiteren sind die Konstruktion der Partition aus der Äquivalenzrelation und die Konstruktion der Äquivalenzrelation aus der Partition zueinander invers: Für jede Partition $𝒫$ von $X$ gilt $𝒫_{\sim_{𝒫}} = 𝒫$ und für jede Äquivalenzrelation $\sim$ auf $X$ gilt $\sim_{𝒫_{\sim}} = \sim$ .

Sei $X$ eine Menge, $\sim$ eine Äquivalenzrelation auf $X$ und $𝒫_{\sim}$ wie in Proposition 1.66 definiert. Selbstverständlich gilt nach den Definitionen eigentlich $𝒫_{\sim} = X ∕ \sim$ . Wir möchten jedoch zwei verschiedene Symbole mitführen, da wir $𝒫_{\sim}$ und $X ∕ \sim$ jeweils verschieden interpretieren möchten. $𝒫_{\sim}$ werden wir stets als eine Kollektion von Teilmengen von $X$ auffassen; $X ∕ \sim$ hingegen werden wir als einen neuen Raum erachten, wo die Punkte durch Identifikation („Aneinanderkleben“) von gewissen Punkten in $X$ entstanden sind. (Die Punkte in $X ∕ \sim$ sind die Teilmengen von $X$ , die in $𝒫_{\sim}$ enthalten sind).

Applet 1.67 (Eine Äquivalenzrelation und deren Quotient).

Links wird eine Menge $X$ partitioniert, was einer Äquivalenzrelation $\sim$ auf $X$ entspricht. Rechts betrachten wir die Menge der Äquivalenzklassen, also den Quotienten von $X$ bzüglich $\sim$ . Die Menge links könnte eine abstrakte Menge darstellen oder den Einheitskreis. Im letzteren Fall muss klar definiert sein, zu welcher Menge die Punkte der Kanten, bei denen der Kreis unterteilt wird, gehören. Wir haben dies im Beispiel mit Farben angedeutet.

Übung 1.68 (Zwei Quotienten).

Charakterisieren Sie die Äquivalenzklassen der beiden in Übung 1.62 (ii) definierten Äquivalenzrelation $\sim$ . Zeigen Sie jeweils, dass $𝒫_{\sim}$ (wie in obiger Proposition definiert) eine Partition ist (ohne auf die noch nicht-bewiesene Proposition zurückzugreifen) und beschreiben Sie $X ∕ \sim$ intuitiv.

Für den Beweis der Proposition 1.66 ziehen wir folgende Behauptung vor:

Behauptung.

Sei $\sim$ eine Äquivalenzrelation auf $X$ . Dann sind folgende drei Aussagen für alle $x, y \in X$ (paarweise) äquivalent:

(i): $x \sim y$
(ii): ${[x]}_{\sim} = {[y]}_{\sim}$
(iii): ${[x]}_{\sim} \cap {[y]}_{\sim} \neq {}$

Beweis der Behauptung. Wir beweisen die Implikationen $(i) \Rightarrow (i i) \Rightarrow (i i i) \Rightarrow (i)$ , woraus folgt, dass alle drei Aussagen äquivalent sind. Seien $x, y \in X$ .

Wir nehmen also zuerst an, dass $x \sim y$ gilt wie in $(i)$ . Sei $z \in {[x]}_{\sim}$ . Dann ist $z \sim x \sim y$ und also $z \sim y$ und $z \in {[y]}_{\sim}$ wegen der Transitivität. Die andere Inklusion folgt analog (durch Vertauschen von $x$ und $y$ ) und es gilt ${[x]}_{\sim} = {[y]}_{\sim}$ wie in $(i i)$ .

Gilt ${[x]}_{\sim} = {[y]}_{\sim}$ wie in $(i i)$ , so folgt ${[x]}_{\sim} \cap {[y]}_{\sim} \neq {}$ wie in $(i i i)$ wegen Reflexivität.

Gilt ${[x]}_{\sim} \cap {[y]}_{\sim} \neq {}$ wie in $(i i i)$ , so existiert ein $z \in X$ mit $z \sim x$ und $z \sim y$ . Aus Symmetrie und Transitivität folgt daher $x \sim y$ wie in $(i)$ . □

Beweis von Proposition 1.66. Sei $\sim$ eine Äquivalenzrelation auf $X$ . Dann gilt $⋃_{P \in 𝒫_{\sim}} P = ⋃_{x \in X} {[x]}_{\sim} = X$ , da $x \in {[x]}_{\sim}$ für jedes $x \in X$ . Paarweise Disjunktheit der Elemente von $𝒫_{\sim}$ gilt dank der Behauptung und es folgt, dass $𝒫_{\sim}$ eine Partition ist.

Sei nun $𝒫$ eine Partition von $X$ und sei die Relation $\sim_{𝒫}$ wie in der Proposition definiert. Es ist für jedes $x \in X$ auch $x \sim_{𝒫} x$ , da es wegen $⋃_{P \in 𝒫} P = X$ ein $P \in 𝒫$ gibt mit $x \in P$ ; dies zeigt Reflexivität. Falls $x \sim_{𝒫} y$ für $x, y \in X$ , dann folgt $y \sim_{𝒫} x$ direkt aus der Definition, das heisst $\sim_{𝒫}$ ist symmetrisch. Angenommen es gilt $x \sim_{𝒫} y$ und $y \sim_{𝒫} z$ . Dann gibt es ein Partitionselement $P_{1} \in 𝒫$ mit $x, y \in P_{1}$ und $P_{2} \in 𝒫$ mit $y, z \in P_{2}$ . Insbesondere ist $P_{1} \cap P_{2} \neq {}$ und daher $P_{1} = P_{2}$ nach den Eigenschaften der Partition. Es folgt $x, z \in P_{1}$ , $x \sim_{𝒫} z$ und die Transitivität der Relation $\sim_{𝒫}$ . Daher ist $\sim_{𝒫}$ eine Äquivalenzrelation.

Für $x \in X$ ist die Äquivalenzklasse bezüglich $\sim_{𝒫}$ gegeben durch

\begin{array}{l} {[x]}_{\sim_{𝒫}} = {y \in X ∣ y \sim_{𝒫} x} = ⋃_{P \in 𝒫 \land x \in P} P \end{array}

Da aber die Elemente von $𝒫$ paarweise disjunkt sind, kann $x$ nur in einem Element enthalten sein. Insbesondere folgt, dass ${[x]}_{\sim_{𝒫}} \in 𝒫$ das eindeutig bestimmte Element der Partition $𝒫$ ist, das $x$ enthält, und $𝒫_{\sim_{𝒫}} \subseteq 𝒫$ . Ist $P \in 𝒫$ und $x \in P$ , so gilt ${[x]}_{\sim_{𝒫}} = P$ , also $𝒫_{\sim_{𝒫}} = 𝒫$ .

Ist umgekehrt $\sim$ eine Äquivalenzrelation auf $X$ und $𝒫_{\sim}$ die entsprechende Partition, dann gilt für alle $x, y \in X$

\begin{array}{l} x \sim_{𝒫_{\sim}} y \Leftrightarrow {[x]}_{\sim} = {[y]}_{\sim} \Leftrightarrow x \sim y \end{array}

nach der Definition von $\sim_{𝒫_{\sim}}$ und der Behauptung. □

Man verwendet Quotienten modulo Äquivalenzrelationen in der Mathematik oft für die Konstruktion von gewissen Räumen und auch von neuen Zahlenmengen. Wir betrachten zu letzterem ein einfaches und grundlegendes Beispiel: Wir konstruieren die rationalen Zahlen aus den ganzen Zahlen.

Beispiel 1.69 (Konstruktion der rationalen Zahlen).

Wir nehmen an, dass wir bereits die ganzen Zahlen $ℤ$ und die Addition und Multiplikation auf $ℤ$ mit allen üblichen Eigenschaften kennen und wollen damit die rationalen Zahlen $ℚ$ definieren. Zu diesem Zwecke betrachten wir die Relation $\sim$ auf $ℤ \times (ℤ ∖ {0})$ definiert durch

\begin{array}{l} (m_{1}, m_{2}) \sim (n_{1}, n_{2}) \Leftrightarrow m_{1} n_{2} = n_{1} m_{2} \end{array}

für $(m_{1}, m_{2}), (n_{1}, n_{2}) \in ℤ \times (ℤ ∖ {0})$ . Diese Definition rührt daher, dass wir rationale Zahlen als Brüche von ganzen Zahlen auffassen möchten. Dabei müssen wir allerdings solche identifizieren, die „nach Kürzen“ gleich sind; zum Beispiel sollte gelten $\frac{10}{6} = \frac{5}{3}$ . Allerdings wollen wir hier davon ausgehen, dass wir die rationalen Zahlen noch nicht kennen, weswegen wir anstatt Gleichungen der Form $\frac{m_{1}}{m_{2}} = \frac{n_{1}}{n_{2}}$ Gleichungen der Form $m_{1} n_{2} = n_{1} m_{2}$ mit Ausdrücken innerhalb von $ℤ$ betrachten (im Beispiel $10 \cdot 3 = 5 \cdot 6$ ).

Nun verifzieren wir, dass obige Relation tatsächlich eine Äquivalenzrelation ist. Seien dazu $(m_{1}, m_{2}), (n_{1}, n_{2}), (q_{1}, q_{2}) \in ℤ \times (ℤ ∖ {0})$ .

•

Reflexivität:

(m_{1}, m_{2}) \sim (m_{1}, m_{2})

, denn

m_{1} m_{2} = m_{1} m_{2}

•

Symmetrie: Angenommen es gilt

(m_{1}, m_{2}) \sim (n_{1}, n_{2})

. Dann ist per Definition also

m_{1} n_{2} = n_{1} m_{2}

, was

n_{1} m_{2} = m_{1} n_{2}

und daher auch

(n_{1}, n_{2}) \sim (m_{1}, m_{2})

impliziert.

•

Transitivität:

(m_{1}, m_{2}) \sim (n_{1}, n_{2})

und

(n_{1}, n_{2}) \sim (q_{1}, q_{2})

ergibt

m_{1} n_{2} = n_{1} m_{2}

und

n_{1} q_{2} = q_{1} n_{2}

. Durch Multiplikation der ersten Gleichungen mit

q_{2}

und der zweiten Gleichung mit

m_{2}

erhalten wir

\begin{array}{l} m_{1} n_{2} q_{2} = n_{1} m_{2} q_{2} = q_{1} n_{2} m_{2} . \end{array}

Da $n_{2}$ nicht Null ist, können wir in obiger Gleichung $n_{2}$ Wegstreichen (was eine der Eigenschaften von $ℤ$ ist und $ℚ$ nicht verwendet), womit sich $m_{1} q_{2} = q_{1} m_{2}$ und damit $(m_{1}, m_{2}) \sim (q_{1}, q_{2})$ ergibt.

Der Quotient $(ℤ \times (ℤ ∖ {0})) ∕ \sim$ kann nun als Definition der rationalen Zahlen $ℚ$ angesehen werden. Für eine Äquivalenzklasse ${[(m_{1}, m_{2})]}_{\sim} \in ℚ$ schreibt man wie üblich $\frac{m_{1}}{m_{2}}$ . Damit gilt nun die Gleichung

\frac{q m_{1}}{q m_{2}} = \frac{m_{1}}{m_{2}}

für $m_{1} \in ℤ$ und $q, m_{2} \in ℤ ∖ {0}$ . In der Tat bezeichnen nach Definition beide Seiten Äquivalenzklassen und die Gleichung gilt genau wenn

(q m_{1}, q m_{2}) \sim (m_{1}, m_{2})

oder äquivalenterweise $q m_{1} m_{2} = m_{1} q m_{2}$ erfüllt ist. Da letzteres gilt, erfüllen damit die so definierten rationalen Zahlen die üblichen Erweiterungs- und Kürzungsregeln.

Des Weiteren lässt sich $ℤ$ als Teilmenge von $ℚ$ auffassen. In der Tat ist die Abbildung

\begin{array}{l} ℤ \to ℚ, m \mapsto \frac{m}{1} \end{array}

injektiv, denn die Gleichung $\frac{m}{1} = \frac{n}{1}$ ist für $m, n \in ℤ$ per Definition genau dann erfüllt, wenn $m = n$ ist. Wir identifizieren $ℤ$ mit dem Bild obiger Abbildung und schreiben insbesondere $\frac{m}{1} = m$ für $m \in ℤ$ .

Wir wollen kurz zu allgemeinen Quotienten zurückkehren, also sei $X$ eine Menge und $\sim$ eine Äquivalenzrelation auf $X$ . Häufig will man eine Funktion auf $X ∕ \sim$ unter Verwendung der Elemente von $X$ (also der Repräsentanten der Äquivalenzklassen) definieren. Zum Beispiel möchten wir in obigem Beispiel in der Lage sein, zusätzliche Abbildungen auf $ℚ$ zu definieren (unter anderem die Addition und die Multiplikation).

Konkreter, wenn $Y$ eine weitere Menge ist und $f : X \to Y$ eine Funktion ist, wollen wir möglicherweise durch

\begin{array}{l} \bar{f} : X / \sim \to Y, {[x]}_{\sim} \mapsto f (x) \end{array}

eine Funktion definieren. Dies ist aber nur dann möglich, wenn $x_{1} \sim x_{2}$ für $x_{1}, x_{2} \in X$ (also ${[x_{1}]}_{\sim} = {[x_{2}]}_{\sim}$ ) auch $f (x_{1}) = f (x_{2})$ impliziert. In diesem Fall ist $\bar{f} ({[x]}_{\sim})$ unabhängig von der Wahl des Repräsentanten $x$ der Äquivalenzklasse ${[x]}_{\sim}$ . Also definiert dies in der Tat eine Funktion $\bar{f}$ , die jedem Element ${[x]}_{\sim}$ des Definitionsbereichs $X ∕ \sim$ ein eindeutig bestimmtes Element $\bar{f} ({[x]}_{\sim})$ zuordnet. Zur Betonung dieser (für Funktionen notwendiger) Eigenschaft sagen wir in diesem Fall, dass $\bar{f}$ wohldefiniert ist.

Übung 1.70 (Addition und Multiplikation auf den rationalen Zahlen).

Wir definieren nun zusätzliche Strukturen auf $ℚ$ . Zeigen Sie, dass die Abbildungen

\begin{array}{l} + : ℚ \times ℚ \to ℚ, (\frac{m}{n}, \frac{p}{q}) \mapsto \frac{m}{n} + \frac{p}{q} = \frac{m q + n p}{n q} \end{array}

und

\begin{array}{l} \cdot : ℚ \times ℚ \to ℚ, (\frac{m}{n}, \frac{p}{q}) \mapsto \frac{m}{n} \cdot \frac{p}{q} = \frac{m p}{n q} \end{array}

wohldefiniert sind. Verifizieren Sie des Weiteren die Rechenregeln

\begin{array}{l} \frac{m}{n} \cdot \frac{n}{m} = 1, \frac{a}{b} + \frac{- a}{b} = 0 \end{array}

für $m, n, b \in ℤ ∖ {0}$ und $a \in ℤ$ . Sie dürfen in dieser Aufgabe zwar alle üblichen Rechenregeln und Eigenschaften von $ℤ$ verwenden, aber nicht jene von $ℚ$ (da wir letztere ja definieren wollen).