Eine (n-stellige) Relation R zwischen Mengen M1,…,Mn ist eine Teilmenge des Kartesischen Produkts
M1 ×
×Mn.
Wir spezialisieren sofort auf n= 2 (zweistellige Relationen) und schreiben R(a,b) oder aRb wenn < a,b >∈R.
Beispiel: Sei T die Menge aller Tierarten, F die Menge aller Fortbewegungsarten (schwimmen, fliegen, tauchen, …). Dann ist
Im Beispiel hat “Schwan” mehrere Bilder und “fliegt” mehrere Urbilder. In diesem Sinn ist die Relation eine Verallgemeinerung des Funktionsbegriffs.
Beispiel: M= {1,2,3}, < ⊂M×M. Relation “ist kleiner als” ist < = {< 1,2 >,< 1,3 >,< 2,3 >}. Wir schreiben 1 < 2, 1 < 3 usf.
Vokabeln
Sei R⊆M×M.
Wir reden jetzt also von Relationen zwischen Elementen ein und derselben Menge.
R heißt
- reflexiv: ∀x∈M:< x,x >∈R.
- symmetrisch: < x,y >∈R⇒< y,x >∈R.
- transitiv: < x, y >∈R∧< y,z >∈R⇒< x,z >∈R.
Beispielsweise ist die Relation “=” reflexiv, symmetrisch und transitiv, die Relation “<” transitiv, die Relation “≤” reflexiv und transitiv.
Relationen können eine dieser Eigenschaften einfach nicht haben, es kann aber auch sein, dass es für alle Elemente irgendwelche Negationen der Bedingungen gegeben sind. Die Negation kann auf verschiedene Arten geschehen:
- irreflexiv: ∀x∈M:< x,x >∉R– beachtet, dass das etwas ganz anderes ist, als nicht reflexiv. Ist etwa R⊆ℕ ×ℕ einfach nur nicht reflexiv, kann es durchaus sein, dass zwar < 1,1 >∈R, aber nicht < 2,2 >∈R.
- asymmetrisch: < x, y >∈R⇒< y,x >∉R– das verlangt sozusagen das “Gegenteil” der Symmetrie. Relationen wie < oder > wären Beispiele dafür.
- antisymmetrisch: < x,y >∈R∧< y,x >∈R⇒x= y– im Gegensatz zur Asymmetrie wird hier erlaubt, dass sowohl < x,y > als auch < y,x > in der Relation sind. Dann aber müssen die Elemente gleich sein; das ist keine komische Forderung, sondern beschreibt, was Relationen wie ≤ oder auch ⊆ (auf einer geeigneten Menge von Mengen) tun. Mit antisymmetrischen Relationen kann man Mengen ordnen.
- intransitiv: ∃x,y,z∈R:< x,y >∈R∧< y,z >∈R∧< x,z >∉R– das ist eine eher schwache Forderung, denn sie wird von allen Relationen erfüllt, die die Forderung aus der Definition der Transitivität nicht erfüllen.
- antitransitiv: < x,y >∈R∧< y,z >∈R⇒< x,z >∉R– dies ist demgegenüber eine starke Forderung, nämlich wieder quasi das “Gegenteil” der Transitivität. Ein Beispiel wäre die (direkte) Vorgängerrelation auf den Natürlichen Zahlen: Wenn 2 auf 1 folgt und 3 auf 2, dann darf natürlich 3 nicht auch auf 1 folgen.