Relation (Mathematik)

Eine Relation ist allgemein eine Beziehung, die zwischen Dingen bestehen kann (vgl. Einleitungsartikel Relation). Relationen im Sinne der Mathematik sind ausschließlich diejenigen Beziehungen, bei denen stets klar ist, ob sie bestehen oder nicht. Zwei Gegenstände können entsprechend nicht "zu einem gewissen Grade" in einer Relation zueinander stehen.

Damit ist eine einfache mengentheoretische Definition des Begriffs der Relation möglich: eine Relation R ist eine Menge von n-Tupeln. Dinge, die in der Relation R zueinander stehen, bilden ein n-Tupel, das Element von R ist.

Wenn nicht ausdrücklich etwas anderes angegeben ist, versteht man unter einer Relation eine "zweistellige" oder "binäre" Relation, also eine Beziehung zwischen je zwei Dingen. Die Elemente eines Paares (a,b) können aus verschiedenen Grundmengen A und B stammen; die Relation heißt dann heterogen oder "Relation zwischen den Mengen A und B". Wenn die Grundmengen übereinstimmen, A = B, heißt die Relation auch homogen oder "Relation in der Menge A". Wichtige Spezialfälle, zum Beispiel Äquivalenzrelationen und Ordnungsrelationen, sind Relationen in einer Menge.

Definition

Die vorstehenden Überlegungen erlauben uns nun folgende formale Definition: eine binäre Relation R ist eine Teilmenge des kartesischen Produkts zweier Mengen A und B:

R \sube A \times B  \quad\mbox{mit}\quad A \times B:= \{ (a,b) \,|\, \left( a \in A \right) \ \and \left( \ b\in B \right) \}

Allgemeiner ist eine n-stellige Relation eine Teilmenge des kartesischen Produkts von n Mengen A₁, ..., A_n.

Erläuterungen

Das kartesische Produkt ist die Menge aller geordneten Paare von a und b, wobei a irgendein Element aus der Menge A und b eines aus B darstellt. Bei dem geordneten Paar ist die Reihenfolge wichtig, d.h. (a, b) ist etwas anderes als (b, a). Im Gegensatz zu der ungeordneten Menge {a, b}, die identisch ist mit {b, a}.

Für "(a, b) $\in R$ " schreibt man meist "a R b". Sehr oft ist dabei die Menge A = B, also $R \sube A \times A$ , die Relation heißt dann auch homogen.

Relationen können als Funktionen gesehen werden, deren Definitionsmenge das kartesische Produkt der Mengen ist und deren Zielmenge lediglich wahr und falsch umfasst. Man könnte also auch R(a,b) für den Ausdruck der Relation schreiben. Umgekehrt kann man aber auch eine Funktion als eine spezielle (nämlich als eine linkstotale und rechtseindeutige) Relation auffassen (siehe unten). Ob man Funktionen als spezielle Relationen oder Relationen als spezielle Funktionen erklärt, bleibt willkürlich.

Beispiel

Relation.PNG

Eigenschaften

Die in der folgenden Tabelle gegebenen Beispiele beziehen sich bei Verwendung von Gleichheitszeichen "=", Kleinerzeichen "<" und Kleinergleich-Zeichen "≤" auf die gewöhnliche Anordnung reeller Zahlen.

Wichtige Eigenschaften von binären Relationen sind:

Die Relation heißt	wenn gilt	und das bedeutet	-	reflexiv (A = B)	$\forall a \in A : \ (a,a) \in R$	Jedes Element steht in Relation zu sich selbst, z. B. ist stets a≤a	-	irreflexiv	$\forall a \in A: \ (a,a) \ \not\in\ R$	Kein Element steht in Relation zu sich selbst, z. B. gilt a<a für kein a	-	symmetrisch (A = B)	$\forall {(a,b)} \in A^2: (a,b) \in R \ \Rightarrow \ (b,a) \in R$	Die Relation ist ungerichtet, z. B. folgt aus a=b stets b=a	-	asymmetrisch	$\forall {(a,b)} \in A^2: (a,b) \in R \ \Rightarrow \ (b,a) \ \not\in\ R$	Es gibt keine zwei Elemente, die in beiden Richtungen in Relation stehen, z. B. folgt aus a<b stets, dass b<a nicht gilt	-	antisymmetrisch bzw. identitiv (A = B)	$\forall {(a,b)} \in A^2: (a,b) \in R \, \and \, (b,a) \in R \ \Rightarrow \ a = b$	Es gibt keine zwei verschiedenen Elemente, die in beiden Richtungen in Relation stehen, z. B. folgt aus a≤b und b≤a stets a=b	-	transitiv (A = B)	$\forall{a,b,c} \in A: (a,b) \in R \and (b,c) \in R \Rightarrow (a,c) \in R$	Anfang und Ende einer verbundenen Sequenz sind verbunden, z. B. folgt aus a<b und b<c stets a<c	-	intransitiv	${\exist a,b,c}\in A: (a,b) \in R \, \and \, (b,c) \in R \, \and \, (a,c) \ \not\in\ R$	nicht bei jeder verbundenen Sequenz sind Anfang und Ende verbunden	-	antitransitiv	$\forall{a,b,c}\in A: (a,b) \in R \, \and \, (b,c) \in R \, \Rightarrow \, (a,c) \ \not\in\ R$	bei keiner verbundenen Sequenz sind Anfang und Ende verbunden	-	drittengleich (rechtskomparativ)	$\forall{a,b,c}\in A: (a,c) \in R \,\and\, (b,c) \in R \,\Rightarrow\, (a,b) \in R$	Stehen zwei Elemente jeweils zu einem dritten in Relation, dann stehen sie auch zueinander in Relation, z. B. folgt aus a=c und b=c auch a=b. Zu beachten ist, dass diese Forderung nicht äquivalent zur Transitivität ist.	-	drittengleich (linkskomparativ)	$\forall{a,b,c}\in A: (c,a) \in R \,\and\, (c,b) \in R \,\Rightarrow\, (a,b) \in R$	Siehe oben.	-	total bzw. linear bzw. konnex (A = B)	$\forall {a,b} \in A : (a,b) \in R \ \or\ (b,a) \in R$	Je zwei Elemente stehen in Relation, z. B. gilt stets a≤b oder b≤a	-	trichotomisch	$\forall {a,b} \in A : (a,b) \in R \ \dot\or\ (b,a) \in R \ \dot\or\ a = b$	Je zwei Elemente sind entweder gleich, oder stehen in genau einer Art und Weise zueinander in Relation.	-	linkstotal	$\forall a \in A: \exist b \in {B} : (a,b) \in R$	Jedes El. aus A hat mindestens einen Partner in B	-	surjektiv bzw. rechtstotal	$\forall b \in B: \exist a \in A: (a,b) \in R$	Jedes El. aus B hat mindestens einen Partner in A	-	injektiv bzw. linkseindeutig	$\forall a,c \in A: \forall b \in B: (a,b) \in R \and (c,b) \in R \Rightarrow a\,=\,c$	Kein El. aus B hat mehr als einen Partner in A	-	rechtseindeutig	$\forall a \in A: \forall b,c \in B: (a,b) \in R \and (a,c) \in R \Rightarrow b\,=\,c$	Kein El. aus A hat mehr als einen Partner in B	-	bijektiv bzw. eineindeutig (umkehrbar eindeutig)	$\forall a,c \in A: \forall b \in B: (a,b) \in R \and (c,b) \in R \Rightarrow a\,=\,c$ $\forall b \in B: \exist a \in A: (a,b) \in R$	Jedes El. aus B hat genau einen Partner in A	-	alternativ	$\forall a,b \in A, a \neq b: (a,b) \in R \Leftrightarrow (b,a) \ \not\in\ R$	Es gilt stets genau eine der Relationen a R b oder b R a

Relationen werden oft auch mit N:1 oder N:N und dergleichen charakterisiert. Dabei steht 1, wenn es rechts steht, für linkstotal und rechtseindeutig (und umgekehrt). N steht meistens für gar nichts. Manchmal wird auch 0 statt 1 verwendet, um die Totalität wegzulassen.

Relationszeichen

In der Mathematik gibt es drei Grundrelationen:

$x < y$ (Beispiel: 2 < 3 "2 ist kleiner als 3")
$x = y$ (Beispiel: 3 = 3 "3 ist gleich 3")
$x > y$ (Beispiel: 3 > 2 "3 ist größer als 2")

mit

x, y \in \R

Zwei Zahlen stehen immer in einer dieser Relationen zueinander. Mit diesen Relationszeichen lassen sich auch weitere erschaffen; so gilt:

$x \leq y$ , falls $x < y$ oder $x = y$ (Beispiel: $4 \leq 5$ )
$x \geq y$ , falls $x > y$ oder $x = y$ (Beispiel: $5 \geq 5$ )
$x \neq y$ , falls $x < y$ oder $x > y$ (Beispiel: $4 \neq 5$ )

für alle

x, y \in \R

Klassen von Relationen

Wichtige Klassen von Relationen:

Eine Äquivalenzrelation ist reflexiv, transitiv und symmetrisch.
Eine Funktion ist linkstotal und rechtseindeutig (d.h. N:1).
Eine Verträglichkeitsrelation ist reflexiv und symmetrisch . (Nicht notwendig transitiv.)
Eine Quasiordnung oder Präordnung ist reflexiv und transitiv. (Nicht notwendig symmetrisch oder antisymmetrisch.)
Eine Halbordnung oder partielle Ordnung ist reflexiv, transitiv und antisymmetrisch. (Halbordnung = Präordnung + antisymmetrisch)
Eine lineare Ordnung oder totale Ordnung ist reflexiv, transitiv, antisymmetrisch und total (linear). (lineare Ordnung = Halbordnung + total)
Eine strenge Halbordnung oder Striktordnung ist transitiv und irreflexiv.
Eine lineare Striktordnung oder strenge Totalordnung ist eine trichotomische Striktordnung.
Achtung: eine lineare Striktordnung ist nicht linear, eine strenge Totalordnung nicht total!
Eine Wohlordnung ist eine lineare Ordnung, bei der jede nichtleere Teilmenge von A ein kleinstes Element besitzt.

Alternative Sprechweisen

Zu linkseindeutig sagt man auch injektiv oder voreindeutig.
Zu linkstotal sagt man auch vordefiniert.
Zu rechtseindeutig sagt man auch nacheindeutig.
Zu rechtstotal sagt man auch surjektiv oder nachdefiniert.
Zu eineindeutig sagt man auch bijektiv.

Siehe auch

Operationen auf ganzen Relationen werden in der relationalen Algebra behandelt.
In der Informatik sind Relationen für relationale Datenbanken wichtig.

Mengenlehre | Logik

Gourt Home::Gourt :: Relation (Mathematik)