Relation (Mathematik)

Eine Relation ist in der Mathematik eine Zusammenstellung oder Zuordung von Elementen aus einer oder mehr Mengen. Eine 2-stellige (binäre) Relation ordnet den Elementen einer Menge die Elemente einer zweiten Menge zu. Die zwei Mengen müssen nicht verschieden sein, so können die sich zugeordneten Elemente auch aus ein und derselben Menge stammen.

Table of contents

1 Definition 2 Erläuterungen 3 Beispiel 4 Eigenschaften 5 Klassen von Relationen 6 Siehe auch

Definition

Eine binäre Relation R ist eine Teilmenge des kartesischen Produkts zweier Mengen:

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 Gegesatz zu der ungeordneten Menge {a,b}, die identisch ist mit {b,a}. Siehe auch: Tupel

Für "(a, b) " schreibt man meist "a R b". Sehr oft ist dabei die Menge A = B, also . Relationen können als Funktionenen gesehen werden, deren Definitionsmenge das kartesische Produkt der Mengen ist und deren Wertemenge lediglich wahr und falsch umfasst. (Was etwas verwirrend sein könnte, denn eine Funktion ist eine spezielle Relation, siehe Tabelle unten.) Man könnte also auch R(a,b) für den Ausdruck der Relation schreiben.

Beispiel

Eigenschaften

Wichtige Eigenschaften von binären Relationen sind:

Die Relation heißt	wenn gilt	und das bedeutet
reflexiv (A = B)		Jedes Element steht in Relation zu sich selbst
irreflexiv (A = B)		Kein Element steht in Relation zu sich selbst
symmetrisch (A = B)		Die Relation ist ungerichtet
antisymmetrisch bzw. identitiv (A = B)		Es kann z.B. nicht a kleiner b und b kleiner a sein.
transitiv (A = B)	∀ a,b,c ∈ A: a R b ∧ b R c ⇒ a R c	Anfang und Ende einer verbundenen Sequenz sind verbunden
intransitiv	nicht transitiv	nicht bei jeder verbundenen Sequenz sind Anfang und Ende verbunden
antitransitiv	∀ a,b,c ∈ A: a R b ∧ b R c ⇒ ¬ a R c	bei keiner verbundenen Sequenz sind Anfang und Ende verbunden
Funktion		Jedem (für alle) a wird genau ein b zugeordnet. A ist Definitionsmenge und B die Wertemenge
total bzw. linear (A = B)		Je zwei Elemente stehen in Relation
linkstotal	∀ a ∈ A ∃ b ∈ B: a R b	Jedes El. aus A hat einen Partner in B
rechtstotal	∀ b ∈ B ∃ a ∈ A: a R b	Jedes El. aus B hat einen Partner in A
linkseindeutig	∀ a,c ∈ A ∀ b ∈ B: a R b ∧ c R b ⇒ a = c	Kein El. aus B hat mehr als einen Partner in A
rechtseindeutig	∀ a ∈ A ∀ b,c ∈ B: a R b ∧ a R c ⇒ b = c	Kein El. aus A hat mehr als einen Partner in B
alternativ (A = B)	∀ a,b: a R b ¬ b R a	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.

Klassen von Relationen

Wichtige Klassen von Relationen:

• Eine Funktion ist linkstotal und rechtseindeutig (d.h. N:1).
• Eine Ordnungsrelation ist reflexiv, transitiv und antisymmetrisch.
• Eine Äquivalenzrelation ist reflexiv, transitiv und symmetrisch.

Siehe auch

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