Relation (Mathematik)

Eine Relation ist allgemein eine Beziehung, die zwischen Dingen bestehen kann. Relationen im Sinne der Mathematik sind ausschließlich diejenigen Beziehungen, bei denen stets klar ist, ob sie bestehen oder nicht. Zwei Gegenstände können also nicht „bis zu einem gewissen Grade“ in einer Relation zueinander stehen. Damit ist eine einfache mengentheoretische Definition des Begriffs möglich: Eine Relation R ist eine Menge von n-Tupeln. Dinge, die in der Relation R zueinander stehen, bilden ein n-Tupel, das Element von R ist.

Wenn nicht ausdrücklich etwas anderes angegeben ist, versteht man unter einer Relation eine zweistellige oder binäre Relation, also eine Beziehung zwischen je zwei Dingen; diese bilden dann genau geordnete Paare. Stammen die Elemente eines Paares $(a,b)$ aus verschiedenen Grundmengen A und B, so heißt die Relation heterogen oder „Relation zwischen den Mengen A und B“. Wenn die Grundmengen übereinstimmen, A = B, heißt die Relation homogen oder „Relation in bzw. auf der Menge A“.

Wichtige Spezialfälle, zum Beispiel Äquivalenzrelationen und Ordnungsrelationen, sind Relationen in einer Menge.

Definitionen

Zweistellige Relation

Eine zweistellige Relation $R$ zwischen zwei Mengen $A$ und $B$ ist eine Teilmenge des kartesischen Produkts $A\times B=\{(a,b)\mid a\in A,b\in B\}\colon$

$R\subseteq A\times B.$

Die Menge $A$ wird als Vorbereich oder Quellmenge der Relation $R$ bezeichnet; die Menge $B$ als Nachbereich oder Zielmenge.

Manchmal ist diese Definition jedoch nicht präzise genug und man bezieht die Quell- und Zielmenge in die Definition mit ein; obige Teilmenge wird dann der Graph $G_{R}$ der Relation genannt. Eine zweistellige Relation $R$ ist dann definiert als Tripel

$R=(G_{R},A,B)\;{\text{ mit }}\,G_{R}=\mathrm {Graph} (R)\subseteq A\times B.$

Die Kenntnis von Quelle und Zielmenge ist insbesondere dann von Bedeutung, wenn man Funktionen als spezielle (sogenannte funktionale) Relationen betrachtet.

Mehrstellige Relation

Allgemeiner ist eine $n$-stellige Relation $R$ eine Teilmenge des kartesischen Produkts von $n$ Mengen $A_{1},\ldots ,A_{n}$

$R\subseteq A_{1}\times \ldots \times A_{n}\;{\text{ mit }}\,A_{1}\times \ldots \times A_{n}=\{(a_{1},\ldots ,a_{n})\mid a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}\}.$

Die ausführlichere Definition lässt sich auch auf $n$-stellige Relationen verallgemeinern und man erhält dann das $(n+1)$-Tupel

$R=(G_{R},A_{1},\ldots ,A_{n})\;{\text{ mit }}\,G_{R}=\mathrm {Graph} (R)\subseteq A_{1}\times \ldots \times A_{n}.$

Erläuterungen und Schreibweisen

Das kartesische Produkt zweier Mengen $A$ und $B$ 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)$ unterscheidet sich von $(b,a),$ im Gegensatz zum ungeordneten Paar $\{a,b\},$ das identisch ist mit $\{b,a\}.$ Für $(a,b)\in R$ schreibt man auch $a\;R\;b$, um zu verdeutlichen, dass jene Beziehung zwischen den Objekten besteht.

Relationen und Funktionen

Eine Funktion ist eine spezielle, nämlich eine linkstotale und rechtseindeutige (binäre) Relation $f\subseteq A\times B$ (siehe unten). Bei der ausführlicheren Definition $f=(G_{f},A,B)$ kann, weil $A$ durch $G_{f}$ eindeutig bestimmt ist (linkstotal), auch $A$ weggelassen und einfacher $f=(G_{f},B)$ genommen werden. An Stelle von $f\subseteq A\times B$ bzw. $G_{f}\subseteq A\times B$ wird dann $f\colon \,A\to B$ und für $(a,b)\in f$ bzw. $(a,b)\in G_{f}$ auch $f\colon \,a\mapsto b$ oder $f(a)=b$ geschrieben.

Eine Relation $R\subseteq A\times B$ entspricht auf eindeutige Weise einer Funktion $f_{R}\colon \,A\times B\to \{wahr,falsch\}.$ Diese Funktion ist auch als Indikatorfunktion oder charakteristische Funktion der Teilmenge $R\subseteq A\times B$ bzw. $G_{R}\subseteq A\times B$ bekannt, wobei $\{wahr,falsch\}$ durch $\{1,0\}$ ersetzt werden kann.

$R\subseteq A\times B$ lässt sich ebenso als eine Abbildung $i_{R}$ von $A$ in die Potenzmenge von $B$ auffassen, $i_{R}\colon \,a\mapsto \{b\in B\mid (a,b)\in R\},$ man spricht dann oft von einer Korrespondenz.

Verkettung von Relationen

Eine Relation $R\subseteq A\times B$ und eine Relation $S\subseteq B\times C$ können miteinander verkettet werden. Das Ergebnis ist die Relation:

$RS=S\circ R=\{(a,c)\in A\times C\mid \exists ~b\in B:(a,b)\in R\land (b,c)\in S\}.$

Die Relation nennt man Relationsprodukt oder relatives Produkt. Dieses ist eine Verallgemeinerung des bekannteren Konzepts der Verkettung von Funktionen.

Beispiel: Die Relation „Schwägerin sein von“ ist die Vereinigungsmenge

• des relativen Produktes der Relation „Bruder sein von“ und der Relation „Ehefrau sein von“ und
• des relativen Produktes der Relation „Ehepartner(in) sein von“ und der Relation „Schwester sein von“.

Homogene Relationen

Ist $A=B,$ also $R\subseteq A\times A,$ dann nennt man die Relation homogen. In diesem Fall ist die Verkettung $R\circ R$ ebenfalls eine homogene Relation. Hier ist die Schreibweise $R^{2}=R\circ R$ und allgemeiner $R^{n}$ für $n\in \mathbb {N} \setminus \{0,1\}$ gebräuchlich. Das kann zu Verwechslungen mit dem kartesischen Produkt $M^{2}=M\times M$ führen, das sich natürlich auch aus Relationen bilden lässt. Die Bedeutung ergibt sich aus dem Sinnzusammenhang. Manche Autoren definieren eine allgemeine Relation bereits als homogene Relation, denn eine allgemeine Relation $R\subseteq A\times B$ ist auch immer homogen: $R\subseteq (A\cup B)\times (A\cup B).$

Die einfachste Relation, die in jedem kartesischen Produkt enthalten ist, ist die leere Relation oder Nullrelation (leere Menge)

$\mathrm {O} :=\emptyset .$

Eine spezielle homogene Relation ist die Diagonale $\Delta _{A}$ (oder auch nur $\Delta$; gelegentlich auch als $R^{0}$ notiert) auf einer Menge A. Dies ist nichts anderes als die Gleichheitsrelation als Teilmenge des kartesischen Produkts $A\times A$ geschrieben:

$\Delta _{A}=\{(a,b)\in A\times A\mid a=b\}=\{(a,a)\mid a\in A\}.$

Diese Schreib- und Sprechweise kann verwendet werden, um gewisse Eigenschaften von Relationen in Mengenschreibweise kurz darzustellen.

Eine weitere spezielle homogene Relation ist die Allrelation oder Universalrelation

$\mathrm {U} _{A}:=A\times A,$

die etwa in der Graphentheorie eine Rolle spielt. Ein Anwendungsbeispiel ist folgender Satz:

Ist $\mathbf {G} =(E,K)$ ein gerichteter Graph mit einer Menge $E$ von Ecken und einer (assoziierten) Relation $K\subseteq E\times E$ von Kanten, so ist $\mathbf {G}$ genau dann (stark) zusammenhängend, wenn die reflexiv-transitive Hülle von $K$ die Allrelation ist.

Umkehrrelation

Die Umkehrrelation (auch konverse Relation, Konverse oder inverse Relation genannt) ist für eine Relation $R\subseteq A\times B$ definiert als

$R^{-1}=\{(b,a)\in B\times A\mid (a,b)\in R\}.$

Beispiel 1: Die Umkehrrelation der Relation „Ehemann sein von“ ist die Relation „Ehefrau sein von“.

Beispiel 2: Die Umkehrrelation der Relation „kleiner als“ ist die Relation „größer als“.

Beispiel 3: Die Umkehrrelation der Relation „liefert an“ ist die Relation „wird beliefert von“.

Beispiel

Alle möglichen Kombinationen von den Elementen aus der Menge $A:=\{a,b,c\}$ und $B:=\{x,y,z\}$, sowie eine zwischen $A$ und $B$ definierte Relation $R\colon$

Eigenschaften (zweistellig)

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

Attribute für homogene Relationen

Die folgenden Attribute beschreiben gemeinsam eine Äquivalenzrelation, die Attribute reflexiv und transitiv sind auch für Ordnungsrelationen gebräuchlich:

Die Relation heißt	wenn gilt (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet
reflexiv	$\forall a\in A\colon (a,a)\in R,$	$\Delta \subseteq R$	Jedes Element steht in Relation zu sich selbst, z. B. ist stets a≤a.
symmetrisch	${\begin{aligned}\forall a,b&\in A\colon (a,b)\in R\\\Rightarrow \,&(b,a)\in R\end{aligned}}$	$R\subseteq R^{-1}\,\lor \,R=R^{-1}$	Die Relation ist ungerichtet, z. B. folgt aus a = b stets b = a (und umgekehrt)
transitiv	${\begin{aligned}\forall a,b,c&\in A\colon \\&(a,b)\in R\land (b,c)\in R\\\Rightarrow \,&(a,c)\in R\end{aligned}}$	$R\circ R\subseteq R$	Anfang und Ende einer verbundenen Sequenz sind verbunden, z. B. folgt aus a < b und b < c stets a < c.

Die folgenden Attribute werden zur Kennzeichnung von Ordnungsrelationen ebenfalls gebraucht:

Die Relation heißt	wenn gilt (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet
irreflexiv (antireflexiv)	$\forall a\in A\colon (a,a)\notin R$	$\Delta \cap R=\emptyset$	Kein Element steht in Relation zu sich selbst, z. B. gilt a < a für kein a.
asymmetrisch	${\begin{aligned}\forall a,b&\in A\colon \\&(a,b)\in R\\\Rightarrow \,&(b,a)\notin R\end{aligned}}$	$R\cap R^{-1}=\emptyset$	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 für beliebige bzw. identitiv für homogene Relationen	${\begin{aligned}\forall a,b&\in A\colon \\&(a,b)\in R\land (b,a)\in R\\\Rightarrow \,&a=b\end{aligned}}$	$R\cap R^{-1}\subseteq \Delta$	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.
total, vollständig oder linear	${\begin{aligned}\forall a,b&\in A\colon \\&(a,b)\in R\lor (b,a)\in R\end{aligned}}$	$R\cup R^{-1}=A\times A$	Je zwei Elemente stehen in Relation, z. B. wenn stets a ≤ b oder b ≤ a gilt.
konnex	${\begin{aligned}\forall a,b&\in A\colon \\&a\neq b\\\Rightarrow \,&(a,b)\in R\lor (b,a)\in R\end{aligned}}$	$\Delta \cup R\cup R^{-1}=A\times A$	Je zwei verschiedene Elemente stehen in Relation, z. B. wenn stets a = b, a < b oder b < a, aber ebenso wenn stets a ≤ b oder b ≤ a gilt.
alternativ	${\begin{aligned}\forall a,b&\in A,a\neq b\colon \\&(a,b)\in R\\\Leftrightarrow \,&(b,a)\notin R\end{aligned}}$	${\begin{aligned}\Delta \cup R\cup R^{-1}&=A\times A\\\land \;R\cap R^{-1}&=\emptyset \end{aligned}}$	Je zwei verschiedene Elemente stehen stets auf genau eine Weise in Relation, z. B. wenn stets entweder a = b, a < b oder b < a gilt.

Die folgenden Attribute sind besonders zur Beschreibung von Verknüpfungen gebräuchlich.

Die Relation heißt	wenn gilt (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet
drittengleich oder rechtskomparativ	${\begin{aligned}\forall a,b,c&\in A:\\&(a,c)\in R\land \ (b,c)\in R\\\Rightarrow \,&(a,b)\in R\end{aligned}}$	$R^{-1}\circ R\subseteq R$	Stehen zwei Elemente jeweils zu einem dritten in Relation, dann stehen sie auch zueinander in Relation. Zu beachten ist, dass diese Forderung nicht äquivalent zur Transitivität ist.
drittengleich oder linkskomparativ	${\begin{aligned}\forall a,b,c&\in A:\\&(c,a)\in R\land (c,b)\in R\\\Rightarrow \,&(a,b)\in R\end{aligned}}$	$R\circ R^{-1}\subseteq R$

Die folgenden Attribute werden seltener gebraucht:

Die Relation heißt	wenn gilt (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet
intransitiv	${\begin{aligned}\exists a,b,c&\in A:\\&(a,b)\in R\land (b,c)\in R\\\land &(a,c)\notin R\end{aligned}}$	$R\circ R\not \subseteq R$	Nicht bei jeder verbundenen Sequenz sind Anfang und Ende verbunden.
antitransitiv	${\begin{aligned}\forall a,b,c&\in A:\\&(a,b)\in R\land (b,c)\in R\\\Rightarrow \,&(a,c)\notin R\\\end{aligned}}$	$(R\circ R)\cap R=\emptyset$	Bei keiner verbundenen Sequenz sind Anfang und Ende verbunden.

Intransitivität und Antitransitivität sind nicht zu verwechseln mit negativer Transitivität.

Attribute für Relationen zwischen verschiedenen Mengen

Die folgenden Relationen sind für Funktionen (dargestellt als spezielle Relationen) wichtig. Im Allgemeinen besteht hier die Relation $R\subseteq A\times B$ zwischen zwei verschiedenen Mengen $A,B,$ der Fall $A=B$ ist natürlich auch möglich.

Die Relation heißt	wenn gilt (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet
linkstotal bzw. definal	$\forall a\in A\;\exists b\in {B}\colon (a,b)\in R$	$\Delta _{A}\subseteq R^{-1}\circ R$	Jedes Element aus $A$ hat mindestens einen Partner in $B.$
rechtstotal bzw. surjektiv	$\forall b\in B\;\exists a\in A\colon (a,b)\in R$	$\Delta _{B}\subseteq R\circ R^{-1}$	Jedes Element aus $B$ hat mindestens einen Partner in $A.$
linkseindeutig bzw. injektiv	${\begin{aligned}&\forall b\in B\;\forall a,c\in A\colon \\&(a,b),(c,b)\in R\Rightarrow a=c\end{aligned}}$	$R^{-1}\circ R\subseteq \Delta _{A}$	Jedes Element aus $B$ hat höchstens einen Partner in $A.$
rechtseindeutig oder eindeutig bzw. funktional	${\begin{aligned}&\forall a\in A\;\forall b,d\in B\colon \\&(a,b),(a,d)\in R\Rightarrow b=d\end{aligned}}$	$R\circ R^{-1}\subseteq \Delta _{B}$	Jedes Element aus $A$ hat höchstens einen Partner in $B.$
Abbildung bzw. Funktion	$\forall a\in A\;\exists !b\in B\colon (a,b)\in R$	${\begin{aligned}&\Delta _{A}\subseteq R^{-1}\circ R\\\land \;\;&R\circ R^{-1}\subseteq \Delta _{B}\end{aligned}}$	Jedes Element aus $A$ hat genau einen Partner in $B.$
bijektiv	$\forall b\in B\;\exists !a\in A\colon (a,b)\in R$	${\begin{aligned}&\Delta _{B}\subseteq R\circ R^{-1}\\\land \;\;&R^{-1}\circ R\subseteq \Delta _{A}\end{aligned}}$	Jedes Element aus $B$ hat genau einen Partner in $A.$
eineindeutig	${\begin{aligned}&\forall a,c\in A\;\forall b,d\in B\colon \\&(a,b),(c,b)\in R\Rightarrow a=c,\\&(a,b),(a,d)\in R\Rightarrow b=d\end{aligned}}$	${\begin{aligned}&R^{-1}\circ R\subseteq \Delta _{A}\\\land \;\;&R\circ R^{-1}\subseteq \Delta _{B}\end{aligned}}$	Jedes Element aus $A$ hat höchstens einen Partner in $B$ und umgekehrt.
umkehrbar eindeutig bzw. Bijektion	${\begin{aligned}&\forall a\in A\;\forall b\in B\;\exists !d\in B\;\exists !c\in A\colon \\&(a,d)\in R\,\;\land \,\;(c,b)\in R\end{aligned}}$	${\begin{aligned}&R^{-1}\circ R=\Delta _{A}\\\land \;\;&R\circ R^{-1}=\Delta _{B}\end{aligned}}$	Jedes Element aus $A$ hat genau einen Partner in $B$ und umgekehrt.

Eine Relation ist also genau dann eine Funktion, wenn sie linkstotal und rechtseindeutig ist. Die Attribute surjektiv, injektiv und bijektiv werden in der Regel für Funktionen gebraucht. Z. B. ist eine Funktion $R$ (und nach der hiesigen Definition auch eine Relation) genau dann bijektiv, wenn sie surjektiv und injektiv ist, also wenn ihre Umkehrung $R^{-1}$ eine Funktion ist.

Alternative Sprechweisen

• Zu linkstotal sagt man auch linksvollständig.
• Zu rechtstotal sagt man auch rechtsvollständig.
• Zu linkseindeutig sagt man auch voreindeutig.
• Zu rechtseindeutig sagt man auch nacheindeutig.

Relationszeichen

In der elementaren Mathematik gibt es drei grundlegende Vergleichsrelationen:

1. $x<y$ (Beispiel: 2 < 3 "2 ist kleiner als 3")
2. $x=y$ (Beispiel: 3 = 3 "3 ist gleich 3")
3. $x>y$ (Beispiel: 3 > 2 "3 ist größer als 2")

mit $x,y\in \mathbb {R}$.

Zwei reelle Zahlen stehen immer in genau einer dieser Relationen zueinander. Mit diesen Relationszeichen lassen sich auch weitere erschaffen; so gilt:

• $x\leq y$, falls $x<y$ oder $x=y$ (Beispiel: $4\leq 5$)
• $x\geq y$, falls $x>y$ oder $x=y$ (Beispiel: $5\geq 5$)
• $x\neq y$, falls $x<y$ oder $x>y$ (Beispiel: $4\neq 5$)

für alle $x,y\in \mathbb {R}$.

Für komplexe Zahlen existieren obige Ordnungsrelationen nicht.

Mathematiker verwenden das Zeichen ≤ auch für abstrakte Ordnungsrelationen (und ≥ für die zugehörige Umkehrrelation) während "<" keine Ordnungsrelation im Sinne der mathematischen Definition ist.

Für Äquivalenzrelationen werden "symmetrische" Symbole wie ≈ , ~ , ≡ bevorzugt.

Klassen von Relationen

Zusammenhänge zwischen verschiedenen binären Relationen

Wichtige Klassen von Relationen und ihre Eigenschaften:

• Äquivalenzrelation: reflexiv, transitiv und symmetrisch
• Funktion: linkstotal und rechtseindeutig
• Verträglichkeitsrelation oder Toleranzrelation: verträglich (reflexiv und symmetrisch)
• Quasiordnung oder Präordnung: reflexiv und transitiv
• Halbordnung oder partielle Ordnung: reflexiv, transitiv und antisymmetrisch.
• Totalordnung oder totale/lineare Ordnung: reflexiv, transitiv, antisymmetrisch und total/linear
• Wohlordnung: eine lineare Ordnung, bei der jede nichtleere Teilmenge von A ein kleinstes Element besitzt
• Striktordnung oder strenge Halbordnung: transitiv und asymmetrisch (d.h. irreflexiv und antisymmetrisch)

Kategorientheorie

Für einen beliebigen Halbring $(H,+,\cdot )$ mit Nullelement $0$ und Einselement $1$ ist folgendes ${\mathcal {C}}$ eine Kategorie:

• $\mathrm {Ob} ({\mathcal {C}})=\mathrm {Ob} (\mathbf {Set} )$,
• ein Morphismus $f\in \mathrm {Hom} _{\mathcal {C}}(X,Y)$ ist eine Funktion $f\colon X\times Y\to H$,
• Für Objekte $X$ ist $\mathrm {id} _{X}(x,x'):={\begin{cases}1&x=x'\\0&{\text{sonst,}}\end{cases}}$
• für Objekte $X,Y,Z$ und Morphismen $f\in \mathrm {Hom} _{\mathcal {C}}(Y,Z),g\in \mathrm {Hom} _{\mathcal {C}}(X,Y)$ ist

  $(f\circ g)(x,z):=\sum _{y\in Y}g(x,y)\cdot f(y,z)$.

Die Morphismen sind also mengenindizierte Matrizen, und ihre Komposition geschieht wie bei der Matrixmultiplikation.

Im Sonderfall $(H,+,\cdot )$ $=(\{0,1\},\lor ,\land )$ ist ${\mathcal {C}}=\mathbf {Rel}$, d.h. die Kategorie der Relationen.

Anwendung

Operationen auf ganzen Relationen werden in der relationalen Algebra untersucht. In der Informatik sind Relationen bei der Arbeit mit relationalen Datenbanken wichtig.

Siehe auch

• Prädikat (Logik)

Literatur

• Ingmar Lehmann, Wolfgang Schulz: Mengen – Relationen – Funktionen. Eine anschauliche Einführung. 3., überarbeitete und erweiterte Auflage. Vieweg & Teubner, Wiesbaden 2007, ISBN 978-3-8351-0162-3. 
• Gunther Schmidt, Thomas Ströhlein: Relationen und Graphen. Springer, Berlin et al. 1989, ISBN 3-540-50304-8. 
• F. Reinhardt, H. Soeder: dtv-Atlas Mathematik. 11. Auflage. Band 1: Grundlagen, Algebra und Geometrie. Deutscher Taschenbuchverlag, München 1998, ISBN 3-423-03007-0. 

Weblinks

Wikibooks: Mathe für Nicht-Freaks: Relation – Lern- und Lehrmaterialien

• Literatur über Relation im Katalog der Deutschen Nationalbibliothek