Relation (Mathematik)
Eine (binäre) Relation ordnet Elementen einer Menge Elemente einer zweiten Menge zu (oder auch derselben).
Definition: Eine binäre Relation ist eine Teilmenge des kartesischen Produkts zweier Mengen.
- R ⊆ A × B
Für (a,b) ∈ R schreibt man meist a R b. Sehr oft ist dabei A = B. Allgemeiner ist eine n-stellige Relation eine Teilmenge des kartesischen Produkts von n Mengen A1, ..., An.
Relationen können als Funktionen gesehen werden, deren Definitionsmenge das kartesische Produkt der Mengen ist und deren Wertemenge lediglich wahr und falsch umfasst. Man könnte also auch R (a,b) für den Ausdruck der Relation schreiben.
Wichtige Eigenschaften von binären 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 |
| irreflexiv (A = B) | ∀ a ∈ A: ¬ a R a | Kein 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 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 |
| 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 |
| alternativ oder linear (A = B) | ∀ a,b: entweder 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.
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.