6.1 Grundbegriffe und Darstellungsformen
Beziehungen durch geordnete Paare
Im kartesischen Produkt \(A\times B\) stehen alle möglichen Paare. Eine Relation wählt daraus genau die Paare aus, für welche die betrachtete Beziehung gilt. Die Reihenfolge der Einträge ist dabei wesentlich.
Definition 6.1 (Binäre Relation). Seien \(A,B\) Mengen. Eine Teilmenge \(T\subseteq A\times B\) heißt binäre Relation von \(A\) nach \(B\).
Ist \(T\) endlich, so spricht man von einer endlichen Relation.
Für \(A=B=M\) heißt \(T\) eine Relation auf \(M\).
Die Schreibweisen \((x,y)\in T\) und \(x\,T\,y\) bedeuten dasselbe: „\(x\) steht in Relation \(T\) zu \(y\)“.
Auch eine Beziehung, die niemals oder immer gilt, lässt sich so beschreiben.
Grenzfälle. Sowohl \(\emptyset\) als auch \(A\times B\) sind Relationen.
Bei einer Teilbarkeitsbeziehung kann ein Element mehrere Partner haben.
Beispiel: Welche Zahl teilt welche?
Für \(A=\{2,3,4\}\) und \(B=\{6,8,9\}\) sei \(x\,T\,y\) genau dann, wenn \(x\) die Zahl \(y\) teilt. Geben Sie \(T\) elementweise an.
Relationen in unterschiedlichen Kontexten
Die Einträge eines Paares können ganz unterschiedliche Objekte sein:
- Zahlen vergleichen: Auf \(\mathbb R\) gilt \((x,y)\in T\) genau dann, wenn \(x\leq y\).
- Geometrie: Für Geraden einer Ebene gilt \((g,h)\in T\) genau dann, wenn \(g\) senkrecht auf \(h\) steht.
- Soziales Netzwerk: Für Benutzerkonten gilt \((a,b)\in T\) genau dann, wenn Konto \(a\) dem Konto \(b\) folgt.
- Datenbank einer Hochschule: Für Studierende und Lehrveranstaltungen gilt \((s,v)\in T\) genau dann, wenn \(s\) in der Veranstaltung \(v\) eingeschrieben ist.
- Software: Für Module eines Programms gilt \((A,B)\in T\) genau dann, wenn Modul \(A\) das Modul \(B\) direkt importiert.
Senkrechtstehen gilt in beiden Richtungen; Folgen oder Importieren müssen das nicht. Die Hochschulrelation verbindet sogar Objekte aus zwei verschiedenen Mengen.
Identitätsrelation
Die Gleichheit lässt sich auf jeder Menge durch dieselbe Konstruktion erfassen.
Definition 6.2 (Identitätsrelation). Die Identitätsrelation auf \(M\) ist \[ I_M=\{(x,x)\mid x\in M\}. \] Sie enthält genau die Paare mit gleichen Einträgen.
Mehrstellige Relationen
Wenn eine Beziehung mehr als zwei Einträge benötigt, verwenden wir längere Tupel.
Definition 6.3 (Mehrstellige Relation). Für Mengen \(M_1,\ldots,M_n\) mit \(n\geq1\) heißt eine Teilmenge \[ T\subseteq M_1\times\cdots\times M_n \] eine \(n\)-stellige Relation.
Ein Datensatz \((\text{Person},\text{Lehrveranstaltung},\text{Note})\) beschreibt beispielsweise eine dreistellige Beziehung. Eine Tabelle mit solchen Zeilen stellt eine Relation dar; gleiche Tupel werden als Mengenelemente nur einmal gezählt.
Eine Relation, mehrere Darstellungen
Je nach Fragestellung ist eine Liste, ein Koordinatenbild oder ein Graph übersichtlicher. Alle Darstellungen müssen dieselben geordneten Paare enthalten.
Darstellungen einer endlichen Relation.
- Paarmenge: alle \((x,y)\in T\) aufzählen.
- Pfeildiagramm: \(A\) links, \(B\) rechts; Pfeil von \(x\) nach \(y\) genau für \((x,y)\in T\).
- Koordinatenbild: die zugehörigen Punkte \((x,y)\) markieren.
- Gerichteter Graph auf \(M\): ein Knoten je Element; Pfeil \(x\to y\) für jedes Paar. Ein Paar \((x,x)\) ergibt eine Schlinge.
Tabelle und Graph lesen
Die Richtung eines Pfeils entspricht der Reihenfolge der Einträge in einem Paar.
Beispiel: Ein Pfeilweg mit Schlinge
Auf \(M=\{a,b,c\}\) sei \(T=\{(a,a),(a,b),(b,c)\}\).
- Zeile: erster Eintrag
- Spalte: zweiter Eintrag
- \(1\): Paar gehört zu \(T\),
- \(0\): Paar gehört nicht zu \(T\).
| \(T\) | \(a\) | \(b\) | \(c\) |
|---|---|---|---|
| \(a\) | \(1\) | \(1\) | \(0\) |
| \(b\) | \(0\) | \(0\) | \(1\) |
| \(c\) | \(0\) | \(0\) | \(0\) |
Zusammenfassung
- Eine binäre Relation ist eine Teilmenge eines festgelegten kartesischen Produkts.
- \((x,y)\) und \((y,x)\) beschreiben grundsätzlich verschiedene Zuordnungen.
- Die Identitätsrelation besteht aus allen Diagonalpaaren.
- Eine (endliche) Relation lässt sich als Menge der Paarmenge, Tabelle, Koordinatenbild und gerichteter Graph darstellen.