Relationen und ihre Struktureigenschaften

 Gilt (a, b)  ∈  R, so sagen wir auch, dass a in der Relation R zu b steht. Anstelle von (a, b)  ∈  R schreiben wir auch a R b oder R(a, b). Gilt a R b und b R c, so schreiben wir auch a R b R c.

 Für eine Relation R definieren wir:

dom(R)  =  { a | ∃b (a, b)  ∈  R }, (Definitionsbereich, „domain“)

rng(R)  =  { b | ∃a (a, b)  ∈  R }. (Wertebereich, „range“)

 Die Menge field(R) = dom(R) ∪ rng(R) heißt das Feld von R. Das Feld von R ist die kleinste Menge A derart, dass R eine Relation auf A ist.

 Weiter können wir für jede Relation R eine Umkehrrelation definieren:

R⁻¹  =  { (a, b) | (b, a)  ∈  R }. (Umkehrrelation)

 Der Übergang von R zu R⁻¹ entspricht dem Übergang von „kleiner“ zu „größer“, von „höher“ zu „niedriger“, von „ist ein Kind von“ zu „ist ein Elternteil von“. Offenbar gilt

dom(R⁻¹)  =  rng(R),  rng(R⁻¹)  =  dom(R),  field(R⁻¹)  =  field(R).

 Für Relationen gibt es eine Hand voll grundlegender Struktureigenschaften. So schließt zum Beispiel „a ist größer als b“ aus, dass „b ist größer als a“ gilt, und umgekehrt folgt aus „a ist ähnlich zu b“, dass auch „b ist ähnlich zu a“ gilt − andernfalls würde eine Relation den Namen „größer“ bzw. „ähnlich“ nicht verdient haben.

 Die fünf wichtigsten Struktureigenschaften einer Relation sind nun die folgenden.

 Wir können uns eine Relation R auf A als eine „Punktwolke“ im kartesischen Produkt A × A vorstellen: Wir tragen ein (a, b)  ∈  A × A genau dann als Punkt ein, wenn a R b gilt. Dann bedeutet die Reflexivität von R, dass die gesamte Diagonale { (a, a) | a  ∈  A } zur Punktwolke gehört. Die Symmetrie von R bedeutet, dass die Punktwolke invariant gegenüber der Spiegelung an der Diagonale ist. Die Transitivität hat dagegen bei dieser Darstellung von R keine besonders anschauliche Bedeutung.

 Eine ganz andere Möglichkeit, sich eine Relation R auf A zu visualisieren, ist die folgende: Wir fassen A als Menge von Punkten auf und verbinden diejenigen Punkte a, b mit einem Pfeil, für die a R b gilt. Nun hat die Transitivität von R eine sehr anschauliche Bedeutung, denn sie besagt: Gibt es einen Pfeil von a nach b und weiter einen Pfeil von b nach c in unserem Diagramm, so gibt es immer auch einen Pfeil von a nach c. Die Symmetrie besagt, dass es zu jedem Pfeil von a nach b auch immer den umgekehrten Pfeil von b nach a gibt. Wir können im symmetrischen Fall also die Pfeile ganz weglassen und einfach alle a, b, für die a R b gilt, mit einer Linie verbinden. Die Irreflexivität von R besagt schießlich, dass unser Diagramm keine „Schlingen“ besitzt, die von einem Punkt a zu a selbst führen. Diese Form der Visualisierung ist vor allem für Relationen auf endlichen Mengen sehr nützlich und wir werden im Kapitel über Graphen darauf zurückkommen.

 Der Leser kann bereits an dieser Stelle die Tragweite des Konzepts sehen: Relationen decken abstrakte mathematische Dinge wie die Element-Beziehung ebenso ab wie die Modellierung von konkreten Verkehrsnetzen. Sobald wir die Beziehungen betrachten, die zwischen Objekten eines Bereichs bestehen, werden wir Relationen definieren und untersuchen. Damit treten Relationen überall auf, wo es um mehr geht als die reine Anzahl von Dingen.

 Wir führen noch einige Sprechweisen und Notationen für mehrstellige Relationen ein. Eine Menge R heißt eine dreistellige Relation auf A, falls R ⊆ A³. Statt (a₁, a₂, a₃)  ∈  R schreiben wir auch R(a₁, a₂, a₃). Analog sind 4-, 5-, … stellige Relationen definiert. Konsequent nennen wir ein R ⊆ A dann auch eine einstellige Relation auf A und schreiben R(a) für a  ∈  R. Hier wird die Wortbedeutung „Relation“ („Beziehung“) missbraucht und man spricht auch deswegen oft von einem (einstelligen) Prädikat auf A. Allgemein werden die Begriffe Prädikat und Relation in der Mathematik synonym verwendet.

 Es gibt drei Haupttypen von Relationen: Äquivalenzrelationen, Ordnungen und Funktionen. Diese drei Typen spielen eine universelle Rolle in der Mathematik, und wir wollen sie der Reihe nach vorstellen.