Eigenschaften von Relationen

In einem Satz: Man beschreibt eine Relation, indem man prüft, welche von vier typischen Regeln für sie gelten.

Schreibweise und Vorgehen

Sei $R$ eine Relation auf einer Menge $A$, also $R \subseteq A \times A$. Statt $(a, b) \in R$ schreibt man auch $a \,R\, b$. Mit $\mathbb{N}$ ist hier $\{1, 2, 3, \dots\}$ gemeint.

Jede der vier Eigenschaften ist eine Aussage über alle Elemente. Deshalb gibt es zwei Wege:

• Nachweisen: Du nimmst beliebige Elemente und formst die Regel Schritt für Schritt um, bis die Behauptung dasteht. Einzelne Beispiele beweisen nichts.
• Widerlegen: Du suchst ein Gegenbeispiel mit konkreten Werten. Ein einziger Fall genügt.

Warum das so ist, steht im Artikel Logik und Notation bei der Verneinung von $\forall$.

Für zwei Eigenschaften nutzen wir dieselbe Relation auf $\mathbb{N} \times \mathbb{N}$, deren Elemente Paare $(a, b)$ sind:

Sie vergleicht Paare nach dem Verhältnis $a/b$ gegen $c/d$. Mit $a/b \leq c/d$ und Multiplikation mit $b \cdot d > 0$ entsteht genau $a \cdot d \leq b \cdot c$.

Reflexiv

Aufgabe. Auf $\mathbb{N} \times \mathbb{N}$ ist durch $(a, b) \,R\, (c, d) \Leftrightarrow a d \leq b c$ eine Relation erklärt. Untersuche $R$ auf Reflexivität.

Lösung. Zu zeigen: $(a, b) \,R\, (a, b)$ für jedes Paar, am Ende muss also $a \cdot b \leq b \cdot a$ dastehen.

Sei $(a, b)$ beliebig. Wir setzen $(c, d) = (a, b)$ ein:

Der zweite Schritt ist das Kommutativgesetz $b \cdot a = a \cdot b$. Die letzte Aussage ist für alle $a, b \in \mathbb{N}$ wahr. Also gilt $(a, b) \,R\, (a, b)$ für jedes Paar, und $R$ ist reflexiv.

Gegenbeispiel. Zu zeigen: “kleiner als” ist nicht reflexiv, wir brauchen also ein $x$ mit $\neg(x \,R\, x)$. Sei $x \,R\, y \Leftrightarrow x < y$ auf $\mathbb{N}$. Dann ist $x \,R\, x \Leftrightarrow x < x$, und das ist falsch. Schon für $x = 1$ gilt $1 < 1$ nicht. Also ist “kleiner als” nicht reflexiv.

Symmetrisch

Aufgabe. Sei $M$ die Menge der Studierenden und $s(x)$ das Fachsemester von $x$. Zwei Studierende stehen in Relation $R_1$, wenn sie im selben Fachsemester sind, also $x \,R_1\, y \Leftrightarrow s(x) = s(y)$. Untersuche $R_1$ auf Symmetrie.

Lösung. Zu zeigen: Aus $x \,R_1\, y$ folgt $y \,R_1\, x$, am Ende muss also $s(y) = s(x)$ dastehen.

Seien $x, y \in M$ beliebig mit $x \,R_1\, y$:

Der mittlere Schritt gilt, weil die Gleichheit von Zahlen in beide Richtungen gilt. Also folgt aus $x \,R_1\, y$ immer $y \,R_1\, x$, und $R_1$ ist symmetrisch.

Aufgabe. Ist die Relation $(a, b) \,R\, (c, d) \Leftrightarrow a d \leq b c$ auf $\mathbb{N} \times \mathbb{N}$ symmetrisch?

Lösung. Nein. Zu zeigen: Es gibt Paare mit $(a,b) \,R\, (c,d)$, aber nicht $(c,d) \,R\, (a,b)$. Wähle $(a, b) = (1, 2)$ und $(c, d) = (3, 4)$:

Es gilt $(1,2) \,R\, (3,4)$, aber nicht $(3,4) \,R\, (1,2)$. Damit ist $R$ nicht symmetrisch.

Antisymmetrisch

Aufgabe. Sei $M$ die Menge der Studierenden und $m(x)$ die Matrikelnummer von $x$. Zwei Studierende stehen in Relation $R_2$, wenn sie dieselbe Matrikelnummer haben, also $x \,R_2\, y \Leftrightarrow m(x) = m(y)$. Untersuche $R_2$ auf Antisymmetrie.

Lösung. Zu zeigen: Aus $x \,R_2\, y$ und $y \,R_2\, x$ folgt $x = y$, am Ende muss also die Gleichheit der Studierenden dastehen.

Seien $x, y \in M$ mit $x \,R_2\, y$ und $y \,R_2\, x$:

Der letzte Schritt gilt, weil Matrikelnummern eindeutig sind: Verschiedene Studierende haben verschiedene Nummern. Also ist $R_2$ antisymmetrisch.

Aufgabe. Ist die Relation $(a, b) \,R\, (c, d) \Leftrightarrow a d \leq b c$ auf $\mathbb{N} \times \mathbb{N}$ antisymmetrisch?

Lösung. Nein. Zu zeigen: Es gibt zwei verschiedene Paare, die in beide Richtungen in Relation stehen. Wähle $(a, b) = (1, 2)$ und $(c, d) = (2, 4)$:

Beide Richtungen gelten, aber $(1,2) \neq (2,4)$. Damit ist $R$ nicht antisymmetrisch.

Transitiv

Aufgabe. Zeige, dass die Relation $(a, b) \,R\, (c, d) \Leftrightarrow a d \leq b c$ auf $\mathbb{N} \times \mathbb{N}$ transitiv ist.

Lösung. Zu zeigen: Aus $(a, b) \,R\, (c, d)$ und $(c, d) \,R\, (e, f)$ folgt $(a, b) \,R\, (e, f)$. Am Ende muss also $a f \leq b e$ dastehen.

Seien $(a, b)$, $(c, d)$ und $(e, f)$ beliebig mit $(a, b) \,R\, (c, d)$ und $(c, d) \,R\, (e, f)$. Das bedeutet

Wir multiplizieren (1) mit $f$ und (2) mit $b$. Das ist erlaubt, weil $f, b > 0$ sind und die Ungleichung dabei erhalten bleibt:

Beide Ungleichungen haben $b c f$ in der Mitte. Also gilt

Jetzt teilen wir durch $d$. Das ist erlaubt, weil $d \geq 1$ ist:

Damit folgt aus $(a, b) \,R\, (c, d)$ und $(c, d) \,R\, (e, f)$ immer $(a, b) \,R\, (e, f)$. Also ist $R$ transitiv.

Überblick

Vier Relationen aus den Beispielen und ihre Eigenschaften. Dabei ist $P(n)$ die Menge der Primteiler von $n$, zum Beispiel $P(12) = \{2, 3\}$.

Relationen ergänzen

Fehlt einer Relation eine Eigenschaft, kann man fehlende Paare hinzufügen. Gesucht ist dann die kleinste Relation, die die gewünschten Eigenschaften hat und die alte Relation enthält.

• Transitiv machen: zu $(x,y)$ und $(y,z)$ das Paar $(x,z)$ ergänzen.
• Reflexiv machen: alle Paare $(x, x)$ ergänzen.
• Symmetrisch machen: zu jedem Paar $(x, y)$ das Paar $(y, x)$ ergänzen.

Aufgabe: Kleinste Erweiterungen

Sei $A = \{a, b, c, d, e, f\}$ und

Bestimme jeweils die Relation mit der kleinsten Elementanzahl, für die gilt:

• a) $R \subseteq R_1$ und $R_1$ ist transitiv.
• b) $R \subseteq R_2$ und $R_2$ ist transitiv und reflexiv.
• c) $R \subseteq R_3$ und $R_3$ ist symmetrisch, transitiv und reflexiv.

Lösung.

a) Kleinste transitive Relation $R_1 \supseteq R$. Wir suchen alle Ketten:

• $(a,b)$ und $(b,d)$ verlangen $(a,d)$.
• $(c,b)$ und $(b,d)$ verlangen $(c,d)$.
• $(e,f)$ und $(f,e)$ verlangen $(e,e)$.
• $(f,e)$ und $(e,f)$ verlangen $(f,f)$.

Mit den vier neuen Paaren entstehen keine weiteren Ketten, die Relation ist jetzt transitiv:

b) Kleinste transitive und reflexive Relation $R_2 \supseteq R$. Zu $R_1$ fehlen noch die Paare $(a,a)$, $(b,b)$, $(c,c)$ und $(d,d)$. Die Paare $(e,e)$ und $(f,f)$ sind schon da. Die neuen Schleifen erzeugen keine neuen Ketten:

c) Kleinste symmetrische, transitive und reflexive Relation $R_3 \supseteq R$. Das ist eine Äquivalenzrelation. Wir sehen, welche Elemente die Paare von $R$ verbinden: $a, b, c, d$ hängen über $(a,b)$, $(c,b)$, $(b,d)$ zusammen, und $e, f$ hängen über $(e,f)$ zusammen. Eine Äquivalenzrelation muss innerhalb jeder solchen Gruppe alle Paare enthalten: