Relation (Mathematik)

Eine Relation (lateinisch relatio „Beziehung“, „Verhältnis“) 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 ein 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 Elementen $a$ und $b$; diese bilden dann ein geordnetes Paar $(a,b).$ Stammen dabei $a$ und $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$), dann heißt die Relation homogen oder „Relation in bzw. auf der Menge $A$.“

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

Heute sehen manche Autoren den Begriff Relation nicht unbedingt als auf Mengen beschränkt an, sondern lassen jede aus geordneten Paaren bestehende Klasse als Relation gelten.

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 (seltener Graf) $G_{R}$ der Relation genannt. Eine zweistellige Relation $R$ ist dann definiert als Tripel

$R=(G_{R},A,B)$ mit $G_{R}\equiv \operatorname {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.

Als Urbild-, Argument- oder Definitionsbereich einer gegebenen zweistelligen Relation $R$ wird der kleinstmögliche Vorbereich zum Graphen $G_{R}$ verstanden, dessen Elemente alle in den geordneten Paaren von $R$ tatsächlich auf der linken Seite auftreten, in Zeichen

$Db(R)\equiv {\mathfrak {D}}(R):=\{a|\exists b:(a,b)\in G_{R}\}\subseteq A$.

Der Wertevorrrat, Werte- oder Bildbereich bezeichnet in diesem Sinne den kleinsten Nachbereich zu $G_{R}$ bei gegebenem $R$, dessen Elemente also alle in den Paaren von $R$ auf der rechten Seite auftreten, in Zeichen

$Wb(R)\equiv {\mathfrak {B}}(R):=\{b|\exists a:(a,b)\in G_{R}\}\subseteq B$.

Gelegentlich wird für die Vereinigungsmenge die Bezeichnung Feld benutzt, in Zeichen

$Fd(R)\equiv {\mathfrak {F}}(R):=Db(R)\cup Wb(R)=\{x|\exists x':(x,x')\in G_{R}\lor (x',x)\in R\}\subseteq A\cup B$.

Stimmen zwei Relationen in ihren Graphen überein, so sagt man auch, sie seien im Wesentlichen gleich. Beispiel: Jede Relation $R=(G_{R},A,B)$ ist im Wesentlichen gleich mit $(G_{R},Db(R),Wb(R))$ und mit $(G_{R},Fd(R),Fd(R))$.

Mehrstellige Relation

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

$R\subseteq A_{1}\times \dotsb \times A_{n}$ mit $A_{1}\times \dotsb \times A_{n}=\{(a_{1},\dotsc ,a_{n})\mid a_{1}\in A_{1},\dotsc ,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},\dotsc ,A_{n})$ mit $G_{R}\equiv \operatorname {Graph} (R)\subseteq A_{1}\times \dotsb \times A_{n}.$

Die Mengen $A_{1},\dotsc A_{i}\dotsc A_{n}$ heißen Trägermengen der Relation mit den minimalen Trägermengen zum Graphe $G_{R}$, nämlich

$Tr_{i}(R)\equiv {\mathfrak {T}}_{i}(R):=\{a_{i}|\exists a_{1},\dotsc {a}_{i-1},a_{i+1}\dotsc {a}_{n}:\ (a_{1},\dotsc {a}_{i-1},a_{i},a_{i+1}\dotsc {a}_{n}\in G_{R}\}$.

Das Feld einer mehrstelligen Relation ist gegeben durch

$Fd(R)\equiv {\mathfrak {F}}(R):=\bigcup \{A_{i}|1\leq i\leq n\}$.

Wesentliche Gleichheit ist analog definiert wie für zweistellige Relationen durch Übereinstimmung der Graphen, insbesondere ist jede n-stellige Relation $R=(G_{R},A_{1},\dotsc ,A_{n})$ im Wesentlichen gleich mit $(G_{R},Tr_{1}(R),\dotsc Tr_{n}(R))$.

Relationen zwischen oder auf echten Klassen

Häufig sind die Trägerbereiche $A_{i}$ einer Relation keine Mengen, sondern echte Klassen. Gelegentlich kann man mengentheoretische Probleme, die sich daraus ergeben, vermeiden, indem man nur noch den Graph der entsprechenden Relation betrachtet. Die (minimalen) Trägermengen ($Tr_{i}(R)$, im zweistelligen Fall Definitions- und Wertemenge $Db(R),Wb(R)$) sind tatsächlich Mengen, aber es ist nicht nötig, sich von vornherein auf Quellmenge, Zielmenge,… ($A,B,A_{i}...$) festzulegen, wenn die Relationen im Wesentlichen gleich sind. Nicht immer ist das möglich, beispielsweise für die Äquivalenzrelation der Gleichmächtigkeit, siehe auch: Kardinalzahlen §Definition. Gleichheit von Relationen im Wesentlichen ist ein weiteres Beispiel.

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 (wie in $a>b$).

Relationen und Funktionen

• Eine Funktion $f:A\to B$ ist eine spezielle, nämlich eine linkstotale und rechtseindeutige (zweistellige) Relation, näheres siehe unten.
• Eine Multifunktion $f:X\multimap Y$ ist eine linkstotale Relation$f\subseteq A\times B$.
• Eine partielle Funktion $f\colon X\not \to Y$ ist eine (im Allgemeinen nicht linkstotale) rechtseindeutige Relation$f\subseteq A\times B$.

In allen Fällen ist $f\subseteq A\times B$ (beziehungsweise $G_{f}\subseteq A\times B$ wenn die ausführliche Definition zugrundegelegt wird).

Für Funktionen und Multifunktionen gilt:
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.

Für Funktionen und partielle Funktionen gilt:
Für $(a,b)\in f$ bzw. $(a,b)\in G_{f}$ wird auch $f\colon a\mapsto b$ (englisch: maplet), oder $f(a)=b$ geschrieben.

Allgemein gilt:

1. Eine Relation $R\subseteq A\times B$ entspricht auf eindeutige Weise einer Funktion $\chi _{R}\colon A\times B\to \{{\mathsf {wahr}},{\mathsf {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 $\{{\mathsf {wahr}},{\mathsf {falsch}}\}$ durch $\{1,0\}$ ersetzt werden kann.
2. Eine Relation $R\subseteq A\times B$ lässt sich ebenso als eine Abbildung $\kappa _{R}$ von $A$ in die Potenzmenge von $B$ auffassen, $\kappa _{R}\colon A\to {\mathcal {P}}(B),\ a\mapsto \{b\in B\mid (a,b)\in R\},$ man spricht dann oft von einer Korrespondenz, und für $B=A$ von einer Transitionsrelation.

Verkettung von Relationen

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

Dabei kann auch die einfachste Relation, die in jedem kartesischen Produkt enthaltene leere Relation $\emptyset$ (leere Menge) auftreten, nämlich wenn $B$ und $C$ disjunkt sind, in Zeichen: $B\cap C=\emptyset$.

Manche Autoren verwenden für die Verkettung von Relationen alternativ die Notation $R|S$.

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“.

Umkehrrelation

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

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

Gelegentlich findet sich hierfür auch die Bezeichnung transponierte Relation, in Zeichen $R^{T}$. 

• Beispiel 1: Die Umkehrrelation der Relation „ist Nachkomme von“ ist die Relation „ist Vorfahre von“.
• Beispiel 2: Die Umkehrrelation der Relation „ist kleiner als“ ist die Relation „ist größer als“.
• Beispiel 3: Die Umkehrrelation der Relation „liefert an“ ist die Relation „wird beliefert von“.

Die Verallgemeinerung der Umkehrrelation (Konverse) auf n-stellige Relationen ist die Permutation der Koordinaten der in ihr enthaltenen n-Tupel, speziell

• die Vertauschungen von lediglich 2 Koordinaten (Transpositionen) und
• die Umkehrung der Reihenfolge (Spiegelung),

beides Beispiele (zyklischer) selbstinverser Permutationen.
Sei $\pi \colon \{1,2,\ldots ,n\}\rightarrow \{1,2,\ldots ,n\}$ eine Permutation (d. h. bijektive Abbildung von $\{1,\ldots ,n\}$ auf sich selbst), und sei $R\subseteq (A_{i})_{i\in \{1,\ldots ,n\}}$ eine n-stellige Relation, dann ist $S:=\{a\circ \pi |a\in R\}$ die sich nach Anwendung der Permutation $\pi$ sich ergebende Relation (man verstehe $a=(a_{i})_{i\in \{1,\ldots ,n\}}$ als Familie). Im Fall der Spiegelung

$\pi =\sigma _{n}={\begin{pmatrix}1&2&\cdots &n\\n&n-1&\cdots &1\end{pmatrix}}$,

ist $S=\{(a_{n},\dots a_{1})|(a_{1},\dots a_{n})\in R\}$.

Bild und Urbild

Bei einer zweistelligen Relation $R\subseteq A\times B$ bezeichnet man als das Bild einer Menge $X$ die Menge

$R\langle X\rangle :=\{y|\exists x\in X:(x,y)\in R\}=\{(x,y)\in R|x\in X\}$,

Das Urbild einer Menge $Y$ ist die Menge

$R^{-1}\langle Y\rangle \equiv {\overset {\smile }{R}}\langle Y\rangle \equiv {\;}^{^{\smile }}{R}\langle Y\rangle =\{x|\exists y\in Y:(x,y)\in R\}=\{(x,y)\in R|y\in Y\}$.

Gelegentlich findet sich hierfür auch die Bezeichnung $R{\grave {}}{\grave {}}Y$

Einschränkung

Relationen lassen sich auf verschiedene Art und Weise auf Teilmengen der Trägermengen einschränken, näheres siehe Einschränkung §Einschränkung einer Relation.

Komplementäre Relation

Für zweistellige Relationen $R\subseteq A\times B$ bei festem Vor- und Nachbereich $A,B$ ist die komplementäre Relation gegeben durch

${\overline {R}}\equiv \;^{^{\overline {}}}{R}=(A\times B)\setminus R=\{(x,y)\in A\times B|(x,y)\not \in R\}$, 

analog für n-stellige Relationen $R\subseteq A_{1}\times \dots \times A_{n}$ bei festen Trägerbereichen $A=(A_{1},\dots A_{n})$. Auf den Reellen Zahlen $\mathbb {R}$ ist beispielsweise $\leq$ die komplementäre Relation zu $>$.

Wird die komplexe Notation $R=(G_{R},A,B)$ zugrunde gelegt, so ist

${\overline {R}}\equiv \;^{^{\overline {}}}{R}=((A\times B)\setminus G_{R},A,B)$,

wobei $A,B$ jetzt keine äußeren Zugaben mehr sind, sondern Bestandteile der Relation; analog für n-stellige Relationen in dieser Notation.

Wie für alle Mengen ist das Komplement auch für Relationen involutiv:

${\overline {\overline {R}}}=R$.

Homogene Relationen

Ist $A=B,$ also $R\subseteq A\times A,$ dann nennt man die Relation homogen. 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).$

Eine spezielle homogene Relation in einer Menge $A$ ist die Gleichheits- oder Identitätsrelation

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

Wenn $A$ bereits bekannt ist, wird sie einfach mit $\mathrm {I}$ bezeichnet, man nennt sie auch die Diagonale $\Delta$ oder $\mathrm {D} .$

Die Bildung der Umkehrrelation (konversen Relation) einer homogenen binären Relation liefert wieder eine homogene binäre Relation (Abgeschlossenheit), zweimalige Ausführung ergibt wieder die Ausgangsrelation (Involutivität). Die Verknüpfung einer beliebigen (auch nicht-homogenen) Relation mit der dazu konversen Relation ist symmetrisch und reflexiv, also eine Äquivalenzrelation, aber im Allgemeinen nicht gleich der Identitätsrelation.

In Erweiterung der Notation $R^{-1}$ anstelle von ${\overset {\smile }{R}}$  für die Umkehrrelation bezeichnet man deren Potenzen mit negativen Exponenten:

$R^{-n}:={\overset {\smile }{R}}^{n}={\overset {\smile }{R^{n}}}$  

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 $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 $G$ genau dann (stark) zusammenhängend, wenn die reflexiv-transitive Hülle von $K$ die Universalrelation ist.

Im Fall einer homogenen Relation $R\subseteq A\times A$ ist die Verkettung $R\circ R$ ebenfalls eine homogene Relation, sodass die homogenen Relationen in $A$ ein Monoid mit der multiplikativen Verknüpfung $\circ$ und dem neutralen Element $\mathrm {I} _{A}$ bilden. Somit kann $R^{2}:=R\circ R$ und können allgemeiner Potenzen $R^{n}:=R\circ R^{n-1}$ für $n\in \mathbb {N}$ definiert werden, wobei $R^{0}:=\mathrm {I} _{A}$ ist.
$\mathrm {I} _{A}$ wird daher auch Einsrelation auf der Menge $A$ genannt.

Zudem besitzt jedes Monoid homogener Relationen mit der leeren Relation noch ein absorbierendes Element, sodass diese ebenso als Nullrelation

$\mathrm {O} :=\emptyset$

bezeichnet wird.

Durch Vereinigung der verschiedenen Potenzen entstehen die Relationen

$R^{*}:=\bigcup _{n\in {\mathbb {N} _{0}}}R^{n}$ und $R^{+}:=\bigcup _{n\in {\mathbb {N} }}^{\infty }R^{n}$.

Alles zusammengefasst, bilden die zweistelligen Relationen auf einer Menge $A$ eine Relationsalgebra

${\mathfrak {Re}}(A)=(2^{A^{2}},\cap ,\cup ,{}^{^{-}},\mathrm {O} ,A^{2},\circ ,\mathrm {I} _{A},{}^{\smile })$

unter Verwendung der Notationen $A^{2}=A\times A,\ \;\ 2^{A^{2}}={\mathcal {P}}(A\times A)$.

Zusammen mit den Beschränkungen bilden die homogenen Relationen eine (heterogene) Peirce-Algebra.

Homogene mehrstellige Relationen sind (mit ihrem Graphen) Teilmengen von $A^{n}$. Die als Verallgemeinerung der Konversenbildung beschriebene Anwendung von Permutationen auf ihre n-Tupel sind hier von besonderer Bedeutung, da man auf diese Weise immer innerhalb der Teilmengen von $A^{n}$ bleibt (Abgeschlossenheit). M. a. W. sind diese Operationen bijektive Abbildungen in ${\mathcal {P}}(A^{n})=2^{A^{n}}$.

Beispiele

• 
  Alle möglichen geordneten Paare $(u,v)$ mit $u\in A:=\{a,b,c\}$ und $v\in B:=\{x,y,z\}$ sowie eine zwischen $A$ und $B$ definierte Relation $R.$
• 
  Beispiel einer Relation „Eine Person x studiert das Fach y“.
• 
  Beispiel einer Relation „Person x liebt Person y“. Diese zweistellige Relation wird über eine Menge von geordneten Paaren modelliert.
• 
  Die einstellige Relation „Person x ist weiblich“ wird als Teilmenge der Grundmenge modelliert.
• 
  Die dreistellige Relation „Person x lernt das Fach y beim Lehrer z“ wird über eine Menge von 3-Tupeln realisiert.

Eigenschaften zweistelliger Relationen

Allgemeine Relationen

Übersicht über die Eigenschaften

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 $R$ heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
linkstotal bzw. definal (Multifunktion)	$\forall a\in A\;\exists b\in {B}\colon \;(a,b)\in R$	$\mathrm {I} _{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$	$\mathrm {I} _{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)\in R\,\land \,(c,b)\in R\;\Rightarrow \;a=c\end{aligned}}$	$R^{-1}\circ R\subseteq \mathrm {I} _{A}$	Jedes Element aus $B$ hat höchstens einen Partner in $A.$
(rechts-) eindeutig (partielle Funktion)	${\begin{aligned}&\forall a\in A\;\forall b,d\in B\colon \\&(a,b)\in R\,\land \,(a,d)\in R\;\Rightarrow \;b=d\end{aligned}}$	$R\circ R^{-1}\subseteq \mathrm {I} _{B}$	Jedes Element aus $A$ hat höchstens einen Partner in $B.$

Die Relation $R$ heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
bitotal	${\begin{aligned}&(\forall a\in A\;\exists b\in B\ \colon (a,b)\in R)\\\land \;&(\forall b\in B\;\exists a\in A\ \colon (a,b)\in R)\end{aligned}}$	${\begin{aligned}&\mathrm {I} _{A}\subseteq R^{-1}\circ R\\\land \;&\mathrm {I} _{B}\subseteq R\circ R^{-1}\end{aligned}}$	Jedes Element aus $A$ hat mindestens einen Partner in $B$ und umgekehrt.
eineindeutig	${\begin{aligned}&\forall b,d\in B\;\forall a,c\in A\colon \\&(a,b)\in R\,\land \,(c,b)\in R\;\Rightarrow \;a=c,\\&(a,b)\in R\,\land \,(a,d)\in R\;\Rightarrow \;b=d\end{aligned}}$	${\begin{aligned}&R^{-1}\circ R\subseteq \mathrm {I} _{A}\\\land \;&R\circ R^{-1}\subseteq \mathrm {I} _{B}\end{aligned}}$	Jedes Element aus $B$ hat höchstens einen Partner in $A$ und umgekehrt.
bijektiv	$\forall b\in B\;\exists !a\in A\colon \;(a,b)\in R$	${\begin{aligned}&\mathrm {I} _{B}\subseteq R\circ R^{-1}\\\land \;&R^{-1}\circ R\subseteq \mathrm {I} _{A}\end{aligned}}$	Jedes Element aus $B$ hat genau einen Partner in $A.$
Abbildung bzw. Funktion	$\forall a\in A\;\exists !b\in B\colon \;(a,b)\in R$	${\begin{aligned}&\mathrm {I} _{A}\subseteq R^{-1}\circ R\\\land \;&R\circ R^{-1}\subseteq \mathrm {I} _{B}\end{aligned}}$	Jedes Element aus $A$ hat genau einen Partner in $B.$

Alternative Sprechweisen

Man sagt auch

• linksvollständig an Stelle von linkstotal,
• rechtsvollständig an Stelle von rechtstotal,
• voreindeutig an Stelle von linkseindeutig,
• nacheindeutig an Stelle von rechtseindeutig,

Eine rechtseindeutige bzw. funktionale Relation nennt man auch partielle Funktion. Wenn diese auch linkstotal – also eine Funktion – ist, dann sagt man zur Verdeutlichung auch totale Funktion.

Funktionen

Übersicht über Funktionseigenschaften bei Relationen

Eine Relation ist also genau dann eine (totale) Funktion, wenn sie linkstotal und rechtseindeutig ist. Das heißt, dass jedes Element in A genau einen Partner in B hat. Die Eigenschaften surjektiv, injektiv und bijektiv werden in der Regel für Funktionen gebraucht und spezifizieren bestimmte zusätzliche Eigenschaften. Z. B. ist eine Funktion (und auch eine beliebige Relation) $R$ genau dann bijektiv, wenn sie surjektiv und injektiv ist, also wenn ihre Umkehrrelation $R^{-1}$ eine Funktion ist.

Die Relation $R$ heißt	genau dann, wenn sie eine	ist oder gleichwertig (Mengenschreibweise)	und das bedeutet:
Surjektion	surjektive Funktion	${\begin{aligned}&\mathrm {I} _{A}\subseteq R^{-1}\circ R\\\land \;&R\circ R^{-1}=\mathrm {I} _{B}\end{aligned}}$	Jedes Element aus $A$ hat genau einen Partner in $B$ und jedes Element aus $B$ hat mindestens einen Partner in $A.$
Injektion	injektive Funktion	${\begin{aligned}&\mathrm {I} _{A}=R^{-1}\circ R\\\land \;&R\circ R^{-1}\subseteq \mathrm {I} _{B}\end{aligned}}$	Jedes Element aus $A$ hat genau einen Partner in $B$ und jedes Element aus $B$ hat höchstens einen Partner in $A.$
Bijektion	bijektive Funktion	${\begin{aligned}&\mathrm {I} _{A}=R^{-1}\circ R\\\land \;&R\circ R^{-1}=\mathrm {I} _{B}\end{aligned}}$	Jedes Element aus $A$ hat genau einen Partner in $B$ und umgekehrt.

Umkehrfunktion

Eine Abbildung bzw. Funktion nennt man auch

• umkehrbar eindeutig oder umkehrbar, falls sie bijektiv ist.

Eine Funktion ist als Relation immer umkehrbar, als Funktion ist sie dagegen genau dann umkehrbar, wenn ihre Umkehrrelation auch wieder eine Funktion ist, also wenn es eine Umkehrfunktion von ihr gibt.

Homogene Relationen

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

Die Relation $R$ heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
rechtskomparativ bzw. drittengleich	${\begin{aligned}&\forall a,b,c\in A\colon \\&(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 gleichen dritten Element in Relation, dann stehen auch sie zueinander in Relation. Z. B. gilt mit a = c und b = c stets a = b.
linkskomparativ bzw. euklidisch	${\begin{aligned}&\forall a,b,c\in A\colon \\&(a,b)\in R\,\land \,(a,c)\in R\\&\Rightarrow \;(b,c)\in R\end{aligned}}$	$R\circ R^{-1}\subseteq R$	Steht ein erstes Element jeweils zu einem zweiten und zu einem dritten Element in Relation, so stehen auch diese zueinander in Relation. Z. B. gilt mit a = b und a = c stets ebenso b = c.
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$	Steht ein erstes Element zu einem zweiten Element und dieses wiederum zu einem dritten Element in Relation, so steht auch das erste Element zum dritten Element in Relation. Z. B. folgt aus a < b und b < c stets a < c.
intransitiv	${\begin{aligned}&\forall a,b,c\in A\colon \\&(a,b)\in R\,\land \,(b,c)\in R\\&\Rightarrow \;(a,c)\notin R\\\end{aligned}}$	$(R\circ R)\cap R=\emptyset$	Stehen zwei Elemente in Relation und zudem das zweite Element zu einem dritten Element in Relation, dann steht das erste Element zum dritten Element nicht in Relation. Z. B. ist jede natürliche Zahl n die (unmittelbare) Vorgängerin von n + 1 und n + 1 die (unmittelbare) Vorgängerin von n + 2, aber n ist nicht (unmittelbare) Vorgängerin von n + 2.

Nichttransitivität (d. h. die Relation ist nicht transitiv), Intransitivität und negative Transitivität sind jeweils voneinander verschieden.

Die Relation $R$ heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
reflexiv	$\forall a\in A\colon \;(a,a)\in R$	$\mathrm {I} \subseteq R$	Jedes Element steht in Relation zu sich selbst, z. B. ist stets a ≤ a.
		$\mathrm {I} \cap R=\mathrm {I}$
irreflexiv	$\forall a\in A\colon \;(a,a)\notin R$	$\mathrm {I} \cap R=\emptyset$	Kein Element steht in Relation zu sich selbst, z. B. gilt a < a für kein a.

Die Relation $R$ heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
symmetrisch	${\begin{aligned}&\forall a,b\in A\colon \\&(a,b)\in R\;\Rightarrow \;(b,a)\in R\end{aligned}}$	$R^{-1}\subseteq R$	Die Relation ist ungerichtet, z. B. folgt aus a = b stets b = a (und umgekehrt)
		$R^{-1}=R$
antisymmetrisch bzw. identitiv	${\begin{aligned}&\forall a,b\in A\colon \\&(a,b)\in R\,\land \,(b,a)\in R\\&\Rightarrow \;a=b\end{aligned}}$	$R^{-1}\cap R\subseteq \mathrm {I}$	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.
asymmetrisch	${\begin{aligned}&\forall a,b\in A\colon \\&(a,b)\in R\;\Rightarrow \;(b,a)\notin R\end{aligned}}$	$R^{-1}\cap R=\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.

Die Relation $R$ heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
total bzw. vollständig	${\begin{aligned}&\forall a,b\in A\colon \\&(a,b)\in R\,\lor \,(b,a)\in R\end{aligned}}$	$R^{-1}\cup R=A\times A$	Je zwei Elemente stehen in Relation, z. B. wenn stets a ≤ b oder b ≤ a gilt.
konnex bzw. verbunden	${\begin{aligned}&\forall a,b\in A\colon \\&a\neq b\\&\Rightarrow \;(a,b)\in R\,\lor \,(b,a)\in R\end{aligned}}$	$R^{-1}\cup R\cup \mathrm {I} =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.
trichotom	${\begin{aligned}&\forall a,b\in A\colon \\&((a,b)\in R\Rightarrow (b,a)\notin R)\,\land \\&(a\neq b\\&\Rightarrow \;(a,b)\in R\,\lor \,(b,a)\in R)\end{aligned}}$	${\begin{aligned}R^{-1}\cup R\cup \mathrm {I} &=A\times A\\\land \;R^{-1}\cap R&=\emptyset \end{aligned}}$	Je zwei verschiedene Elemente stehen stets auf genau eine Weise in Relation, z. B. wenn stets entweder a < b oder b < a gilt.

Zwischen den Eigenschaften gelten folgende Zusammenhänge:

Zusammenhang der Eigenschaften binärer Relationen

Zwischen den Eigenschaften einer Relation $R$ und denen ihres Komplements ${\overline {R}}$ bestehen folgende Zusammenhänge:

• $R$ ist symmetrisch $\iff$ ${\overline {R}}$ ist symmetrisch
• $R$ ist reflexiv $\iff$ ${\overline {R}}$ ist irreflexiv   (und umgekehrt)
• $R$ ist antisymmetrisch $\iff$ ${\overline {R}}$   (und umgekehrt)
• $R$ ist total $\iff$ ${\overline {R}}$ ist asymmetrisch   (und umgekehrt) 

Klassen von Relationen

Zusammenhänge zwischen verschiedenen zweistelligen Relationen

Weitere wichtige Klassen von Relationen und ihre Eigenschaften:

• Quasiordnung oder Präordnung: transitiv und reflexiv
• Äquivalenzrelation: transitiv, reflexiv und symmetrisch
• Halbordnung/Teilordnung, partielle Ordnung oder Ordnung: transitiv, reflexiv und antisymmetrisch.
• Vollordnung/Totalordnung oder lineare Ordnung: transitiv, reflexiv, antisymmetrisch und total
• Wohlordnung: eine lineare Ordnung, in der jede nichtleere Teilmenge von A ein kleinstes Element besitzt
• Striktordnung oder strenge Halbordnung/Teilordnung: transitiv, irreflexiv und antisymmetrisch (d. h. asymmetrisch)
• Strenge Vollordnung/Totalordnung oder lineare Striktordnung: transitiv, irreflexiv, antisymmetrisch und konnex.

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 bilden. Es gilt:

• $x\leq y$, falls $x<y$ oder $x=y$ (Beispiel: $4\leq 5,$ „4 ist nicht größer als 5“)
• $x\geq y$, falls $x>y$ oder $x=y$ (Beispiel: $5\geq 5,$ „5 ist nicht kleiner als 5“)
• $x\neq y$, falls $x<y$ oder $x>y$ (Beispiel: $4\neq 5,$ „4 ist nicht gleich 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.

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$ gilt

  $\mathrm {id} _{X}(x,x'):={\begin{cases}1&x=x'\\0&{\text{sonst}}\end{cases}}$.

Das ist identisch mit dem Kronecker-Delta: $\mathrm {id} _{X}(x,x')=\delta _{xx'}$.

• Für Objekte $X,Y,Z$ und Morphismen $f\in \mathrm {Hom} _{\mathcal {C}}(Y,Z),\ g\in \mathrm {Hom} _{\mathcal {C}}(X,Y)$ gilt

  $(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, $\mathrm {id} _{x}$ entspricht der Einheitsmatrix $E$.

Im Sonderfall $(H,+,\cdot )=(\{0,1\},\lor ,\land )$ gilt ${\mathcal {C}}=\mathbf {Rel}$, d. h., ${\mathcal {C}}$ ist 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

• Garrett Birkhoff: Lattice Theory. 3rd Edition. AMS, Providence, RI 1973, ISBN 0-8218-1025-1. 
• Marcel Erné: Einführung in die Ordnungstheorie. Bibliographisches Institut, Mannheim 1982, ISBN 3-411-01638-8. 
• Helmuth Gericke: Theorie der Verbände. Bibliographisches Institut, Mannheim 1963. 
• 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. 
• Fritz Reinhardt, Heinrich Soeder: dtv-Atlas Mathematik. 11. Auflage. Band 1: Grundlagen, Algebra und Geometrie. Deutscher Taschenbuchverlag, München 1998, ISBN 3-423-03007-0, S. 30–33, 42–45. 
• Gunther Schmidt, Thomas Ströhlein: Relationen und Graphen. Springer, Berlin u. a. 1989, ISBN 3-540-50304-8. 
• Robert Wall: Einführung in die Logik und Mathematik für Linguisten. Übersetzt von W. Klein, A. Kratzer, A. v. Stechow. Band 1: Logik und Mengenlehre. Scriptor, Kronberg/Ts. 1974, ISBN 3-589-00023-6. 
• Dieter Klaua: Mengenlehre. De-Gruyter-Lehrbuch. de Gruyter, Berlin, New York 1979, ISBN 3-11-007726-4.  DerAutor benutzt die Bezeichnung Korrespondenz im mengentheoretischen Sinn synonym zu Relation, verwendet dann aber das Zeichen $F$ anstelle von $R$. Im Artikel hier ist jedoch durchgängig $R$ bzw. $G_{R}$ (Graph von $R$) benutzt.
• H. König: Entwurf und Strukturtheorie von Steuerungen für Fertigungseinrichtungen (= ISW Forschung und Praxis. Band 13). Springer-Verlag, Berlin / Heidelberg 1976, ISBN 3-540-07669-7, S. 15–17, doi:10.1007/978-3-642-81027-5_1. 
• Willard van Orman Quine: Set Theory And Its Logic (anglisch). Belknap Press of Harvard University Press, Cambridge, USA 1963, ISBN 0-674-80207-1, S. 359 (HC)/ 380 (PB).  (englisch);
  Willard van Orman Quine: Mengenlehre und ihre Logik (= Logik und Grundlagen der Mathematik (deutsche Übersetzung). Band 10). Vieweg+Teubner Verlag, 1973, ISBN 3-528-08294-1, S. 264.  Die Seitenangaben beziehen sich auf die deutsche Übersetzung.

Weblinks

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

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

• Literatur über Relation im Katalog der Deutschen Nationalbibliothek
• Video: Idee der zweistelligen Relationen. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19788.