Äquivalenz- und Ordnungsrelationen

In einem Satz: Eine Äquivalenzrelation sagt “gleichwertig in einer Hinsicht”, eine Ordnungsrelation sagt “kommt davor oder ist gleich”.

Die Eigenschaften reflexiv, symmetrisch, antisymmetrisch und transitiv sind im Artikel Eigenschaften von Relationen erklärt. Hier setzen wir sie zu zwei Sorten von Relationen zusammen.

Äquivalenzrelationen

Vorgehen beim Nachweis. Du zeigst alle drei Eigenschaften einzeln für beliebige Elemente. Fehlt eine, ist es keine Äquivalenzrelation.

Aufgabe: Fachsemester

Sei $M$ die Menge der Studierenden und $s(x)$ das Fachsemester von $x$. Gib eine Relation $R_1$ an, die eine Äquivalenzrelation auf $M$ ist, und begründe es. Zwei Studierende stehen in Relation, wenn sie im selben Fachsemester sind.

Lösung. Zu zeigen: $R_1$ ist reflexiv, symmetrisch und transitiv. Wir setzen $x \,R_1\, y \Leftrightarrow s(x) = s(y)$ und prüfen die drei Eigenschaften einzeln für beliebige $x, y, z \in M$.

Reflexiv. Ich bin im selben Fachsemester wie ich selbst:

Die Aussage stimmt für jedes $x \in M$.

Symmetrisch. Seien $x$ und $y$ im selben Fachsemester. Dann auch $y$ und $x$:

Transitiv. Seien $x, y$ im selben und $y, z$ im selben Fachsemester. Dann sind $x$ und $z$ im selben:

Alle drei Eigenschaften gelten, also ist $R_1$ eine Äquivalenzrelation. Sie zerlegt $M$ in Gruppen, nämlich in alle Studierenden eines Fachsemesters. Solche Gruppen heißen Äquivalenzklassen. Jedes Element liegt in genau einer Klasse.

Aufgabe: Primteiler

Für $n \in \mathbb{N}$ bezeichnet $P(n) = \{p \mid p \text{ ist Primzahl und } p \text{ teilt } n\}$ die Menge der Primteiler von $n$. Zum Beispiel ist $P(12) = \{2, 3\}$ und $P(8) = \{2\}$. Auf $\mathbb{N}$ wird eine Relation $\sim$ definiert durch

Untersuche $\sim$ auf Reflexivität, Symmetrie und Transitivität. Ist $\sim$ eine Äquivalenz- oder eine Ordnungsrelation?

Lösung. Zu zeigen: $\sim$ ist reflexiv, symmetrisch und transitiv. Dann ist es eine Äquivalenzrelation. Seien $a, b, c \in \mathbb{N}$ beliebig.

Reflexiv: $a \sim a \Leftrightarrow P(a) = P(a)$. Das stimmt immer.

Symmetrisch: $a \sim b \Leftrightarrow P(a) = P(b) \Leftrightarrow P(b) = P(a) \Leftrightarrow b \sim a$.

Transitiv: Aus $P(a) = P(b)$ und $P(b) = P(c)$ folgt $P(a) = P(c)$, also $a \sim c$.

Damit ist $\sim$ eine Äquivalenzrelation. Die Klassen sind zum Beispiel $\{2, 4, 8, 16, \dots\}$ (alle Zahlen mit $P = \{2\}$) und $\{6, 12, 18, 24, \dots\}$ (alle mit $P = \{2, 3\}$). Die Zahl $1$ hat $P(1) = \emptyset$ und bildet allein eine Klasse.

Ordnungsrelationen

Beispiele für Ordnungen.

• $\leq$ auf den Zahlen ist eine totale Ordnung.
• $\subseteq$ auf $\mathcal{P}(\{1,2\})$ ist reflexiv, antisymmetrisch und transitiv, aber nicht total: $\{1\}$ und $\{2\}$ sind unvergleichbar.
• “Gleiche Matrikelnummer” ist eine Ordnung (und zugleich eine Äquivalenzrelation), denn sie bedeutet nur Gleichheit: Aus $m(x) = m(y)$ folgt $x = y$, weil Matrikelnummern eindeutig sind.

Aufgabe: Teilmengen der Primteiler

Mit $P$ wie oben wird auf $\mathbb{N}$ eine Relation $R$ definiert durch $a \,R\, b \Leftrightarrow P(a) \subseteq P(b)$. Untersuche $R$ auf Reflexivität, Symmetrie, Antisymmetrie und Transitivität. Ist $R$ eine Äquivalenz- oder eine Ordnungsrelation?

Lösung. Zu zeigen: Für jede der vier Eigenschaften entweder ein Beweis oder ein Gegenbeispiel. Danach entscheiden wir, ob $R$ eine Äquivalenz- oder eine Ordnungsrelation ist. Wir prüfen die Eigenschaften einzeln.

Reflexiv: $a \,R\, a \Leftrightarrow P(a) \subseteq P(a)$. Jede Menge ist Teilmenge von sich selbst.

Transitiv: Seien $a \,R\, b$ und $b \,R\, c$, also $P(a) \subseteq P(b)$ und $P(b) \subseteq P(c)$. Dann gilt $P(a) \subseteq P(c)$, also $a \,R\, c$.

Nicht symmetrisch. Wähle $a = 2$ und $b = 6$:

Aus $a \,R\, b$ folgt also nicht $b \,R\, a$. Damit ist $R$ keine Äquivalenzrelation.

Nicht antisymmetrisch. Wähle $a = 2$ und $b = 4$:

Beide Richtungen gelten für zwei verschiedene Zahlen. Damit ist $R$ keine Ordnungsrelation.

Der Vergleich