Relation (Mathematik)

Eine Relation (engl.: relation) ordnet Elementen einer Menge Elemente einer zweiten Menge zu (oder auch derselben).

Definition: Eine Relation ist eine Teilmenge des kartesischen Produkts zweier Mengen.

R ⊆ A × B

Ist (a, b) ein Element von R, dann schreibt man meist a R b.

Sehr oft ist A = B .

Relationen sind Funktionen, da sie Zuordnungen sind. Man könnte also auch R(a,b) für den Ausdruck der Relation schreiben.

Wichtige Eigenschaften von Relationen sind:

Die Relation heißt	wenn gilt	und das bedeutet
reflexiv (A = B)	∀ a ∈ A: a R a	Jedes Element steht in Relation zu sich selbst
symmetrisch (A = B)	∀ a,b ∈ A: a R b ⇒ b R a	Die Relation ist ungerichtet
antisymmetrisch (A = B)	∀ a,b ∈ A: a R b ∧ b R a ⇒ 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 verb. Sequenz sind verbunden
total (A = B)	∀ a,b ∈ A: a R b ∨ b R a	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

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.

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.

Operationen auf ganzen Relationen werden in der relationalen Algebra behandelt.

In der Informatik sind Relationen für relationale Datenbanken wichtig.