Infos Home | Impressum | Original Artikel & Autoren Liste

Relation (Mathematik)

Dieser Artikel enth�lt mathematische Symbole. Diese werden in der Tabelle mit mathematischen Symbolen erl�utert.

Eine Relation ist eine Beziehung zwischen Dingen. Eine Relation im Sinne der Mathematik ist eine Beziehung, die zwischen gewissen Dingen gegeben, zwischen anderen Dingen nicht gegeben sein kann - es gibt also keine Zwischenabstufungen; Dinge können 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 Element von R ist.

Wenn nicht ausdrücklich anderes angegeben ist, versteht man unter einer Relation eine "zweistellige" oder "binäre" Relation, also eine Beziehung zwischen je zwei Dingen. Die Tupel sind in diesem Fall Paare. Die 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.

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

Definition

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

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 Gegensatz zu der ungeordneten Menge {a,b}, die identisch ist mit {b,a}.

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. Man könnte also auch R(a,b) für den Ausdruck der Relation schreiben. Umgekehrt kann man aber auch eine Funktion als eine spezielle (nämlich als eine linkstotale und rechtseindeutige) Relation auffassen (siehe unten). Ob man Funktionen als spezielle Relationen oder Relationen als spezielle Funktionen erklärt, bleibt willkürlich.

Beispiel

Eigenschaften

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

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, z.B. ist stets a≤a
irreflexiv (A = B)

Kein Element steht in Relation zu sich selbst, z.B. gilt a<a für kein a
symmetrisch (A = B)

Die Relation ist ungerichtet, z.B. folgt aus a=b stets b=a
asymmetrisch (A = B)

Es gibt keine zwei Elemente, die in beiden Richtungen in Relation stehen, z.B. folgt aus a<b stets, dass b<a nicht gilt
antisymmetrisch bzw. identitiv (A = B)

Es gibt keine zwei verschiedenen Elemente, die in beiden Richtungen in Relation stehen, z.B. folgt aus a≤b und b≤a stets a=b
transitiv (A = B)

Anfang und Ende einer verbundenen Sequenz sind verbunden, z.B. folgt aus a<b und b<c stets a<c
intransitiv

nicht transitiv

nicht bei jeder verbundenen Sequenz sind Anfang und Ende verbunden
antitransitiv

bei keiner verbundenen Sequenz sind Anfang und Ende verbunden
drittengleich (rechtskomparativ)

Stehen zwei Elemente jeweils zu einem dritten in Relation, dann stehen sie auch zueinander in Relation, z.B. folgt aus a=c und b=c auch a=b. Zu beachten ist, dass diese Forderung nicht äquivalent zur Transitivität ist.
drittengleich (linkskomparativ)

Siehe oben.
Funktion

Jedem a wird genau ein b zugeordnet. A heißt Definitionsmenge und B Wertemenge
total bzw. linear (A = B)

Je zwei Elemente stehen in Relation, z.B. gilt stets a≤b oder b≤a
trichotomisch

Je zwei Elemente sind entweder gleich, oder stehen in genau einer Art und Weise zueinander in Relation.
linkstotal

Jedes El. aus A hat einen Partner in B
rechtstotal

Jedes El. aus B hat einen Partner in A
linkseindeutig

Kein El. aus B hat mehr als einen Partner in A
rechtseindeutig

Kein El. aus A hat mehr als einen Partner in B
alternativ (A = B)

Es gilt stets genau eine der Relationen a R b oder b R a

Die Relation heißt	wenn gilt	und das bedeutet
reflexiv (A = B)		Jedes Element steht in Relation zu sich selbst, z.B. ist stets a≤a
irreflexiv (A = B)		Kein Element steht in Relation zu sich selbst, z.B. gilt a<a für kein a
symmetrisch (A = B)		Die Relation ist ungerichtet, z.B. folgt aus a=b stets b=a
asymmetrisch (A = B)		Es gibt keine zwei Elemente, die in beiden Richtungen in Relation stehen, z.B. folgt aus a<b stets, dass b<a nicht gilt
antisymmetrisch bzw. identitiv (A = B)		Es gibt keine zwei verschiedenen Elemente, die in beiden Richtungen in Relation stehen, z.B. folgt aus a≤b und b≤a stets a=b
transitiv (A = B)		Anfang und Ende einer verbundenen Sequenz sind verbunden, z.B. folgt aus a<b und b<c stets a<c
intransitiv	nicht transitiv	nicht bei jeder verbundenen Sequenz sind Anfang und Ende verbunden
antitransitiv		bei keiner verbundenen Sequenz sind Anfang und Ende verbunden
drittengleich (rechtskomparativ)		Stehen zwei Elemente jeweils zu einem dritten in Relation, dann stehen sie auch zueinander in Relation, z.B. folgt aus a=c und b=c auch a=b. Zu beachten ist, dass diese Forderung nicht äquivalent zur Transitivität ist.
drittengleich (linkskomparativ)		Siehe oben.
Funktion		Jedem a wird genau ein b zugeordnet. A heißt Definitionsmenge und B Wertemenge
total bzw. linear (A = B)		Je zwei Elemente stehen in Relation, z.B. gilt stets a≤b oder b≤a
trichotomisch		Je zwei Elemente sind entweder gleich, oder stehen in genau einer Art und Weise zueinander in Relation.
linkstotal		Jedes El. aus A hat einen Partner in B
rechtstotal		Jedes El. aus B hat einen Partner in A
linkseindeutig		Kein El. aus B hat mehr als einen Partner in A
rechtseindeutig		Kein El. aus A hat mehr als einen Partner in B
alternativ (A = B)		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 Ä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 transitiv.)
Eine Quasiordnung oder Präordnung ist transitiv und reflexiv. (Nicht notwendig symmetrisch oder antisymmetrisch.)
Eine lineare Ordnung oder totale Ordnung ist eine Halbordnung, die zusätzlich total (linear) ist.
Eine strenge Halbordnung oder Striktordnung ist transitiv und irreflexiv.
Eine lineare Striktordnung oder strenge Totalordnung ist eine trichotomische Striktordnung.Achtung: eine lineare Striktordnung ist nicht linear, eine strenge Totalordnung nicht total!
Eine Wohlordnung ist eine lineare Ordnung, bei jede nichtleere Teilmenge von A ein kleinstes Element besitzt.

Siehe auch

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

Symmetrie_(wiskunde)
Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.