Äquivalenzrelationen · Relationen und Funktionen

In vielen Situationen wollen wir Objekte als "im Wesentlichen gleich" betrachten:

Zwei Brüche $\frac{1}{2}$ und $\frac{2}{4}$ sind "gleich", obwohl sie verschieden geschrieben sind
Zwei Uhrzeiten 7:00 und 19:00 sind "gleich modulo 12"

Solche Beziehungen sind Äquivalenzrelationen. Sie zerlegen eine Menge in Gruppen von "gleichwertigen" Objekten.

Definition

Äquivalenzrelation

Eine Relation $\sim$ auf einer Menge $A$ heißt Äquivalenzrelation, wenn sie folgende drei Eigenschaften hat:

Reflexiv: Für alle $a$ : $a \sim a$

Symmetrisch: Wenn $a \sim b$ , dann $b \sim a$

Transitiv: Wenn $a \sim b$ und $b \sim c$ , dann $a \sim c$

Diese drei Eigenschaften zusammen besagen: Die Relation verhält sich wie Gleichheit.

\sim \text{ ist Äquivalenzrelation} \;\Leftrightarrow\; \text{reflexiv, symmetrisch, transitiv}

Beispiel

Kongruenz modulo n

Kongruenz modulo 3 auf $\mathbb{Z}$ :

$a \equiv b \pmod{3}$ bedeutet: $a$ und $b$ haben denselben Rest bei Division durch 3.

Beispiele:
$7 \equiv 4 \pmod{3}$ (beide haben Rest 1)
$9 \equiv 0 \pmod{3}$ (beide durch 3 teilbar)

Dies ist eine Äquivalenzrelation:

Reflexiv: $a \equiv a$ ✓
Symmetrisch: $a \equiv b \Rightarrow b \equiv a$ ✓
Transitiv: $a \equiv b$ und $b \equiv c \Rightarrow a \equiv c$ ✓

Definition

Äquivalenzklasse

Sei $\sim$ eine Äquivalenzrelation auf $A$ . Die Äquivalenzklasse eines Elements $a$ ist:

$[a] = \{b \in A \mid a \sim b\}$

Das ist die Menge aller Elemente, die äquivalent zu $a$ sind.

Beispiel für modulo 3:
$[0] = \{\ldots, -6, -3, 0, 3, 6, 9, \ldots\}$ (alle durch 3 teilbaren Zahlen)
$[1] = \{\ldots, -5, -2, 1, 4, 7, 10, \ldots\}$ (Rest 1)
$[2] = \{\ldots, -4, -1, 2, 5, 8, 11, \ldots\}$ (Rest 2)

[a] = \{b \in A \mid a \sim b\}

Zusammenfassung

Äquivalenzrelation = reflexiv + symmetrisch + transitiv
Äquivalenzklasse $[a]$ = alle zu $a$ äquivalenten Elemente
Die Äquivalenzklassen zerlegen die Menge in disjunkte Teile

Kongruenz modulo n

Zusammenfassung

Übungen