Relation (Mathematik)

Eine Relation ist eine Beziehung zwischen Dingen. Eine im Sinne der Mathematik ist eine Beziehung die zwischen gewissen gegeben zwischen anderen Dingen nicht gegeben sein - es gibt also keine Zwischenabstufungen; Dinge nicht "ein bisschen" zueinander in Relation stehen.

Diese Festlegung ermöglicht eine einfache mengentheoretische Definition des Begriffs Relation: eine Relation R ist eine Menge von Tupeln . Dinge die in der Relation R zueinander stehen bilden ein Tupel das von R ist.

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

Inhaltsverzeichnis

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

Definition

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

<math>R \sube A \times B \ mit \ \ A \times B:= \{ b) \ |\ a \in A \ \ b\in B \}</math>

Allgemeiner ist eine n -stellige Relation eine Teilmenge des kartesischen Produkts n Mengen A ₁ ... A _n .

Erläuterungen

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

Für "( a b ) <math>\in R</math>" schreibt man meist " a R b ". Sehr oft ist dabei die Menge A = B also <math>R \sube A \times A

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

Beispiel

Eigenschaften

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

Wichtige Eigenschaften von binären Relationen sind:

Die Relation heißt	wenn gilt	und das bedeutet
reflexiv ( A = B )	<math>\forall a \in A : \ a) \in R </math>	Jedes Element steht in Relation zu selbst z.B. ist stets a ≤ a
irreflexiv ( A = B )	<math>\not{\exist} \ a \in A: \ a) \in R</math>	Kein Element steht in Relation zu selbst z.B. gilt a < a für kein a
symmetrisch ( A = B )	<math>\forall {(a b)} \in A^2: (a \in R \ \Rightarrow \ (b a) R</math>	Die Relation ist ungerichtet z.B. folgt a = b stets b = a
asymmetrisch ( A = B )	<math>\forall {(a b)} \in A^2: (a \in R \ \Rightarrow \ \neg (b \in R</math>	Es gibt keine zwei Elemente die beiden Richtungen in Relation stehen z.B. folgt a < b stets dass b < a nicht gilt
antisymmetrisch bzw. identitiv ( A = B )	<math>\forall {(a b)} \in A^2: (a \in R \ \and \ (b a) R \ \Rightarrow \ a = b</math>	Es gibt keine zwei verschiedenen Elemente die in beiden Richtungen in stehen z.B. folgt aus a ≤ b und b ≤ a stets a = b
transitiv ( A = B )	∀ a b c ∈ A : a R b ∧ b R c ⇒ a R c	Anfang und Ende einer verbundenen Sequenz verbunden z.B. folgt aus a < b und b < c stets a < c
intransitiv	nicht transitiv	nicht bei jeder verbundenen Sequenz sind und Ende verbunden
antitransitiv	∀ a b c ∈ A : a R b ∧ b R c ⇒ ¬ a R c	bei keiner verbundenen Sequenz sind Anfang Ende verbunden
Funktion	<math>\forall {a} \in A : \exist_1 b \in {B} : (a b) \in	Jedem a wird genau ein b zugeordnet. A heißt Definitionsmenge und B Wertemenge
total bzw. linear ( A = B )	<math>\forall {a b} \in A : \mathrm{R}\ b \ \or\ b\ \mathrm{R}\ a</math>	Je zwei Elemente stehen in Relation gilt stets a ≤ b oder b ≤ a
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 <math>\Leftrightarrow</math> ¬ b a	Es gilt stets genau eine der a R b oder b R a

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

Klassen von Relationen

Wichtige Klassen von Relationen:

• Eine Äquivalenzrelation ist reflexiv transitiv und symmetrisch.
• Eine Halbordnung ist reflexiv transitiv und antisymmetrisch.
• Eine Funktion ist linkstotal und rechtseindeutig (d.h. N:1).
• Eine Verträglichkeitsrelation ist reflexiv und symmetrisch. (Nicht notwendig
• Eine Quasiordnung oder Präordnung ist transitiv und reflexiv. (Nicht notwendig oder antisymmetrisch.)
• Eine lineare Ordnung oder totale Ordnung ist eine Halbordnung die zusätzlich total ist.
• Eine strenge Halbordnung oder Striktordnung ist transitiv und irreflexiv.
• Eine lineare Striktordnung oder strenge Totalordnung ist eine Striktordnung bei der je verschiedene Elemente in einer der beiden Richtungen Relationen stehen (also a R b oder b R a gilt)
• Eine Wohlordnung ist eine lineare Ordnung bei jede Teilmenge von A ein kleinstes Element besitzt.

Siehe auch

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

Symmetrie_(wiskunde)

Bücher zum Thema Relation (Mathematik)

Dieser Artikel von Wikipedia unterliegt der GNU FDL.