Äquivalenzrelationen – Analysis I (Kap. 1-9)

1.6 Äquivalenzrelationen

In diesem Abschnitt besprechen wir Relationen auf Mengen. Mit dem Begriff der Äquivalenzrelation 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)$ “, …).

Der Begriff der Relation umfasst viele verschiedene Beispiele, die in verschiedene Typen von Relation eingeteilt werden können. Um diese Allgemenheit zu ermöglichen, ist obige Definition eher abstrakt formuliert. Wir werden aber für den allgemeinen Begriff keinerlei theoretischen Überlegungen anstellen. Stattdessen wollen wir nur kurz einige bekannte Beispiele von Relation besprechen und anschliessend einen wichtigen speziellen Typ von Relationen genauer untersuchen.

Beispiel 1.59 (Beispiele von Relationen).

(i): 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.
(ii): Ebenso können wir $<$ und $\leq$ auch als Relationen auf $ℝ$ auffassen. In der Tat werden wir die Relation $\leq$ mittels unserem Axiomensytem der reellen Zahlen im nächsten Kapitel einführen und dabei nochmals ihre wichtigsten Eigenschaften besprechen. Im Sinne der obigen Definition sollten Sie $\leq$ mit der Teilmenge von $ℝ^{2}$ in Figur 1.12 identifizieren. Denn $(x, y) \in ℝ^{2}$ erfüllt $x \leq y$ genau dann wenn der Punkt auf oder links von der Diagonale liegt.

$PIC$

Figur 1.12: Dies stellt die $\leq$ -Relation als Teilmenge von $ℝ \times ℝ$ dar.
(iii): Manchmal verwendet man auch eine Relation $\approx$ , die ausdrücken soll, dass zwei Zahlen in etwa gleich sind. Um diese Relation† Obwohl wir hier ein schwammiges „Ungefähr-Gleich“ betrachten, benötigen wir eine präzise Definition um darüber sprechen zu können. zu definieren, wählen wir eine fix gewählte positive Konstante $δ > 0$ . Mit dieser defineren wir die Relation $\approx_{δ}$ für $x, y \in ℝ$ mittels $x \approx_{δ} y \Leftrightarrow | x - y | \leq δ$ (wobei $| x - y |$ den Abstand zwischen $x$ und $y$ bestimmt). Als Teilmenge von $ℝ^{2}$ ist diese Relation ein Streifen rund um die Diagonale (siehe Figur 1.13).

$PIC$

Figur 1.13: Dies stellt die Relation $\approx_{δ}$ als Teilmenge $ℝ \times ℝ$ dar, wobei $δ$ die vertikale (oder horizontale) halbe Breite des Streifens rund um die Diagonale ist.
(iv): Für eine beliebige Menge $X$ können wir $\subseteq$ als eine Relation auf der Potenzmenge $𝒫 (X)$ von $X$ betrachten. Dieses Beispiel ist viel schwieriger zu visualisieren. Aber in dem Spezialfall der Menge $X = {a, b, c}$ mit paarweise verschiedenen Elemente $a$ , $b$ und $c$ könnte man die Inklusionsrelation $\subseteq$ wie in der Figur 1.14 visualisieren.

$PIC$

Figur 1.14: Hier wird die Relation $\subseteq$ auf $𝒫 ({a, b, c})$ dargestellt: Ist $A = B$ oder existiert eine Pfeil-Kette von einer Menge $A$ links zu einer anderen Menge $B$ rechts (ohne Pfeile in gegengesetzter Richtung zu verwenden), so gilt $A \subseteq B$ .

Alternativ können wir $\subseteq$ als Teilmenge von $𝒫 (X) \times 𝒫 (X)$ auch wie in Figur 1.15 beschreiben.

$PIC$

Figur 1.15: Dies stellt ebenso die Relation $\subseteq$ auf $𝒫 ({a, b, c})$ dar.

Übung 1.60 (Eine bekannte Relation).

In einem gewissen Sinne haben wir bereits eine gewisse wichtige 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?

Lösung.

Eine derartige Relationen entspricht einer Abbildung von $X$ nach $Y$ , $𝒢 \subseteq X \times Y$ ist der Graph und wir schreiben meist $\mapsto$ statt $𝒢$ .

Für den Rest dieses Abschnittes wollen wir uns aber vorwiegend mit folgendem wichtigen Typ von Relationen beschäftigen.

Definition 1.61 (Ä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.62 (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 Äquivalenzrelation

ℛ = 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)

Sei

X = {1, 2, 3, 4, 5, 6}

und sei

\sim

die Relation, die durch Figur 1.16 definiert wird. Wir behaupten, dass

\sim

eine Äquivalenzrelation auf

X

darstellt.

$PIC$

Figur 1.16: Wir definieren eine Relation

\sim

als Teilmenge von

X \times X

und behaupten, dass diese sogar eine Äquivalenzrelation auf der Menge

X = {1, 2, 3, 4, 5, 6}

darstellt.

In der Tat entspricht der Reflexivität von $\sim$ der Aussage, dass die Diagonale ${(x, x) : x \in X}$ in der Relation enthalten ist. Ebenso entspricht der Symmetrie von $\sim$ der Aussage, dass die Teilmenge bei Spiegelung um die Diagonale (bei Vertauschung der beiden Koordinaten) unverändert bleibt. Beides ist in Figur 1.16 erfüllt. Die Transitivität hat keine derartige einfache visuelle Interpretation. Stattdessen sehen wir in Figur 1.16, dass $x \sim y$ für alle $x, y \in {1, 2, 3}$ aber $x ≁ y$ und $y ≁ x$ für $x \in {1, 2, 3}$ und $y \in {4, 5, 6}$ . Ebenso gilt $x \sim y$ für $x, y \in {4, 5}$ aber $x ≁ 6$ und $6 ≁ x$ für $x \in {4, 5}$ . Und schlussendlich gilt $6 \sim 6$ .

Aus dieser Information ergibt sich nun die Transitivität durch Fallunterscheidung: Angenommen $x \sim y$ und $y \sim z$ für $x, y, z \in X$ . Falls $x \in {1, 2, 3}$ so gilt dies auch für $y$ und $z$ , womit damit auch $x \sim z$ . Falls $x \in {4, 5}$ so gilt dies auch für $y$ und $z$ , womit $x \sim z$ . Falls aber $x = 6$ , so ist $y = 6$ , $z = 6$ und damit ebenso $x \sim z$ .

(v)

Ä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.63 (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.64 (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.

Hinweis.

Die Aussage ist auf jeden Fall falsch für die „leere Relation“, welche $x_{1} ≁ x_{2}$ für alle $x_{1}, x_{2} \in X$ erfüllt.

Übung 1.65 (Beispiele allgemeiner Relationen).

Finden Sie eine Relation (auf $ℕ$ oder anderen Mengen), die von den Eigenschaften einer Äquivalenzrelation

•

nur die Symmetrie,

•

nur die Transitivität,

•

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

•

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

erfüllt.

Hinweis.

Bestimmen Sie die Eigenschaften der Relationen in Beispiel 1.59 und auch von $\neq$ . Insbesondere ist für jedes fest gewählte $δ > 0$ die Relation $\approx_{δ}$ keine Äquivalenzrelation auf $ℝ$ , da $0 \approx_{δ} δ$ und $δ \approx_{δ} 2 δ$ aber $0 ≉_{δ} 2 δ$ .

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

Definition 1.66 (Ä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. In Beispiel 1.62(iv) hatten wir bereits implizit die drei Äquivalenzklassen ${[1]}_{\sim} = {1, 2, 3}$ , ${[4]}_{\sim} = {4, 5}$ und ${[6]}_{\sim} = {6}$ in unserer Diskussion verwendet.

Die Begriffe der Äquivalenzrelation und der Partition in Definition 1.51 sind auf folgende Weise eng verwandt.

Proposition 1.67 (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.67 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.68 (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.69 (Zwei Quotienten).

Charakterisieren Sie die Äquivalenzklassen der beiden in Übung 1.63 (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.

Hinweis.

In (i) werden alle Punkte in $A \subseteq X$ miteinander identifiziert und man kann $X ∕ \sim$ als $X ∖ A \cup {A}$ auffassen. In diesem Sinne wird $A$ zu einem Punkt gequetscht. In (ii) können wir $f^{- 1} ({f (x)}) \in X ∕ \sim$ für $x \in X$ mit $f (x) \in f (X)$ in Beziehung bringen und auf diese Weise eine kanonische Bijektion von $X ∕ \sim$ auf $f (X)$ definieren.

Für den Beweis der Proposition 1.67 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.67.

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.

■

Die folgende Übung zeigt, dass man sich jede Äquivalenzrelation bildlich wie eine disjunkte Vereinigung von Quadraten vorstellen kann, die wie in Beispiel 1.62(iv) entlang der Diagonale angeordnet in $X \times X$ liegen.

Übung 1.70.

Sei $X$ eine Menge und $\sim$ eine Äquivalenzrelation auf $X$ . Zeigen Sie, dass die Relation $\sim$ als Teilmenge von $X \times X$ durch $⋃_{x \in X} {[x]}_{\sim} \times {[x]}_{\sim}$ gegeben ist. Zeigen Sie auch, dass für $x, y \in X$ entweder ${[x]}_{\sim} \times {[x]}_{\sim} = {[y]}_{\sim} \times {[y]}_{\sim}$ oder $({[x]}_{\sim} \times {[x]}_{\sim}) \cap ({[y]}_{\sim} \times {[y]}_{\sim}) = \emptyset$ .

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.71 (Konstruktion der rationalen Zahlen).

Wir nehmen an, dass wir bereits die ganzen Zahlen $ℤ$ und die Addition und Multiplikation auf $ℤ$ mit allen üblichen Eigenschaften kennen. Wir wollen damit die rationalen Zahlen $ℚ$ definieren, wobei ein Element $\frac{m_{1}}{m_{2}} \in ℚ$ als Äquivalenzklasse des Tupels $(m_{1}, m_{2}) \in ℤ \times (ℤ ∖ {0})$ definiert sein wird.

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 eben die 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. Wie bereits erwähnt, sagen wir zur Betonung dieser (für Funktionen notwendiger) Eigenschaft, dass $\bar{f}$ wohldefiniert ist.

Übung 1.72 (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).

Teillösung.

Wir zeigen am Beispiel der Addition, dass die Auflösung bekannte Rechengesetze verwendet. Angenommen $m, m^{'}, p, p^{'} \in ℤ$ und $n, n^{'}, q, q^{'} \in ℤ ∖ {0}$ , erfüllen $(m, n) \sim (m^{'}, n^{'})$ und $(p, q) \sim (p^{'}, q^{'})$ . Dann gilt nach Definition $m n^{'} = m^{'} n$ und $p q^{'} = p^{'} q$ . Wir verwenden nun Erweitern (siehe Beispiel 1.71), Umformungen des Zählers (welcher in $ℤ$ liegt und wo die üblichen Rechengesetze angenommen werden), Kürzen, und erhalten dadurch

\begin{array}{l} \frac{m q + n p}{n q} & = \frac{(m q + n p) n^{'} q^{'}}{n q n^{'} q^{'}} \\ = \frac{m n^{'} q q^{'} + n n^{'} p q^{'}}{n q n^{'} q^{'}} \\ = \frac{m^{'} n q q^{'} + n n^{'} p^{'} q}{n q n^{'} q^{'}} \\ = \frac{(m^{'} q^{'} + n^{'} p^{'}) n q}{n q n^{'} q^{'}} \\ = \frac{m^{'} q^{'} + n^{'} p^{'}}{n^{'} q^{'}} . \end{array}

Dies zeigt, dass die definierte Abbildung $+ : ℚ \times ℚ \to ℚ$ in der Tat wohldefiniert ist.

Beispiel 1.73.

Angenommen wir wollen die reellen Zahlen $ℝ$ mittels Dezimalbruchentwicklungen definieren† Es gibt auch mehrere andere Möglichkeiten, siehe auch Abschnitt A.2.. Ebenso wollen wir auch noch, dass alle üblichen Rechenregeln erfüllt sein sollten. Dann muss man eine reelle Zahl als eine Äquivalenzklasse von Dezimalbrüchen definieren. Der Grund dafür ist, dass auf Grund üblicher Rechenmethoden

\begin{array}{l} (1.0000 \dots) ∕ (3.0000 \dots) = 0.3333 \dots \end{array}

und ebenso

\begin{array}{l} (0.3333 \dots) * (3.0000 \dots) = 0.9999 \dots \end{array}

da kein Übertrag notwendig ist. Aber eigentlich sollte $(x ∕ 3) * 3 = x$ für jedes $x \in ℝ$ sein. Damit also unsere Rechenmethoden Sinn machen, muss also $0.9999 \dots$ mit $1.0000 \dots$ identifiziert werden. Anders formuliert, muss also eine Äquivalenzrelation $\sim$ auf der Menge der Dezimalbruchentwicklungen definiert werden, so dass $0.9999 \dots \sim 1.0000 \dots$ . Die reelle Zahl $1$ ist dann eigentlich die Äquivalenzklasse ${[1.0000 \dots]}_{\sim} = {[0.9999 \dots]}_{\sim}$ .

1.6 Äquivalenzrelationen

Definition 1.58 (Relationen).

Beispiel 1.59 (Beispiele von Relationen).

Übung 1.60 (Eine bekannte Relation).

Definition 1.61 (Äquivalenzrelationen).

Beispiel 1.62 (Beispiele von Äquivalenzrelationen).

Übung 1.63 (Zwei weitere Beispiele).

Übung 1.64 (Ein falscher Beweis).

Übung 1.65 (Beispiele allgemeiner Relationen).

Definition 1.66 (Äquivalenzklassen und die Quotientenmenge).

Proposition 1.67 (Korrespondenz zwischen Äquivalenzrelationen und Partitionen).

Applet 1.68 (Eine Äquivalenzrelation und deren Quotient).

Übung 1.69 (Zwei Quotienten).

Behauptung.

Übung 1.70.

Beispiel 1.71 (Konstruktion der rationalen Zahlen).

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

Beispiel 1.73.

License