Relationen


Elemente in einer Menge stehen in bestimmten Beziehungen zueinander. Diese Beziehungen lassen sich durch Relationen beschreiben. Konkret ist eine Relation eine Teilmenge des kartesischen Produkts zweier Mengen.
Sei A und B zwei beliebige Mengen. Jede Menge R mit
     R ⊆ A χ B
heißt (binäre) Relation.
Man spricht in dieser Definition deshalb von einer binären Relation, weil lediglich eine Relation zwischen zwei Elementen besteht. Tatsächlich lassen sich auch Teilmengen von Produkten von drei oder mehreren Mengen bilden, die ebenfalls Relationen sein können.

Eine Relation lässt sich auf unterschiedliche Weisen darstellen. Jede hier vorgestellte Darstellung hat ihre eigene Vor- und Nachteile. Man kann Relationen folgendermaßen darstellen:
Da Relationen letztendlich nichts anderes als spezielle Mengen sind, können sämtliche Konzepte aus der Mengenlehre auch auf Relationen übertragen werden. So können Relationen gleich sein oder eine Relation kann eine Teilrelation von einer anderen Relation sein. Weiter kann man Relationen vereinigen oder auch das Komplement bilden. Darüber hinaus gibt es aber noch einige speziell für Relationen definierte Operationen von denen nachfolgend vor allem die inverse Relation und das Relationsprodukt interessant sind.

Inverse Relation


Die inverse Relation ist wie folgt definiert:
R-1 := {(y,x) | (x,y) ∈ R}

Beispiel einer inversen Relation

Die inverse Relation der folgenden Ordnungsrelation
R := {(x,y) | x ≤ y}
lautet:
R-1 := {(x,y) | x ≥ y}

Relationenprodukt


Das Relationenprodukt sei wie folgt definiert:
R ⋅ S := {(x,z) | es existiert ein y mit x und y stehen bezüglich Relation R in Beziehung und y und z stehen bezüglich Relation S in Beziehung}

Mit diesen Operationen lassen sich Relationenattribute elegant charakterisieren. Welche Attribute das sind, erfährt man nachfolgend.

Relationenattribute

Eine Relation R in der Menge M heißt:
  • reflexiv in M, falls für alle x ∈ M das Element x in Relation mit x steht, also xRx gilt
  • irreflexiv in M, falls für alle x ∈ M das Element x nicht in Relation mit x steht
  • symmetrisch in M, falls für alle x,y ∈ M aus x steht in Relation mit y stets folgt, dass y in Relation zu x steht.
  • asymmetrisch in M, falls für alle x,y ∈ M aus x steht in Relation mit y stets folgt, dass y nicht in Relation zu x steht.
  • antisymmetrisch in M, falls für alle x,y ∈ M aus x steht in Relation mit y und y steht in Relation zu x stets folgt, dass x=y ist
  • transitiv in M, falls für alle x,y,z ∈ M aus x steht in Relation mit y und y steht in Relation zu z stets folgt, dass x in Relation zu z steht.

Reflexivität

Für eine reflexive Relation gilt, dass für alle x aus einer Menge M gilt, x steht in Relation zu x. Am einfachsten begreiflich machen kann man die Reflexivität mit einem einfachen Beispiel. Die Relation „hat die selben Eltern wie“ zwischen drei Brüdern ist beispielsweise reflexiv. Denn schließlich hat jeder die selben Eltern wie man selbst. Klar wird die Reflexivität auch in der Darstellung von Graphen oder in einer Adjazenzmatrix.

Reflexiven Relation in Graphendarstellung

Beispiel einer reflexiven Relation - Graph

Wie man erkennen kann, muss bei diesem Graph eine reflexive Relation vorliegen. Entscheidend sind nämlich die Schlingen an jedem Knoten. Sobald jeder Knoten eine Schlinge besitzt, ist der Graph reflexiv, da jeder Knoten auf „sich selbst zeigt“.

Reflexiven Relation in Matrixdarstellung

Beispiel einer reflexiven Relation - Matrix

Auch in der Matrixdarstellung, wie die obere Adjazenzmatrix des oberen Graphen, sieht man mit einem Blick, ob die Relation reflexiv ist oder nicht. Sobald in der Hauptdiagonalen alle Einträge eine 1 sind, liegt Reflexivität vor.

Irreflexivität

Eine Relation ist dann irreflexiv, wenn für alle x aus einer Menge M gilt, dass x in keiner Relation zu x steht.
ACHTUNG! Ist eine Relation nicht reflexiv, folgt daraus nicht zwangsläufig, dass die Relation deshalb irreflexiv ist. Damit eine Relation irreflexiv ist, muss für alle x gelten, dass x in keiner Relation zu x steht.

Beispiel für irreflexive Relation

Sei folgende Menge gegeben: M := {1,2,3}

Nun ist folgende Relation beispielsweise reflexiv:
R1 ={(1,1), (1,2), (2,2), (3,3)}
Würde man aus dieser Relation R1 nun (3,3) löschen, hätte man folgende Relation:
R2 ={(1,1), (1,2), (2,2)}
Diese Relation R2 wäre nun nicht Reflexiv aber eben auch nicht irreflexiv, da die Relation eben noch (1,1) und (2,2) enthält. Erst wenn man diese löscht, wäre die Relation irreflexiv.
R3 ={(1,2)}
R3 ist nun irreflexiv!



Symmetrie

Eine Relation ist dann symmetrisch, wenn für alle x,y ∈ M gilt, dass x zu y in Relation steht und daraus folgt, dass auch y zu x in Relation steht. Stellt man eine Relation als Graph dar, kann man eine symmetrische Relation sofort erkennen. Diese liegt nämlich vor, wenn jeder Knoten mit seinem Nachbarknoten durch eine gerichtete Kante an beiden Enden verbunden ist. Also wenn an jede Kante zu jedem Knoten mit einer Pfeilspitze abschließt. Dies ist beispielsweise beim nachfolgenden Graph der Fall.

Symmetrische Relation in Graphendarstellung

Beispiel einer symmetrischen Relation



Asymmetrie

Bei einer asymmetrischen Relation muss für alle x,y ∈ M gelten, wenn x zu y in Relation steht, dann steht nicht y in Relation zu x.
Wie auch bei der Irreflexivität, muss man auch bei der Asymmetrie aufpassen. Wenn eine Relation nämlich nicht Symmetrisch ist, bedeutet dies nicht automatisch, dass die Relation dann asymmetrisch ist.

Antisymmetrie

Bei einer antisymmetrischen Relation gilt für alle x,y ∈ M, dass wenn x in Relation zu y steht und y in Relation zu x, dann ist x=y.

Man sollte sich von dem Begriff "Antisymmetrie" nicht täuschen lassen! Eine Relation kann sehr wohl gleichzeitig symmetrisch als auch antisymmetrisch sein, da beides keine Gegensätze sind.
Beispiel: Die Relation R1 ={(1,1), (2,2), (3,3)} ist symmetrisch, aber auch antisymmetrisch.

Transitivität

Eine Relation ist dann transitiv, wenn für alle x,y,z ∈ M gilt, wenn x in Relation steht zu y und y in Relation steht zu z, dann steht auch x in Relation zu z.

Ein Beispiel für eine transitive Relation wäre die "kleiner als"-Relation: R<= {(0,1), (0,2), (1,2)}
Es ergibt sich: 0 ist kleiner als 1 und 1 ist kleiner als 2, also muss auch 0 kleiner als 2 sein. Was wahr ist und somit ist R< eine transitive Relation.

Äquivalenzrelation


Eine Relation R ist eine Äquivalenzrelation, wenn sie gleichzeitig reflexiv, symmetrisch und transitiv ist.

Eine Äquivalenzrelation hat die Eigenschaft , die Elemente aus einer Menge M in Äquivalenzklassen einzuteilen. Durch die Eigenschaften der Reflexivität, der Symmetrie und der Transitivität führt dazu, dass diese gebildeten Äquivalenzklassen paarweise disjunkt sind.

Allgemeine Frage: Wie viele Äquivalenzklassen kann eine drei-elementige Menge haben?

Antwort: 5

Man nehme an, die Menge sei: M := {a,b,c}, dann wären die fünf möglichen Klassen:
  1. a in einer Klasse, b in einer Klasse und c in einer Klasse
  2. a und b in einer Klasse und c in einer Klasse
  3. a und c in einer Klasse und b in einer Klasse
  4. a in einer Klasse und b und c in einer Klasse
  5. a und b und c in einer Klasse

Ordnungsrelation


Eine Relation R ist eine Ordnungsrelation, wenn sie gleichzeitig reflexiv, antisymmetrisch und transitiv ist.



Quellen:

Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972