Binäre Relation

Eine binäre Relation ist ein spezieller Typ von Relation mit der Stelligkeit zwei. Zu den typischen binären Relationen gehören zum Beispiel kleiner als, Gleichheit, Teilbarkeit, größer als usw.

Beispiele

Die binäre Relation ist eine der typischen und häufig vorkommenden Relationen. Außerdem hat sie einige interessante Eigenschaften, die wir hier beschreiben.

Ein Beispiel für eine binäre Relation kann sein: die Beziehung „Vater – Sohn“, das Paar „Verkehrsmittel – Anzahl der Räder“ oder allgemeiner „Objekt – Eigenschaft des Objekts“. Das Objekt kann ein Tier sein und die Eigenschaft die Anzahl der Beine, die durchschnittliche Lebensdauer, die Anzahl der Haare auf dem Kopf und Ähnliches.

Eine binäre Relation R zwischen den Mengen M₁ und M₂ können wir so definieren: R ⊆ M₁ × M₂. Eine binäre Relation ist also eine Menge von Paaren, wobei diese Menge eine Teilmenge des kartesischen Produkts der beiden Mengen ist, zwischen denen wir die Relation einführen. Die Relation „Vater – Sohn“ kann also eine Relation zwischen den Mengen aller Menschen, aller Menschen in Europa oder in Berlin sein. Die Menge können wir auch in eine andere Richtung einschränken, wir können sagen, dass wir die Relation zwischen den Mengen aller Männer definieren, nicht der Menschen im Allgemeinen.

Für binäre Relationen verwenden wir üblicherweise eine spezielle Schreibweise. Anstatt (a, b) ∈ R zu schreiben, können wir aRb schreiben. Zum Beispiel können wir statt (3, 1) ∈ > schreiben 3 > 1. Ähnlich für die anderen Relationen. Die Schreibweise aSb ist also gleichwertig mit (a, b) ∈ S.

Umkehrrelation

Die Umkehrrelation ist die zur gegebenen Relation entgegengesetzte Relation. (Achtung, nicht mit dem Komplement einer Relation verwechseln.) Welche Relation ist die entgegengesetzte zur Relation kleiner als? Größer als. Wenn die Relation kleiner als das Element (4, 7) enthält, also 4 < 7, dann ist das inverse Element das entgegengesetzte: 7 > 4, in der Umkehrrelation liegt also das inverse Paar (7, 4).

Haben wir die Relation R ⊆ M₁ × M₂, dann konstruieren wir die Umkehrrelation R⁻¹ so, dass wir alle Elemente (a, b) ∈ R nehmen und in R⁻¹ ihre Umkehrung einfügen. Wenn also die Relation R das Element (a, b) enthält, dann muss die Relation R⁻¹ das Element (b, a) enthalten. Das gilt auch umgekehrt: Wenn R⁻¹ das Element (b, a) enthält, dann muss die Relation R das Element (a, b) enthalten.

Als Definition: Die Relation R⁻¹ ist genau dann die Umkehrrelation zu R, wenn gilt:

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a,b)\in R\iff (b,a)\in R^{-1}$$

Es gilt also: 6 < 8 genau dann, wenn 8 > 6. Ähnlich für weitere Paare.

Verkettung von Relationen

Binäre Relationen können wir miteinander verketten. Nehmen wir zwei Relationen, die erste, R, sei „Vater seines Sohnes sein“ und die zweite, S, „Bruder seiner Schwester sein“. Die Relation R enthält also Paare (Vater, Sohn), die zweite Relation enthält Paare (Bruder, Schwester).

Jetzt versuchen wir, die Relationen zu verketten. Es entsteht eine neue Relation, wir bezeichnen sie mit R ∘ S, und diese Relation enthält das Element (a, c) genau dann, wenn (a, b) ∈ R und zugleich (b, c) ∈ S. Beachte, dass in beiden Elementen b vorkommt, einmal an zweiter Stelle und dann an erster Stelle des Paares. Das ist gewissermaßen das Verbindungselement der Verkettung.

Beispiel: R = {(Tom, Max); (Paul, Jakob)} und S = {(Max, Julia); (Max, Lena); (Jakob, Lisa)}. Tom ist der Vater von Max, Paul ist der Vater von Jakob. Max hat die Schwestern Julia und Lena und Jakob hat die Schwester Lisa.

Nun verketten wir die Relationen: R ∘ S. Wir suchen ein Paar aus R, das an der Stelle des Sohnes jemanden hat, der in der Relation S als Bruder geführt wird. Zum Beispiel diese zwei Paare: (Tom, Max) und (Max, Julia). Max ist das Verbindungselement, das brauchen wir weiter nicht, und aus den übrigen Namen bilden wir ein neues Paar: (Tom, Julia). Die Relation R ∘ S enthält also das Paar (Tom, Julia). Max hat noch eine Schwester, Lena, die fügen wir ebenfalls zur verketteten Relation hinzu: (Tom, Lena). Schließlich bleibt der Sohn Jakob. Er hat die Schwester Lisa. Wir haben also zwei Paare: (Paul, Jakob) und (Jakob, Lisa). Daraus bilden wir ein weiteres Element: (Paul, Lisa).

Das Ergebnis ist die Relation: R ∘ S = {(Tom, Julia); (Tom, Lena); (Paul, Lisa)}. Wie könnten wir diese Relation benennen? Wahrscheinlich „Vater seiner Tochter sein“.

Noch einmal die ganze Definition:

$$(a,c)\in (R\circ S)\iff \mathrm{\exists }b(a,b)\in R\wedge (b,c)\in S$$

Anmerkung: Manchmal wird die umgekehrte Schreibweise verwendet, das heißt, für dieselbe Definition würde statt R ∘ S die Schreibweise S ∘ R benutzt.