6. Relationen

Eine Relation ist einfach irgendeine Teilmenge eines kartesischen Produkts von zwei Mengen - es kommt zunächst nicht darauf an, ob die Relation irgendeinen Sinn ergibt.

Statt $(a,b)\in R$ schreibst du meist $aR b$ - insbesondere, wenn der Name der Relation kein Buchstabe wie $R$ ist, sondern irgendein schönes Symbol, z. B. $\leq$ oder $\lhd$.

Beispielsweise definierst du die Relation aus der obigen Einleitung als "kann sagen", bezeichnet mit dem Symbol $\lhd$, in folgender Weise:

Damit gilt beispielsweise Folgendes: Kuh $\lhd$ "Muh", Kuh $\lhd$ " " und Ziege $\lhd$ "Mäh". Die Kuh kann "Muh" sagen, sie kann auch " " sagen, die Ziege kann "Mäh" sagen.

Relationen auf einer Menge $A$

Es ist ohne Weiteres möglich, dass $A$ und $B$ dieselbe Menge sind. Man spricht dann von einer Relation auf der Menge $A$.

Eine Relation auf der Menge $A = \{1{,}2,3{,}4\}$ ist beispielsweise die Relation $<$ ("ist kleiner"):

Die Relation besteht aus allen Paaren $(a,b) \in A \times B$, für die gilt $a<b$.

Du kannst dir die Relation auf einer Menge $A$ auf zwei Arten bildlich veranschaulichen: wie oben gesehen durch ein Pfeildiagramm, das für jedes Paar $(a,b)$ der Relation einen Pfeil von $a$ nach $b$ enthält (links in der untenstehenden Abbildung), oder auch durch einen Graphen, dessen Knoten die Elemente der Menge $A$ sind und der eine Kante vom Knoten $a$ zum Knoten $b$ enthält, wenn das Paar $(a,b)$ ein Element der Relation ist (rechts in der untenstehenden Abbildung).

Eigenschaften von Relationen

Du kannst Relationen anhand bestimmter Eigenschaften klassifizieren:

Eine Relation $R$ auf der Menge $A$ heißt

Beispiele

Zugrundegelegt ist die Menge $A = \{1{,}2,3\}$. Betrachte die Eigenschaften folgender Relationen auf der Menge $A$.

• Die Relation $\{(1{,}1), (1{,}2), (2{,}2), (3{,}3)\}$ ist reflexiv.

• Die Relation $\{(1{,}2), (2{,}1)\}$ ist symmetrisch.

• Die Relation $\{(1{,}2), (2{,}3)\}$ ist asymmetrisch.

• Die Relation $\{(1{,}2), (2{,}3), (3{,}3)\}$ ist antisymmetrisch (aber nicht asymmetrisch).

• Die Relation $\{(1{,}2), (2{,}3), (1{,}3)\}$ ist transitiv.

• Die Relation $\{(1{,}1), (1{,}2), (2{,}2), (2{,}3), (3{,}1), (3{,}3)\}$ ist total.

Manche Relationen haben gleich mehrere der oben angegebenen Eigenschaften.

• Eine Relation, die reflexiv, symmetrisch und transitiv ist, heißt Äquivalenzrelation.

• Eine Relation, die reflexiv, antisymmetrisch und transitiv ist, heißt Halbordnung.

• Eine Halbordnung, die total ist, heißt (totale oder lineare) Ordnung.

Typische Beispiele sind folgende:

• Die Relation $\equiv \pmod n$ auf der Menge der ganzen Zahlen $\Z$ ist eine Äquivalenzrelation. Zwei ganze Zahlen stehen in dieser Relation "ist kongruent modulo $n$", wenn sie bei ganzzahliger Division durch $n$ denselben Rest ergeben. So gilt zum Beispiel $24 \equiv 31 \pmod 7$, denn beide Zahlen ergeben den Rest 3 bei Division durch 7.

• Die Relation $\subseteq$ ("ist enthalten in") auf der Potenzmenge ${\cal P}(M)$ einer Menge $M$ ist eine Halbordnung. Die Relation ist reflexiv, weil jede Menge $A$ in sich selbst enthalten ist, sie ist antisymmetrisch, weil wenn $A$ in $B$ enthalten ist und $B$ in $A$, dann gilt $A=B$. Und sie ist transitiv, denn wenn $A$ in $B$ enthalten ist und $B$ in $C$, dann ist auch $A$ in $C$ enthalten.

• Die Relation $\le$ ("kleiner oder gleich") auf der Menge der reellen Zahlen ist eine totale Ordnung.

Aufgaben