Binäre Relation auf einer Menge

Unter einer binären Relation auf einer Menge verstehen wir eine binäre Relation, die zwischen zwei gleichen Mengen definiert ist.

Beispiele

Eine binäre Relation auf einer Menge ist ein spezieller Typ einer binären Relation, bei dem beide Grundmengen gleich sind. Eine binäre Relation auf einer Menge ist also eine Relation R mit R ⊆ M × M.

Die Relation „größer als“ ist eine binäre Relation auf einer Menge, weil wir auf beiden Seiten mit Zahlen arbeiten. Es gilt also > ⊆ ℝ × ℝ. Die Relation „Vater – Anzahl der Kinder“ ist keine binäre Relation auf einer Menge, weil wir den Vater aus der Menge aller Menschen auswählen, die Anzahl der Kinder dagegen aus einer Zahlenmenge.

Eigenschaften

Eine binäre Relation R auf einer Menge M kann einige interessante Eigenschaften haben. Wir sagen, dass die Relation R…

• reflexiv ist, wenn für alle a ∈ M gilt, dass (a, a) ∈ R.
• symmetrisch ist, wenn für alle a, b ∈ M gilt: Ist (a, b) ∈ R, dann ist auch (b, a) ∈ R.
• antisymmetrisch ist, wenn für alle a, b ∈ M gilt: Ist (a, b) ∈ R und zugleich auch (b, a) ∈ R, dann ist a = b.
• transitiv ist, wenn für alle a, b, c ∈ M gilt: Ist (a, b) ∈ R und zugleich (b, c) ∈ R, dann liegt auch (a, c) in R.

Beispiele zur Reflexivität

Reflexivität bedeutet, dass ein Element mit sich selbst in Relation steht. Ein typisches Beispiel ist die Gleichheit. Wenn wir die Gleichheit auf den natürlichen Zahlen definiert haben, dann gilt sicher für jedes Element a: a = a. Ein weiteres Beispiel kann die Teilbarkeit sein. Dort gilt wieder, dass die Zahl a durch sich selbst teilbar ist, das Paar (a, a) liegt also in der Teilbarkeitsrelation (die Sieben teilt die Sieben).

Die Relation kleiner als ist dagegen nicht reflexiv, weil a < a nicht gilt. Das ist nicht möglich, die Sieben kann nicht kleiner als die Sieben sein. Ähnlich die Relation „Vater seines Kindes sein“ – ich kann nicht mein eigener Vater sein. Solche Relationen sind nicht reflexiv.

Wichtig ist, dass die Reflexivität für alle Elemente gelten muss, es genügt nicht, nur einige zu finden. Nehmen wir zum Beispiel die Relation „jemanden mögen“. Ich kann einerseits jemanden mögen, zum Beispiel den Kontrolleur, aber ich kann auch mich selbst mögen. Sicher findet sich ein Mensch, der sich selbst mag. Genauso findet sich aber ein Mensch, der sich selbst nicht mag. Eine solche Relation ist dann nicht reflexiv – alle Menschen müssten sich selbst mögen.

Beispiele zur Symmetrie

Bei einer symmetrischen Relation gilt: Wenn ein Paar in der Relation liegt, dann liegt auch das umgekehrte Paar in der Relation. Zum Beispiel die Relation „Geschwister sein“. Wenn Jonas ein Geschwisterkind von Julia ist, dann ist auch Julia ein Geschwisterkind von Jonas. Von den Zahlenrelationen könnte es die Relation „Gegenzahl sein“ sein. Damit meine ich die Paare 2 und −2 oder −7 und 7. Das sind zwei Zahlen, deren Summe null ergibt. Eine solche Relation ist symmetrisch, weil es auf die Reihenfolge einfach nicht ankommt: (2, −2) und (−2, 2) sind weiterhin zueinander Gegenzahlen und ergeben als Summe null.

Eine Relation, die nicht symmetrisch ist, ist kleiner als (über den reellen Zahlen). Sie hat kein einziges symmetrisches Element, weil nie zugleich a < b und b < a gelten kann. Wenn 5 < 15 ist, dann kann nicht 15 < 5 gelten. Außerdem ist die Relation „Vater seines Sohnes sein“ nicht symmetrisch. Du kannst der Vater deines Sohnes sein, aber dann kann der Sohn nicht der Vater seines Vaters sein.

Auch diese Eigenschaft muss wieder in allen Fällen gelten. Soll die Relation „jemanden mögen“ (auf der Menge aller Menschen) symmetrisch sein, dann müsste, wenn ich Emma mag, zugleich Emma mich mögen. Und weil sie mich nicht einmal kennt, kann ich nicht sagen, dass sie mich mag, was schade ist, und die Relation ist nicht symmetrisch. Was ebenfalls schade ist.

Beispiele zur Antisymmetrie

Ein klassisches Beispiel für eine antisymmetrische Relation ist kleiner oder gleich. Die Antisymmetrie sagt uns: Wenn die Elemente (a, b) und (b, a) in der Relation liegen, dann nur, wenn sie gleich sind, a = b. Die Relation kleiner oder gleich erfüllt das. Wann gilt a ≤ b und zugleich b ≤ a? Nur im Fall a = b. Setzen wir ein: Gilt 3 ≤ 5 und zugleich 5 ≤ 3? Nein. Aber es gilt 4 ≤ 4 und zugleich 4 ≤ 4.

Ein Beispiel für eine Relation, die nicht antisymmetrisch ist, können Paare von Wörtern mit gleicher Länge sein, zum Beispiel (Samstag, Zwiebel). Eine solche Relation ist nicht antisymmetrisch, weil wir ein Paar von Wörtern finden, das in der Relation liegt, dessen umgekehrtes Element ebenfalls in der Relation liegt, und die beiden Wörter dabei verschieden sind. Also das erwähnte Element (Samstag, Zwiebel) und seine Umkehrung: (Zwiebel, Samstag). Beide liegen offensichtlich in unserer Relation, aber trotzdem ist Samstag ≠ Zwiebel, die Relation ist also nicht antisymmetrisch.

Beispiel zur Transitivität

Transitiv ist die Relation kleiner als. Die Transitivität sagt uns: Wenn 3 < 4 und zugleich 4 < 5, dann muss sicher auch 3 < 5 gelten. Für viele Relationen ist das eine ziemlich natürliche Eigenschaft. Ähnlich im Beispiel mit der gleichen Länge von Wörtern. Liegt (Zwiebel, Samstag) in der Relation und ebenso (Samstag, Teppich), dann liegt auch das Wortpaar (Zwiebel, Teppich) in der Relation.

Nicht transitiv ist die Relation „Vater von jemandem sein“. Wenn Tom der Vater von Max ist und Max der Vater von Moritz, dann ist Tom nicht der Vater von Moritz, sondern sein Großvater. Ähnlich ist die Relation „jemanden mögen“ nicht transitiv. Wenn ich Emma mag und Emma ihren Mann mag, heißt das nicht, dass auch ich Emmas Mann mag.

Mit Transitivität beschäftigt man sich auch bei klassischen Spielwürfeln. Betrachten wir die Relation „Würfel A ist besser als Würfel B“, die gilt, wenn auf Würfel A häufiger (mit größerer Wahrscheinlichkeit) eine höhere Zahl fällt als auf Würfel B. Ist eine solche Relation transitiv? Darauf antwortet der Artikel nichttransitive Würfel.

Äquivalenz und Ordnung

Einige spezielle Typen binärer Relationen haben auch eigene Namen:

• Eine Äquivalenz ist eine Relation, die reflexiv, symmetrisch und transitiv ist.
• Eine Ordnung ist eine Relation, die reflexiv, antisymmetrisch und transitiv ist.