3. Relationen
Relationen drücken Beziehungen zwischen Objekten aus. Mengentheoretisch können wir dies ebenso einfach wie allgemein definieren:
Definition (Relation)
Eine Menge R heißt eine (zweistellige) Relation auf einer Menge A, falls R ⊆ A × A. Allgemeiner heißt R eine n-stelllige Relation auf A, falls R ⊆ An.
Dass a in einer bestimmten Beziehung zu b steht, wird also durch (a, b) ∈ R zum Ausdruck gebracht. Wir vereinbaren suggestive Schreibweisen:
Notation | Bedeutung | Bezeichnung | Lesart |
a R b | (a, b) ∈ R | Relationsnotation | a steht in Relation R zu b, a R b |
a R b R c | a R b ∧ b R c | Kettennotation | a R b R c |
Wichtige Begriffe im Umfeld von zweistelligen Relationen sind:
Objekt | Definition | Bezeichnung | Lesart |
dom(R), Def (R) | { a | ∃b a R b } | Definitionsbereich, Domain | Domain von R |
rng(R) | { b | ∃a a R b } | Wertebereich, Range | Range von R |
field(R) | dom(R) ∪ rng(R) | Feld | Feld von R |
R− 1 | { (b, a) | (a, b) ∈ R } | Umkehrrelation | R hoch minus 1 |
R ∘ S | { (a, c) | ∃b (a R b ∧ b R c) } | (relationale) Verknüpfung, Komposition | R Kringel S |
R2, R3, … | R ∘ R, R ∘ R ∘ R, … | R hoch 2, 3, … |
Eigenschaften von Relationen
Für jede (im Folgenden immer zweistellige) Relation können wir folgende Eigenschaften betrachten:
Eigenschaft | Definition |
R ist linkseindeutig | ∀a, b, c (a R c ∧ b R c → a = b) |
R ist rechtsseindeutig | ∀a, b, c (a R b ∧ a R c → b = c) |
R ist reflexiv auf A | ∀a ∈ A a R a |
R ist irreflexiv | ¬∃a a R a |
R ist symmetrisch | ∀a, b (a R b → b R a) |
R ist antisymmetrisch | ∀a, b (a R b ∧ b R a → a = b) |
R ist transitiv | ∀a, b, c (a R b ∧ b R c → a R c) |
R ist konnex auf A | ∀a, b ∈ A (a R b ∨ b R a) |
R ist semikonnex auf A | ∀a, b ∈ A (a R b ∨ a = b ∨ b R a) |
Durch Kombinationen der Eigenschaften lassen sich wichtige relationale Strukturen beschreiben:
Begriff für eine Relation auf A | Definition |
R ist eine Äquivalenzrelation | R ist reflexiv, symmetrisch, transitiv |
< ist eine partielle Ordnung (vom strikten Typ) | < ist irreflexiv, transitiv |
≤ ist eine partielle Ordnung (von nichtstrikten Typ) | ≤ ist reflexiv, antisymmetrisch, transitiv |
< ist eine lineare oder totale Ordnung (vom strikten Typ) | < ist eine semikonnexe partielle Ordnung vom strikten Typ |
≤ ist eine lineare oder totale Ordnung (vom strikten Typ) | ≤ ist eine konnexe partielle Ordnung vom nichtstrikten Typ |