Ytukyg

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; Objekte 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{displaystyle R} ist eine Menge von n{displaystyle n}-Tupeln. In der Relation R{displaystyle R} zueinander stehende Dinge bilden n{displaystyle n}-Tupel, die Element von R{displaystyle R} sind.

Wird nicht ausdrücklich etwas anderes angegeben, versteht man unter einer Relation gemeinhin eine zweistellige oder binäre Relation. Bei einer solchen Beziehung bilden dann jeweils zwei Elemente a{displaystyle a} und b{displaystyle b} ein geordnetes Paar (a,b).{displaystyle (a,b).} Stammen dabei a{displaystyle a} und b{displaystyle b} aus verschiedenen Grundmengen A{displaystyle A} und B{displaystyle B}, so heißt die Relation heterogen oder „Relation zwischen den Mengen A{displaystyle A} und B{displaystyle B}.“ Stimmen die Grundmengen überein (A=B{displaystyle A=B}), dann heißt die Relation homogen oder „Relation in bzw. auf der Menge A{displaystyle 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{displaystyle R} (auch binäre Relation genannt)^[1] zwischen zwei Mengen A{displaystyle A} und B{displaystyle B} ist eine Teilmenge des kartesischen Produkts A×B={(a,b)∣a∈A,b∈B}:{displaystyle Atimes B={(a,b)mid ain A,bin B}colon }

R⊆A×B{displaystyle Rsubseteq Atimes B}.

Die Menge A{displaystyle A} wird als Quellmenge (englisch: set of departure) der Relation R{displaystyle R} bezeichnet, die Menge B{displaystyle B} als Zielmenge (englisch: set of destination).^[2]

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

R=(GR,A,B){displaystyle R=(G_{R},A,B)} mit GR≡Graph⁡(R)⊆A×B{displaystyle G_{R}equiv operatorname {Graph} (R)subseteq Atimes 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 Definitions- oder Vorbereich^[3][4][5][6] einer gegebenen zweistelligen Relation R{displaystyle R} wird der kleinstmögliche Vorbereich zum Graphen GR{displaystyle G_{R}} verstanden, dessen Elemente alle in den geordneten Paaren von R{displaystyle R} tatsächlich auf der linken Seite auftreten, in Zeichen

Db(R)≡D(R):={a∣∃b:(a,b)∈GR}⊆A{displaystyle Db(R)equiv {mathfrak {D}}(R):={amid exists bcolon (a,b)in G_{R}}subseteq A}.^[7][8][9]

Der Wertevorrat, Werte- oder Bild- oder Nachbereich^[3][4][5][6] bezeichnet in diesem Sinne den kleinsten Nachbereich zu GR{displaystyle G_{R}} bei gegebenem R{displaystyle R}, dessen Elemente also alle in den Paaren von R{displaystyle R} auf der rechten Seite auftreten, in Zeichen

Wb(R)≡B(R):={b∣∃a:(a,b)∈GR}⊆B{displaystyle Wb(R)equiv {mathfrak {B}}(R):={bmid exists acolon (a,b)in G_{R}}subseteq B}.^[10][8][11]

Gelegentlich wird für die Vereinigungsmenge die Bezeichnung Feld (oder Knotenmenge) benutzt, in Zeichen

Fd(R)≡F(R):=Db(R)∪Wb(R)={x∣∃x′:(x,x′)∈GR∨(x′,x)∈R}⊆A∪B{displaystyle Fd(R)equiv {mathfrak {F}}(R):=Db(R)cup Wb(R)={xmid exists x'colon (x,x')in G_{R}lor (x',x)in R}subseteq Acup B}.^[12][8]

Darüber hinaus finden sich folgende Bezeichnungen:

• 
  Domäne (englisch domain) dom⁡R{displaystyle operatorname {dom} R} entweder für die (im Prinzip beliebig große) Quellmenge oder für die (durch den Graphen festgelegte) Urbildmenge (Definitionsbereich),


• 
  Co-Domäne (englisch codomain, range) cod⁡R,ran⁡R{displaystyle operatorname {cod} R,operatorname {ran} R} entweder für die Zielmenge oder für die Bildmenge,^[13]
  


• 
  Knotenmenge (ver⁡R{displaystyle operatorname {ver} R}) für das Feld^[1] einer Relation.

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

n-stellige Relation |

Allgemeiner ist eine n{displaystyle n}-stellige Relation R{displaystyle R} eine Teilmenge des kartesischen Produkts von n{displaystyle n} Mengen A1,…,An{displaystyle A_{1},dotsc ,A_{n}}

R⊆A1×⋯×An{displaystyle Rsubseteq A_{1}times dotsb times A_{n}} mit A1×⋯×An={(a1,…,an)∣a1∈A1,…,an∈An}=∏A{displaystyle A_{1}times dotsb times A_{n}={(a_{1},dotsc ,a_{n})mid a_{1}in A_{1},dotsc ,a_{n}in A_{n}}=textstyle prod A}.

Dabei bezeichnet A=(Ai)i∈{1,…n}{displaystyle A=(A_{i})_{iin {1,dots n}}} die endliche Folge der Mengen, und ∏A=∏i=1nAi{displaystyle textstyle prod A=textstyle prod _{i=1}^{n}A_{i}} das kartesische Produkt.

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

R=(GR,A1,…,An)=(GR,A){displaystyle R=(G_{R},A_{1},dotsc ,A_{n})=(G_{R},A)} mit GR≡Graph⁡(R)⊆A1×⋯×An=∏A{displaystyle G_{R}equiv operatorname {Graph} (R)subseteq A_{1}times dotsb times A_{n}=textstyle prod A}.

Die Mengen A1,…,Ai,…,An{displaystyle A_{1},dotsc ,A_{i},dotsc ,A_{n}} heißen Trägermengen der Relation mit den minimalen Trägermengen zum Graphen GR{displaystyle G_{R}}, nämlich

Tri(R)≡Ti(R):={ai∣∃a1,…,ai−1,ai+1,…,an:(a1,…,ai−1,ai,ai+1,…,an)∈GR}{displaystyle Tr_{i}(R)equiv {mathfrak {T}}_{i}(R):={a_{i}mid exists a_{1},dotsc ,a_{i-1},a_{i+1},dotsc ,a_{n}colon (a_{1},dotsc ,a_{i-1},a_{i},a_{i+1},dotsc ,a_{n})in G_{R}}}.

Das Feld einer n{displaystyle n}-stelligen Relation ist gegeben durch

Fd(R)≡F(R):=⋃{Ai∣1≤i≤n}=⋃A{displaystyle Fd(R)equiv {mathfrak {F}}(R):=textstyle bigcup {A_{i}mid 1leq ileq n}=textstyle bigcup A}.

Wesentliche Gleichheit ist analog definiert wie für zweistellige Relationen durch Übereinstimmung der Graphen, insbesondere ist jede n{displaystyle n}-stellige Relation R=(GR,A1,…,An){displaystyle R=(G_{R},A_{1},dotsc ,A_{n})} im Wesentlichen gleich mit (GR,Tr1(R),…,Trn(R)){displaystyle (G_{R},Tr_{1}(R),dotsc ,Tr_{n}(R))} und mit der homogenen Relation (GR,Fd(R),…,Fd(R)⏟n-mal){displaystyle (G_{R},underbrace {Fd(R),dotsc ,Fd(R)} _{n{text{-mal}}})}.

Einstellige und nullstellige Relation

Eine einstellige Relation auf einer Menge A{displaystyle A} ist somit einfach eine Teilmenge R⊆A{displaystyle Rsubseteq A}, in der ausführlichen Definition R=(GR,A){displaystyle R=(G_{R},A)} mit GR⊆A{displaystyle G_{R}subseteq A}.

Die nullstelligen Relationen sind demnach die Teilmengen des leeren kartesischen Produkts ∏i=10Ai={∅}{displaystyle textstyle prod _{i=1}^{0}A_{i}={emptyset }} bzw. A0={∅}{displaystyle A^{0}={emptyset }}, also ∅{displaystyle emptyset } und {∅}{displaystyle {emptyset }}, ausführlich (∅,{∅}){displaystyle (emptyset ,{emptyset })} und ({∅},{∅}){displaystyle ({emptyset },{emptyset })}.

Relationen zwischen oder auf echten Klassen |

Häufig sind die Trägerbereiche Ai{displaystyle A_{i}} einer Relation keine Mengen, sondern echte Klassen, man spricht dann von Klassenrelationen. Gelegentlich kann man mengentheoretische Probleme, die sich daraus ergeben, vermeiden, indem man nur noch den Graph der entsprechenden Relation betrachtet. Die (minimalen) Trägermengen (Tri(R){displaystyle Tr_{i}(R)}, im zweistelligen Fall Definitions- und Wertemenge Db(R),Wb(R){displaystyle Db(R),Wb(R)}) sind tatsächlich Mengen, aber es ist nicht nötig, sich von vornherein auf Quellmenge, Zielmenge, … (A,B,Ai,…{displaystyle A,B,A_{i},dotsc }) 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.

Eine zweistellige Klassenrelation R{displaystyle R} mit Quellklasse A{displaystyle A} und Zielklasse B{displaystyle B} heißt vorgängerklein,^[14][15]
wenn für alle b∈B{displaystyle bin B} die Klasse der Vorgänger {a∈A∣aRb}{displaystyle {ain Amid aRb}} (Urbildfaser von b{displaystyle b}, s. u.) eine Menge (d. h. keine echte Klasse) ist.^[16]
Die Relation heißt englisch right-narrow (deutsch in etwa nachfolgerklein),^[17]
wenn für alle a∈A{displaystyle ain A} die Klasse der Nachfolger {b∈B∣aRb}{displaystyle {bin Bmid aRb}} (Bildfaser von a{displaystyle a}) eine Menge ist. Im Fall der Rechtseindeutigkeit (partielle Abbildungen, Abbildungen, s. u.) ist eine Klassenrelation stets klein, da es zu jedem Urbild (genau oder höchstens) einen Bildwert gibt, die Klasse der Nachfolger also eine Einermenge (oder die Leermenge) ist. Jede injektive Klassenabbildung ist beides, klein und vorgängerklein. Die Enthaltenseinsrelation ∈{displaystyle in } ist für jede Klasse B{displaystyle B} vorgängerklein, da die b∈B{displaystyle bin B} keine echten Klassen sein können, sondern Mengen sind und damit {a∈A∣a∈b}⊆b{displaystyle {ain Amid ain b}subseteq b} ebenfalls eine Menge ist.^[18][19] Die Begriffe Vorgänger und Nachfolger selbst werden üblicherweise im Kontext von Ordnungsrelationen verwendet, siehe Ordnungsrelation §Vorgänger und Nachfolger.

Erläuterungen und Schreibweisen |

Das kartesische Produkt zweier Mengen A{displaystyle A} und B{displaystyle B} ist die Menge aller geordneten Paare von a{displaystyle a} und b,{displaystyle b,} wobei a{displaystyle a} irgendein Element aus der Menge A{displaystyle A} und b{displaystyle b} eines aus B{displaystyle B} darstellt. Bei dem geordneten Paar ist die Reihenfolge wichtig, d. h. (a,b){displaystyle (a,b)} unterscheidet sich von (b,a),{displaystyle (b,a),} im Gegensatz zum ungeordneten Paar {a,b},{displaystyle {a,b},} das identisch ist mit {b,a}.{displaystyle {b,a}.} Für (a,b)∈R{displaystyle (a,b)in R} schreibt man auch aRb,{displaystyle a;R;b,}, um zu verdeutlichen, dass jene Beziehung zwischen den Objekten besteht (wie in a>b{displaystyle a>b}).
Die Leermenge als Teilmenge des kartesischen Mengenprodukts als Relation aufgefasst heißt Nullrelation O:=∅={}{displaystyle mathrm {O} :=emptyset ={}},
das volle Produkt heißt Allrelation (auch Universalrelation) U{displaystyle mathrm {U} } (auch als ∇{displaystyle nabla } bezeichnet).^[20]

Relationen und Funktionen |

• Eine Funktion f:A→B{displaystyle fcolon Ato B} ist eine spezielle, nämlich eine linkstotale und rechtseindeutige (zweistellige) Relation, näheres siehe unten.


• Eine Multifunktion f:X⊸Y{displaystyle fcolon Xmultimap Y} ist eine linkstotale Relationf⊆A×B{displaystyle fsubseteq Atimes B}.


• Eine partielle Funktion f:X⇀Y{displaystyle fcolon ;Xrightharpoonup Y} ist eine (im Allgemeinen nicht linkstotale) rechtseindeutige Relationf⊆A×B{displaystyle fsubseteq Atimes B}.

In allen Fällen ist f⊆A×B{displaystyle fsubseteq Atimes B} (beziehungsweise Gf⊆A×B{displaystyle G_{f}subseteq Atimes B} wenn die ausführliche Definition zugrundegelegt wird).

Für Funktionen und Multifunktionen gilt:

Bei der ausführlicheren Definition f=(Gf,A,B){displaystyle f=(G_{f},A,B)} kann, weil A{displaystyle A} durch Gf{displaystyle G_{f}} eindeutig bestimmt ist (linkstotal), auch A{displaystyle A} weggelassen und einfacher f=(Gf,B){displaystyle f=(G_{f},B)} genommen werden.

Für Funktionen und partielle Funktionen gilt:

Für (a,b)∈f{displaystyle (a,b)in f} bzw. (a,b)∈Gf{displaystyle (a,b)in G_{f}} wird auch f:a↦b{displaystyle fcolon amapsto b} (englisch: maplet), oder f(a)=b{displaystyle f(a)=b} geschrieben.

Allgemein gilt:

1. Die nullstelligen Relationen O=∅{displaystyle mathrm {O} =emptyset } (als nullstellige Nullrelation) und U={∅}{displaystyle mathrm {U} ={emptyset }} (als nullstellige Vollrelation) haben als charakteristische Funktionen die booleschen oder logischen Konstanten falsch{displaystyle {mathsf {falsch}}} und wahr{displaystyle {mathsf {wahr}}}, wie immer für Nullrelation und Allrelation.^[21]
   


2. Der Fall einstelliger Relationen ist trivial.


3. Eine Relation R⊆A×B{displaystyle Rsubseteq Atimes B} (bzw. R=(GR,A,B){displaystyle R=(G_{R},A,B)}) entspricht auf eindeutige Weise einer Wahrheitsfunktion χR:A×B→{wahr,falsch}{displaystyle chi _{R}colon ;Atimes Bto {{mathsf {wahr}},{mathsf {falsch}}}}. Diese Funktion ist auch als Indikatorfunktion oder charakteristische Funktion der Teilmenge R⊆A×B{displaystyle Rsubseteq Atimes B} (bzw. GR⊆A×B{displaystyle G_{R}subseteq Atimes B}) bekannt, wobei {wahr,falsch}{displaystyle {{mathsf {wahr}},{mathsf {falsch}}}} durch {1,0}{displaystyle {1,0}} ersetzbar ist.


4. Eine n{displaystyle n}-stellige Relation R⊆A1×⋯×An{displaystyle Rsubseteq A_{1}times dotsb times A_{n}} (bzw. R=(GR,A1,…,An){displaystyle R=(G_{R},A_{1},dotsc ,A_{n})}) entspricht der charakteristischen Funktion χR:A1×⋯×An→{wahr,falsch}.{displaystyle chi _{R}colon A_{1}times dotsb times A_{n}to {{mathsf {wahr}},{mathsf {falsch}}}.}
   

Es gilt:

• 
  n=0:χ∅⇔falsch,χ{∅}⇔wahr{displaystyle n=0colon ;chi _{emptyset }Leftrightarrow {mathsf {falsch}},chi _{{emptyset }}Leftrightarrow {mathsf {wahr}}}.

n=1:χR(a)⇔a∈R{displaystyle n=1colon ;chi _{R}(a)Leftrightarrow ain R}.

n=2:χR(a,b)⇔aRb⇔(a,b)∈R{displaystyle n=2colon ;chi _{R}(a,b)Leftrightarrow aRbLeftrightarrow (a,b)in R}.

n>2:χR(a1,…,an)⇔(a1,…,an)∈R{displaystyle n>2colon ;chi _{R}(a_{1},dotsc ,a_{n})Leftrightarrow (a_{1},dotsc ,a_{n})in R}.^[22]

• Eine Relation R⊆A×B{displaystyle Rsubseteq Atimes B} lässt sich ebenso als eine Abbildung κR{displaystyle kappa _{R}} von A{displaystyle A} in die Potenzmenge von B{displaystyle B} auffassen, κR:A→P(B),a↦{b∈B∣(a,b)∈R},{displaystyle kappa _{R}colon Ato {mathcal {P}}(B),;amapsto {bin Bmid (a,b)in R},} man spricht dann oft von einer Korrespondenz, und für B=A{displaystyle B=A} von einer Transitionsrelation.

Verkettung von Relationen |

Die Vorwärtsverkettung^[23] zweier zweistelliger Relationen R∈A×B,S∈C×D{displaystyle Rin Atimes B,Sin Ctimes D} ist wie folgt definiert:

R;S≡RS:={(a,d)∣∃b:aRb∧bSd}={(a,d)∈A×D∣∃b∈B∩C:(a,b)∈R∧(b,d)∈S}{displaystyle R;mathbf {;} ;Sequiv RS:={(a,d)mid exists bcolon ;aRbland bSd}={(a,d)in Atimes Dmid exists bin Bcap Ccolon ;(a,b)in Rland (b,d)in S}}.^[24][25][26]

Die Verkettung in der umgekehrten Reihenfolge wird als Rückwärtsverkettung^[27] bezeichnet:

S∘R:={(a,d)∈A×D∣∃b∈B∩C:(a,b)∈R∧(b,d)∈S}=R;S{displaystyle Scirc R:={(a,d)in Atimes Dmid exists bin Bcap Ccolon ;(a,b)in Rland (b,d)in S}=R;mathbf {;} ;S}.^[25][28]

Manche Autoren (W. v. O. Quine) verwenden hierfür alternativ die Notation S∣R{displaystyle Smid R}.^[29]

Die Reihenfolge ist bei der Rückwärtsverkettung dieselbe wie bei der Verkettung von Funktionen (die als spezielle Relationen aufgefasst werden können).

Die Verkettung zweistelliger Relationen wird auch als relatives Produkt bezeichnet. Bei der Verkettung kann auch die einfachste Relation, die in jedem kartesischen Produkt enthaltene leere Relation ∅{displaystyle emptyset } (leere Menge) auftreten, nämlich wenn B{displaystyle B} und C{displaystyle C} disjunkt sind, in Zeichen: B∩C=∅{displaystyle Bcap C=emptyset }.

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⊆A×B{displaystyle Rsubseteq Atimes B} definiert als

R⌣≡⌣R≡R∼≡R−1:={(b,a)∈B×A∣(a,b)∈R}{displaystyle {overset {smallsmile }{R}}equiv {}^{smallsmile }{R}equiv R^{sim }equiv R^{-1}:={(b,a)in Btimes Amid (a,b)in R}}.^[29][25]

Gelegentlich findet sich hierfür auch die Bezeichnung transponierte Relation, in Zeichen RT{displaystyle R^{T}}.^[30]

• 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{displaystyle n}-stellige Relationen ist die Permutation der Koordinaten der in ihr enthaltenen n{displaystyle n}-Tupel, speziell

• die Vertauschungen von lediglich 2 Koordinaten (Transpositionen) und


• die Umkehrung der Reihenfolge (Spiegelung),

beides Beispiele (zyklischer) selbstinverser Permutationen.

Sei π:{1,2,…,n}→{1,2,…,n}{displaystyle pi colon {1,2,dotsc ,n}rightarrow {1,2,dotsc ,n}} eine Permutation (d. h. eine bijektive Abbildung von {1,…,n}{displaystyle {1,dotsc ,n}} auf sich selbst),^[31] und sei R⊆(Ai)i∈{1,…,n}{displaystyle Rsubseteq (A_{i})_{iin {1,dotsc ,n}}} eine n{displaystyle n}-stellige Relation, dann ist S:={a∘π∣a∈R}{displaystyle S:={acirc pi mid ain R}} die nach Anwenden der Permutation π{displaystyle pi } sich ergebende Relation (man verstehe a=(ai)i∈{1,…,n}{displaystyle a=(a_{i})_{iin {1,dotsc ,n}}} als Familie). Im Fall der Spiegelung

π=σn=(12⋯nnn−1⋯1){displaystyle pi =sigma _{n}={begin{pmatrix}1&2&cdots &n\n&n-1&cdots &1end{pmatrix}}}

ist S={(an,…,a1)∣(a1,…,an)∈R}{displaystyle S={(a_{n},dotsc ,a_{1})mid (a_{1},dotsc ,a_{n})in R}}.

Bild und Urbild |

Bei einer zweistelligen Relation R⊆A×B{displaystyle Rsubseteq Atimes B} bezeichnet man als das Bild einer Menge oder Klasse X{displaystyle X} die Menge bzw. Klasse

R→(X)≡R⟨X⟩:={y∣∃x∈X:(x,y)∈R}{displaystyle R^{to }(X)equiv Rlangle Xrangle :={ymid exists xin Xcolon ;(x,y)in R}}.

Das Urbild einer Menge oder Klasse Y{displaystyle Y} ist die Menge bzw. Klasse

R←(Y)≡R⌣⟨Y⟩≡⌣R⟨Y⟩≡R∼⟨Y⟩≡R−1⟨Y⟩={x∣∃y∈Y:(x,y)∈R}{displaystyle R^{leftarrow }(Y)equiv {overset {smallsmile }{R}}langle Yrangle equiv {}^{smallsmile }{R}langle Yrangle equiv R^{sim }langle Yrangle equiv R^{-1}langle Yrangle ={xmid exists yin Ycolon ;(x,y)in R}}.^[32][33][34]

Gelegentlich findet sich hierfür auch die Bezeichnung R``Y{displaystyle R{grave {}}{grave {}}Y} (sic!),^[29][35]
oft auch mit eckigen Klammern als R[Y]{displaystyle R[Y]} notiert. Bei Korrespondenzen ist für die Bildfaser einer Einermenge (Singleton) {a}{displaystyle {a}} auch die Schreibweise κR(a)=R⟨{a}⟩{displaystyle kappa _{R}(a)=Rlangle {a}rangle } im Gebrauch, wofür teilweise ebenfalls die Notation mit eckigen Klammern verwendet wird, d. h. R[a]{displaystyle R[a]};^[36] im Fall symmetrischer Relationen, d. h. (ggf. partieller) Äquivalenz- bzw. Verträglichkeitsrelationen ist die Notation [a]R=R⟨{a}⟩=R−1⟨{a}⟩{displaystyle [a]_{R}=Rlangle {a}rangle =R^{-1}langle {a}rangle } und spricht von Äquivalenz- bzw. Verträglichkeits- oder Toleranzklassen.

Einschränkung |

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

Komplementäre Relation |

Für zweistellige Relationen R⊆A×B{displaystyle Rsubseteq Atimes B} bei festem Vor- und Nachbereich A,B{displaystyle A,B} ist die komplementäre Relation gegeben durch^[37]

R¯≡−R=(A×B)∖R={(x,y)∈A×B∣(x,y)∉R}{displaystyle {overline {R}}equiv {}^{-}R=(Atimes B)setminus R={(x,y)in Atimes Bmid (x,y)not in R}},

analog für n{displaystyle n}-stellige Relationen R⊆A1×⋯×An{displaystyle Rsubseteq A_{1}times dotsb times A_{n}} bei festen Trägerbereichen A=(A1,…,An){displaystyle A=(A_{1},dotsc ,A_{n})}. Auf den reellen Zahlen R{displaystyle mathbb {R} } ist beispielsweise ≤{displaystyle leq } die komplementäre Relation zu >{displaystyle >}.

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

R¯≡−R=((A×B)∖GR,A,B){displaystyle {overline {R}}equiv {}^{-}R=((Atimes B)setminus G_{R},A,B)},

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

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

R¯¯=R{displaystyle {overline {overline {R}}}=R}.

Homogene Relationen |

Ist A=B{displaystyle A=B}, also R⊆A×A{displaystyle Rsubseteq Atimes A}, dann nennt man die Relation homogen. Manche Autoren definieren eine allgemeine Relation bereits als homogene Relation, denn eine allgemeine Relation R⊆A×B{displaystyle Rsubseteq Atimes B} kann immer auch als Einschränkung einer homogenen betrachtet werden: R⊆(A∪B)×(A∪B){displaystyle Rsubseteq (Acup B)times (Acup B)}.

Spezielle homogene Relationen und Operationen auf homogenen Relationen |

Eine spezielle homogene Relation in einer Menge A{displaystyle A} ist die Gleichheits- oder Identitätsrelation oder Diagonale

IA:={(a,b)∈A×A∣a=b}={(a,a)∣a∈A}.{displaystyle mathrm {I} _{A}:={(a,b)in Atimes Amid a=b}={(a,a)mid ain A}.}

Alternative Notationen für die Diagonale sind ΔA{displaystyle Delta _{A}} oder DA{displaystyle mathrm {D} _{A}}; wenn A{displaystyle A} bereits bekannt ist, wird sie einfach mit I{displaystyle mathrm {I} }, Δ{displaystyle Delta } oder D{displaystyle mathrm {D} } bezeichnet.^[38]

Eine weitere spezielle homogene Relation ist die Allrelation oder Universalrelation

UA=A×A{displaystyle mathrm {U} _{A}=Atimes A} (auch mit Nabla als ∇A{displaystyle nabla _{A}} bezeichnet).

Wenn A{displaystyle A} bereits bekannt ist, wird wie bei der Identitätsrelation auch hier der Index weggelassen.^[39]

Die Allrelation spielt eine Rolle in der Graphentheorie (siehe unten). Ein Anwendungsbeispiel ist folgender Satz:

Ist G=(E,K){displaystyle G=(E,K)} ein gerichteter Graph mit einer Menge E{displaystyle E} von Ecken und einer (assoziierten) Relation K⊆E×E{displaystyle Ksubseteq Etimes E} von Kanten, so ist G{displaystyle G} genau dann (stark) zusammenhängend, wenn die reflexiv-transitive Hülle von K{displaystyle K} die Universalrelation ist.

Die Bildung der Umkehrrelation (konversen Relation) einer homogenen zweistelligen Relation liefert wieder eine homogene zweistellige 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.^[28]

Im Fall einer homogenen Relation R⊆A×A{displaystyle Rsubseteq Atimes A} ist die Verkettung R∘R{displaystyle Rcirc R} ebenfalls eine homogene Relation, sodass die homogenen Relationen in A{displaystyle A} ein Monoid mit der multiplikativen Verknüpfung ∘{displaystyle circ } und dem neutralen Element IA{displaystyle mathrm {I} _{A}} bilden. Somit kann R2:=R∘R{displaystyle R^{2}:=Rcirc R} und können allgemeiner Potenzen Rn:=R∘Rn−1{displaystyle R^{n}:=Rcirc R^{n-1}} für n∈N{displaystyle nin mathbb {N} } definiert werden, wobei R0:=IA{displaystyle R^{0}:=mathrm {I} _{A}} ist.^[40]IA{displaystyle mathrm {I} _{A}} wird daher auch Einsrelation auf der Menge A{displaystyle A} genannt.

In Erweiterung der Notation R−1{displaystyle R^{-1}} anstelle von R⌣{displaystyle {overset {smallsmile }{R}}} für die Umkehrrelation bezeichnet man deren Potenzen mit negativen Exponenten:^[41]

R−n:=R⌣n=Rn⌣{displaystyle R^{-n}:={overset {smallsmile }{R}}^{n}={overset {smallsmile }{R^{n}}}}.

Damit sind beliebige ganze Zahlen n∈Z{displaystyle nin mathbb {Z} } als Exponent zulässig.

Zudem besitzt jedes Monoid homogener Relationen mit der leeren Relation (Nullrelation)

O=∅{displaystyle mathrm {O} =emptyset }

noch ein absorbierendes Element.

Durch Vereinigung der verschiedenen Potenzen entstehen die Relationen^[42][41]

R∗:=⋃n∈N0Rn{displaystyle R^{*}:=textstyle bigcup _{nin {mathbb {N} _{0}}}R^{n}} und R+:=⋃n∈NRn{displaystyle R^{+}:=textstyle bigcup _{nin {mathbb {N} }}R^{n}}. ^[43]

Algebraische Strukturen |

Alles zusammengefasst, bilden die zweistelligen Relationen auf einer Menge A{displaystyle A} eine Relationsalgebra

Re(A)=(2UA,∩,∪,−,O,UA,∘,IA,⌣){displaystyle {mathfrak {Re}}(A)=(2^{U_{A}},cap ,cup ,{}^{-},mathrm {O} ,U_{A},circ ,mathrm {I} _{A},{}^{smallsmile })}^[44]

Unter Verwendung der Notationen UA=A2=A×A,2UA=2A2=P(A×A){displaystyle U_{A}=A^{2}=Atimes A,;;2^{U_{A}}=2^{A^{2}}={mathcal {P}}(Atimes A)}.^[45]

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

Homogene mehrstellige Relationen |

Homogene mehrstellige Relationen sind (mit ihrem Graphen) Teilmengen von An{displaystyle A^{n}}. Für festes n{displaystyle n} sind die Allrelation UA{displaystyle mathrm {U} _{A}} (auch ∇A{displaystyle nabla _{A}}) und die Identitätsrelation (Diagonale) IA{displaystyle mathrm {I} _{A}} (auch DA,ΔA{displaystyle mathrm {D} _{A},Delta _{A}}) gegeben durch

UA=An,IA={(ai)i∈{1,…,n}∈An∣a1=a2=⋯=an}{displaystyle mathrm {U} _{A}=A^{n},;;mathrm {I} _{A}={(a_{i})_{iin {1,dotsc ,n}}in A^{n}mid a_{1}=a_{2}=dotsb =a_{n}}}.

Die als Verallgemeinerung der Konversenbildung beschriebene Anwendung von Permutationen auf ihre n{displaystyle n}-Tupel sind hier von besonderer Bedeutung, da man auf diese Weise immer innerhalb der Teilmengen von An{displaystyle A^{n}} bleibt (Abgeschlossenheit). M. a. W. sind diese Operationen bijektive Abbildungen in P(An)=2An{displaystyle {mathcal {P}}(A^{n})=2^{A^{n}}}. Auch weitere von zweistelligen Relationen bekannte Begriffe wie Reflexivität und Symmetrie etc. lassen sich in kanonischer (natürlicher) Weise auf beliebig mehrstellige Relationen ausdehnen.

Graphentheorie und Verallgemeinerungen |

Die Graphentheorie beschreibt Mengen mit einer Relation darauf zusammen mit gewissen Verallgemeinerungen unter einem gemeinsamen Oberbegriff, dem Graphen.^[47] Die in der Graphentheorie betrachteten Fälle sind (wenn nicht anders angegeben) üblicherweise endlich (finit).

1. Eine relationale Struktur G{displaystyle G} bestehend aus einer Menge M{displaystyle M} zusammen mit einer Relation R{displaystyle R} darauf wird als gerichteter (auch orientierter) Graph G=(M,R){displaystyle G=(M,R)} bezeichnet. M=V(G){displaystyle M=V(G)} wird Knotenmenge des Graphen genannt, ihre Elemente heißen Knoten. E(G)=R{displaystyle E(G)=R} wird als Teilmenge von M×M{displaystyle Mtimes M} als Kantenmenge bezeichnet, ihre Elemente (geordnete Paare aus M{displaystyle M}) heißen gerichtete (d. h. orientierte) Kanten.

2. Symmetrische Graphen G=(M,R){displaystyle G=(M,R)}, d. h. Mengen M{displaystyle M} mit einer symmetrischen Relation R{displaystyle R}, sind äquivalent einem ungerichteten Graphen G′:=(M,{{a,b}∣aRb}){displaystyle G':=(M,{{a,b}mid a;R;b})}, dessen Kantenmenge E(G′){displaystyle E(G')} aus (ungerichteten) Kanten, nämlch den (ungeordnete) Mengen {a,b}{displaystyle {a,b}} mit a R b{displaystyle a R b} (hier äquivalent zu b R a{displaystyle b R a}) besteht.

3. Weitere Verallgemeinerungen betreffen sogenannte gerichtete Graphen mit zusammengefassten Mehrfachkanten, bei denen jede Kante eine natürliche Zahl als Multiplizität hat. Die Kanten solcher Graphen können durch eine Multimenge M{displaystyle {boldsymbol {M}}} dargestellt werden: eine Abbildung M=(M,f){displaystyle {boldsymbol {M}}=(M,f)} mit einer Menge M=supp(M){displaystyle M=supp({boldsymbol {M}})} und einer Abbildung f:M→N{displaystyle fcolon ;Mto mathbb {N} }, die jedem Knoten v∈M{displaystyle vin M} eine Farbe genannte positive Zahl f(v){displaystyle f(v)} zuordnet. Ähnlich sind Graphen mit gefärbte Knoten und/oder Kanten.^[48]

4. Von gewichteten Knoten und/oder Kanten: Von Gewichten anstelle von Farben spricht man, wenn die Abbildung f{displaystyle f} reellwertig ist. Bei f:M→[0,1]{displaystyle fcolon ;Mto [0,1]} gewichteten Knoten entspricht dies einer Fuzzymenge M=(M,f){displaystyle {boldsymbol {M}}=(M,f)}, bei f:M→R+{displaystyle fcolon ;Mto R^{+}} ist M=(M,f){displaystyle {boldsymbol {M}}=(M,f)} ein real valued multiset.^[49]
Entsprechendes gilt für gewichtete Kanten. Für orientierte Graphen bedeutet dies insbesondere, dass die Kantenmenge (eine Relation, d. h. Menge geordneter Knotenpaare) in einer Erweiterung des Relationsbegriffs zu einer Multimenge oder Fuzzymenge wird.

Beispiele |

• 
  

  

  
  

  
  

  Alle möglichen geordneten Paare (u,v){displaystyle (u,v)} mit u∈A:={a,b,c}{displaystyle uin A:={a,b,c}} und v∈B:={x,y,z}{displaystyle vin B:={x,y,z}} sowie eine zwischen A{displaystyle A} und B{displaystyle B} definierte Relation R.{displaystyle 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⊆A×B{displaystyle Rsubseteq Atimes B} zwischen zwei verschiedenen Mengen A,B,{displaystyle A,B,} der Fall A=B{displaystyle A=B} ist natürlich auch möglich.

Die Relation R{displaystyle R} heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
linkstotal bzw. definal (Multifunktion)	∀a∈A∃b∈B:(a,b)∈R{displaystyle forall ain A;exists bin {B}colon ;(a,b)in R}	IA⊆R−1∘R{displaystyle mathrm {I} _{A}subseteq R^{-1}circ R}	Jedes Element aus A{displaystyle A} hat mindestens einen Partner in B.{displaystyle B.}
rechtstotal bzw. surjektiv	∀b∈B∃a∈A:(a,b)∈R{displaystyle forall bin B;exists ain Acolon ;(a,b)in R}	IB⊆R∘R−1{displaystyle mathrm {I} _{B}subseteq Rcirc R^{-1}}	Jedes Element aus B{displaystyle B} hat mindestens einen Partner in A.{displaystyle A.}
linkseindeutig bzw. injektiv	∀b∈B∀a,c∈A:(a,b)∈R∧(c,b)∈R⇒a=c{displaystyle {begin{aligned}&forall bin B;forall a,cin Acolon \&(a,b)in R,land ,(c,b)in R;Rightarrow ;a=cend{aligned}}}	R−1∘R⊆IA{displaystyle R^{-1}circ Rsubseteq mathrm {I} _{A}}	Jedes Element aus B{displaystyle B} hat höchstens einen Partner in A.{displaystyle A.}
(rechts-) eindeutig (partielle Funktion)	∀a∈A∀b,d∈B:(a,b)∈R∧(a,d)∈R⇒b=d{displaystyle {begin{aligned}&forall ain A;forall b,din Bcolon \&(a,b)in R,land ,(a,d)in R;Rightarrow ;b=dend{aligned}}}	R∘R−1⊆IB{displaystyle Rcirc R^{-1}subseteq mathrm {I} _{B}}	Jedes Element aus A{displaystyle A} hat höchstens einen Partner in B.{displaystyle B.}

Die Relation R{displaystyle R} heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
bitotal	(∀a∈A∃b∈B:(a,b)∈R)∧(∀b∈B∃a∈A:(a,b)∈R){displaystyle {begin{aligned}&(forall ain A;exists bin Bcolon ;(a,b)in R)\land ;&(forall bin B;exists ain Acolon ;(a,b)in R)end{aligned}}}	IA⊆R−1∘R∧IB⊆R∘R−1{displaystyle {begin{aligned}&mathrm {I} _{A}subseteq R^{-1}circ R\land ;&mathrm {I} _{B}subseteq Rcirc R^{-1}end{aligned}}}	Jedes Element aus A{displaystyle A} hat mindestens einen Partner in B{displaystyle B} und umgekehrt.
eineindeutig	∀b,d∈B∀a,c∈A:(a,b)∈R∧(c,b)∈R⇒a=c,(a,b)∈R∧(a,d)∈R⇒b=d{displaystyle {begin{aligned}&forall b,din B;forall a,cin Acolon \&(a,b)in R,land ,(c,b)in R;Rightarrow ;a=c,\&(a,b)in R,land ,(a,d)in R;Rightarrow ;b=dend{aligned}}}	R−1∘R⊆IA∧R∘R−1⊆IB{displaystyle {begin{aligned}&R^{-1}circ Rsubseteq mathrm {I} _{A}\land ;&Rcirc R^{-1}subseteq mathrm {I} _{B}end{aligned}}}	Jedes Element aus B{displaystyle B} hat höchstens einen Partner in A{displaystyle A} und umgekehrt.
bijektiv	∀b∈B∃!a∈A:(a,b)∈R{displaystyle forall bin B;exists !ain Acolon ;(a,b)in R}	IB⊆R∘R−1∧R−1∘R⊆IA{displaystyle {begin{aligned}&mathrm {I} _{B}subseteq Rcirc R^{-1}\land ;&R^{-1}circ Rsubseteq mathrm {I} _{A}end{aligned}}}	Jedes Element aus B{displaystyle B} hat genau einen Partner in A.{displaystyle A.}
Abbildung bzw. Funktion	∀a∈A∃!b∈B:(a,b)∈R{displaystyle forall ain A;exists !bin Bcolon ;(a,b)in R}	IA⊆R−1∘R∧R∘R−1⊆IB{displaystyle {begin{aligned}&mathrm {I} _{A}subseteq R^{-1}circ R\land ;&Rcirc R^{-1}subseteq mathrm {I} _{B}end{aligned}}}	Jedes Element aus A{displaystyle A} hat genau einen Partner in B.{displaystyle B.}

Alternative Sprechweisen |

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

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{displaystyle R} genau dann bijektiv, wenn sie surjektiv und injektiv ist, also wenn ihre Umkehrrelation R−1{displaystyle R^{-1}} eine Funktion ist.

Die Relation R{displaystyle R} heißt	genau dann, wenn sie eine	ist oder gleichwertig (Mengenschreibweise)	und das bedeutet:
Surjektion	surjektive Funktion	IA⊆R−1∘R∧R∘R−1=IB{displaystyle {begin{aligned}&mathrm {I} _{A}subseteq R^{-1}circ R\land ;&Rcirc R^{-1}=mathrm {I} _{B}end{aligned}}}	Jedes Element aus A{displaystyle A} hat genau einen Partner in B{displaystyle B} und jedes Element aus B{displaystyle B} hat mindestens einen Partner in A.{displaystyle A.}
Injektion	injektive Funktion	IA=R−1∘R∧R∘R−1⊆IB{displaystyle {begin{aligned}&mathrm {I} _{A}=R^{-1}circ R\land ;&Rcirc R^{-1}subseteq mathrm {I} _{B}end{aligned}}}	Jedes Element aus A{displaystyle A} hat genau einen Partner in B{displaystyle B} und jedes Element aus B{displaystyle B} hat höchstens einen Partner in A.{displaystyle A.}
Bijektion	bijektive Funktion	IA=R−1∘R∧R∘R−1=IB{displaystyle {begin{aligned}&mathrm {I} _{A}=R^{-1}circ R\land ;&Rcirc R^{-1}=mathrm {I} _{B}end{aligned}}}	Jedes Element aus A{displaystyle A} hat genau einen Partner in B{displaystyle 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{displaystyle R} heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
rechtskomparativ bzw. drittengleich[50]	∀a,b,c∈A:(a,c)∈R∧(b,c)∈R⇒(a,b)∈R{displaystyle {begin{aligned}&forall a,b,cin Acolon \&(a,c)in R,land ,(b,c)in R\&Rightarrow ;(a,b)in Rend{aligned}}}	R−1∘R⊆R{displaystyle R^{-1}circ Rsubseteq 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{displaystyle a=c} und b=c{displaystyle b=c} stets a=b.{displaystyle a=b.}
linkskomparativ bzw. euklidisch[51][52]	∀a,b,c∈A:(a,b)∈R∧(a,c)∈R⇒(b,c)∈R{displaystyle {begin{aligned}&forall a,b,cin Acolon \&(a,b)in R,land ,(a,c)in R\&Rightarrow ;(b,c)in Rend{aligned}}}	R∘R−1⊆R{displaystyle Rcirc 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{displaystyle a=b} und a=c{displaystyle a=c} stets ebenso b=c.{displaystyle b=c.}
transitiv	∀a,b,c∈A:(a,b)∈R∧(b,c)∈R⇒(a,c)∈R{displaystyle {begin{aligned}&forall a,b,cin Acolon \&(a,b)in R,land ,(b,c)in R\&Rightarrow ;(a,c)in Rend{aligned}}}	R∘R⊆R{displaystyle Rcirc Rsubseteq 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{displaystyle a<b} und b<c{displaystyle b<c} stets a<c.{displaystyle a<c.}
intransitiv	∀a,b,c∈A:(a,b)∈R∧(b,c)∈R⇒(a,c)∉R{displaystyle {begin{aligned}&forall a,b,cin Acolon \&(a,b)in R,land ,(b,c)in R\&Rightarrow ;(a,c)notin R\end{aligned}}}	(R∘R)∩R=∅{displaystyle (Rcirc 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{displaystyle n} die (unmittelbare) Vorgängerin von n+1{displaystyle n+1} und n+1{displaystyle n+1} die (unmittelbare) Vorgängerin von n+2,{displaystyle n+2,} aber n{displaystyle n} ist nicht (unmittelbare) Vorgängerin von n+2.{displaystyle n+2.}

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

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

Die Relation R{displaystyle R} heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
symmetrisch	∀a,b∈A:(a,b)∈R⇒(b,a)∈R{displaystyle {begin{aligned}&forall a,bin Acolon \&(a,b)in R;Rightarrow ;(b,a)in Rend{aligned}}}	R−1⊆R{displaystyle R^{-1}subseteq R}	Die Relation ist ungerichtet, z. B. folgt aus a=b{displaystyle a=b} stets b=a{displaystyle b=a} (und umgekehrt)
		R−1=R{displaystyle R^{-1}=R}
antisymmetrisch bzw. identitiv	∀a,b∈A:(a,b)∈R∧(b,a)∈R⇒a=b{displaystyle {begin{aligned}&forall a,bin Acolon \&(a,b)in R,land ,(b,a)in R\&Rightarrow ;a=bend{aligned}}}	R−1∩R⊆I{displaystyle R^{-1}cap Rsubseteq mathrm {I} }	Es gibt keine zwei verschiedenen Elemente, die in beiden Richtungen in Relation stehen, z. B. folgt aus a≤b{displaystyle aleq b} und b≤a{displaystyle bleq a} stets a=b.{displaystyle a=b.}
asymmetrisch	∀a,b∈A:(a,b)∈R⇒(b,a)∉R{displaystyle {begin{aligned}&forall a,bin Acolon \&(a,b)in R;Rightarrow ;(b,a)notin Rend{aligned}}}	R−1∩R=∅{displaystyle R^{-1}cap R=emptyset }	Es gibt keine zwei Elemente, die in beiden Richtungen in Relation stehen, z. B. folgt aus a<b{displaystyle a<b} stets, dass b<a{displaystyle b<a} nicht gilt.

Die Relation R{displaystyle R} heißt	genau dann, wenn (Prädikatenlogik)	oder gleichwertig (Mengenschreibweise)	und das bedeutet:
total bzw. vollständig	∀a,b∈A:(a,b)∈R∨(b,a)∈R{displaystyle {begin{aligned}&forall a,bin Acolon \&(a,b)in R,lor ,(b,a)in Rend{aligned}}}	R−1∪R=A×A{displaystyle R^{-1}cup R=Atimes A}	Je zwei Elemente stehen in Relation, z. B. wenn stets a≤b{displaystyle aleq b} oder b≤a{displaystyle bleq a} gilt.
konnex[53] bzw. verbunden	∀a,b∈A:a≠b⇒(a,b)∈R∨(b,a)∈R{displaystyle {begin{aligned}&forall a,bin Acolon \&aneq b\&Rightarrow ;(a,b)in R,lor ,(b,a)in Rend{aligned}}}	R−1∪R∪I=A×A{displaystyle R^{-1}cup Rcup mathrm {I} =Atimes A}	Je zwei verschiedene Elemente stehen in Relation, z. B. wenn stets a=b,{displaystyle a=b,} a<b{displaystyle a<b} oder b<a,{displaystyle b<a,} aber ebenso wenn stets a≤b{displaystyle aleq b} oder b≤a{displaystyle bleq a} gilt.
trichotom	∀a,b∈A:((a,b)∈R⇒(b,a)∉R)∧(a≠b⇒(a,b)∈R∨(b,a)∈R){displaystyle {begin{aligned}&forall a,bin Acolon \&((a,b)in RRightarrow (b,a)notin R),land \&(aneq b\&Rightarrow ;(a,b)in R,lor ,(b,a)in R)end{aligned}}}	R−1∪R∪I=A×A∧R−1∩R=∅{displaystyle {begin{aligned}R^{-1}cup Rcup mathrm {I} &=Atimes 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{displaystyle a<b} oder b<a{displaystyle b<a} gilt.

Zwischen den Eigenschaften gelten folgende Zusammenhänge:

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

• 
  R{displaystyle R} ist reflexiv ⟺{displaystyle iff } R¯{displaystyle {overline {R}}} ist irreflexiv (und umgekehrt).
  


• 
  R{displaystyle R} ist symmetrisch ⟺{displaystyle iff } R¯{displaystyle {overline {R}}} ist symmetrisch.


• 
  R{displaystyle R} ist antisymmetrisch ⟺{displaystyle iff } R¯{displaystyle {overline {R}}} (und umgekehrt).
  


• 
  R{displaystyle R} ist total ⟺{displaystyle iff } R¯{displaystyle {overline {R}}} ist asymmetrisch (und umgekehrt).^[54]
  

Klassen von Relationen |

Zusammenhänge zwischen verschiedenen zweistelligen Relationen

Weitere wichtige Klassen von Relationen und ihre Eigenschaften:

• 
  Quasiordnung oder Präordnung: transitiv und reflexiv


• 
  Verträglichkeitsrelation oder Toleranzrelation: verträglich (reflexiv und symmetrisch)^[55] (englisch: im finiten Fall dependency relation, im transfiniten Fall tolerance relation).


• 
  Ä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{displaystyle x<y} (Beispiel: 2<3,{displaystyle 2<3,} „2 ist kleiner als 3“)
   


2. 
   x=y{displaystyle x=y} (Beispiel: 3=3,{displaystyle 3=3,} „3 ist gleich 3“)
   


3. 
   x>y{displaystyle x>y} (Beispiel: 3>2,{displaystyle 3>2,} „3 ist größer als 2“)
   

mit x,y∈R{displaystyle x,yin mathbb {R} }.

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

• 
  x≤y{displaystyle xleq y}, falls x<y{displaystyle x<y} oder x=y{displaystyle x=y} (Beispiel: 4≤5,{displaystyle 4leq 5,} „4 ist nicht größer als 5“)
  


• 
  x≥y{displaystyle xgeq y}, falls x>y{displaystyle x>y} oder x=y{displaystyle x=y} (Beispiel: 5≥5,{displaystyle 5geq 5,} „5 ist nicht kleiner als 5“)
  


• 
  x≠y{displaystyle xneq y}, falls x<y{displaystyle x<y} oder x>y{displaystyle x>y} (Beispiel: 4≠5,{displaystyle 4neq 5,} „4 ist nicht gleich 5“)
  

für alle x,y∈R{displaystyle x,yin 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,+,⋅){displaystyle (H,+,cdot )} mit Nullelement 0{displaystyle 0} und Einselement 1{displaystyle 1} ist folgendes C{displaystyle {mathcal {C}}} eine Kategorie:

• 
  Ob(C)=Ob(Set){displaystyle mathrm {Ob} ({mathcal {C}})=mathrm {Ob} (mathbf {Set} )}.


• Ein Morphismus f∈HomC(X,Y){displaystyle fin mathrm {Hom} _{mathcal {C}}(X,Y)} ist eine Funktion f:X×Y→H{displaystyle fcolon Xtimes Yto H}.


• Für Objekte X{displaystyle X} gilt
  

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

  
  

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

• Für Objekte X,Y,Z{displaystyle X,Y,Z} und Morphismen f∈HomC(Y,Z), g∈HomC(X,Y){displaystyle fin mathrm {Hom} _{mathcal {C}}(Y,Z), gin mathrm {Hom} _{mathcal {C}}(X,Y)} gilt
  

  
  (f∘g)(x,z):=∑y∈Yg(x,y)⋅f(y,z){displaystyle (fcirc g)(x,z):=sum _{yin Y}g(x,y)cdot f(y,z)}.

  
  

Die Morphismen sind also mengenindizierte Matrizen und ihre Komposition geschieht wie bei der Matrixmultiplikation, idx{displaystyle mathrm {id} _{x}} entspricht der Einheitsmatrix E{displaystyle E}.

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

• Kongruenzrelation


• Prädikat (Logik)

Literatur |

• 
  Garrett Birkhoff: Lattice Theory. 3. Auflage. AMS, Providence, RI 1973, ISBN 0-8218-1025-1. 
  


• Stefan Brass: Mathematische Logik mit Datenbank-Anwendungen. Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, Halle 2005, S. 176 (informatik.uni-halle.de [PDF]). 
  


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


• 
  Dieter Klaua: Mengenlehre. De Gruyter, Berlin / New York 1979, ISBN 3-11-007726-4 (Der Autor benutzt die Bezeichnung Korrespondenz im mengentheoretischen Sinn synonym zu Relation, verwendet dann aber das Zeichen F{displaystyle F} anstelle von R{displaystyle R}. Im Artikel hier wird jedoch durchgängig R{displaystyle R} bzw. GR{displaystyle G_{R}} (Graph von R{displaystyle R}) geschrieben). 
  


• H. König: Entwurf und Strukturtheorie von Steuerungen für Fertigungseinrichtungen (= ISW Forschung und Praxis. Band 13). Springer, Berlin/Heidelberg 1976, ISBN 3-540-07669-7, S. 15–17, doi:10.1007/978-3-642-81027-5_1. 
  


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


• Heike Mildenberger: Axiomatische Mengenlehre. Universität Freiburg, 9. November 2015, S. 58 (mathematik.uni-freiburg.de [PDF]). 
  


• 
  Willard van Orman Quine: Mengenlehre und ihre Logik (= Logik und Grundlagen der Mathematik. Band 10). Vieweg+Teubner, Wiesbaden 1973, ISBN 3-528-08294-1, S. 264 (amerikanisches Englisch: Set Theory And Its Logic. Cambridge, MA 1963. Ullstein 1978 als Taschenbuch). 
  


• Gerard O’Regan: Guide to Discrete Mathematics. Sets, Relations and Functions (= Texts in Computer Science (TCS)). Springer, Schweiz 2016, S. 25–51, doi:10.1007/978-3-319-44561-8_2 (springer.com [PDF; 1000 kB]). 
  


• 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. Band 1: Logik und Mengenlehre. Scriptor, Kronberg/Ts. 1974, ISBN 3-589-00023-6. 
  


• Siegfried Wendt: Nichtphysikalische Grundlagen der Informationstechnik – Interpretierte Formalismen. 2. Auflage. Springer, Berlin/Heidelberg 2013, ISBN 978-3-540-54452-4, doi:10.1007/978-3-642-87627-1 (books.google.de). 
  

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.

Einzelnachweise und Anmerkungen |

1. 
   ↑ ^ab G. Smolka: Programmierung: Kapitel 2 – Mengenlehre, bei: Universität des Saarlandes, 20. Mai 2003, § 2.5. Binäre Relationen, S. 15.
   


2. 
   ↑ Walter Gellert, Herbert Kästner, Siegfried Neuber (Hrsg.): Lexikon der Mathematik. Bibliographisches Institut Leipzig, 1979, S. 484.
   


3. 
   ↑ ^ab Albert Monjallon: Einführung in die moderne Mathematik. Ausgabe 2. Springer-Verlag, 2013, ISBN 978-3-663-16043-4, S. 74. doi:10.1007/978-3-663-16043-4, (books.google.de)
   


4. 
   ↑ ^ab Wilhelm Dangelmaier: Produktionstheorie 1: Methodische Grundlagen. Springer-Verlag, 2017, ISBN 978-3-662-54922-3, S. 478. doi:10.1007/978-3-662-54923-0 (books.google.de)
   


5. 
   ↑ ^ab Cobocards: Vorbereich und Nachbereich.
   


6. 
   ↑ ^ab Matheboard: Relationen: Relationen: Was genau ist mit Vorbereich/Nachbereich einer Relation gemeint?
   


7. 
   ↑ Dieter Klaua: Mengenlehre. Seite 62, Definition 5 (1. Teil).
   


8. 
   ↑ ^abc H. König: Entwurf und Strukturtheorie von Steuerungen für Fertigungseinrichtungen. Seite 19.
   


9. 
   ↑ Weitere Bezeichnungsweisen: VR,V(R){displaystyle V_{R},V(R)}, in der englischsprachigen Literatur: dom⁡R{displaystyle operatorname {dom} R}, siehe:
   Gerard O’Regan: Sets, Relations and Functions. S. 36.
   


10. 
    ↑ Dieter Klaua: Mengenlehre. Seite 62, Definition 5, (2. Teil).
    


11. 
    ↑ Weitere Bezeichnungsweisen: NR,N(R){displaystyle N_{R},N(R)}, in der englischsprachigen Literatur: rng⁡R{displaystyle operatorname {rng} R}, siehe:
    
    Gerard O’Regan: Sets, Relations and Functions. S. 36.
    


12. 
    ↑ Dieter Klaua: Mengenlehre. Seite 62, Definition 5, (3. Teil).
    


13. 
    ↑ In der Theorie algebraischer Strukturen benutzt man – besonders im Hinblick auf die Kategorientheorie die Begriffe domain und codomain meist im Sinn von Quell- und Zielmenge, während in einführenden Schriften zur Mengenlehre diese meist als Urbild- und Bildmenge definiert werden,
    


14. 
    ↑ auch mengenähnlich, mengenartig, auf engl.: left-narrow bzw. set-like genannt, siehe Wikibooks: Mathematik-Glossar: Mathematische Attribute: vorgängerklein
    


15. 
    ↑ Heike Mildenberger 2015, S. 59f.
    


16. 
    ↑ Martin Ziegler: Vorlesung über Mengenlehre, Universität Freiburg, 1992–2014, S. 12.
    


17. 
    ↑ Azriel Levy: Basic Set Theory (= Dover Books on Mathematics. Band 13). Courier Corporation, Newburyport 2012, ISBN 978-0-486-15073-4, S. 22, (online)
    


18. 
    ↑ Falls Urelemente zugelassen sind: für Urelemente b{displaystyle b} ist {a∈A∣a∈b}=∅{displaystyle {ain Amid ain b}=emptyset }, ebenfalls eine Menge.
    


19. 
    ↑ Siehe auch: Axiomatic Set Theory, Getting a model of (ZF – Fnd) ∪ { ¬Fnd} from a model of ZF, Ben Gurion University (BGU) of the Negev, The Department of Mathematics, 2003.
    


20. 
    ↑ Im allgemeinen Fall mit der Trägermengensequenz A=(Ai)i∈{1,…n}{displaystyle A=(A_{i})_{iin {1,dots n}}} ist die Allrelation UA=∏A{displaystyle mathrm {U} _{A}=textstyle prod A}, im homogenen Fall mit der n-fachen Trägermenge A{displaystyle A} ist UA=An{displaystyle U_{A}=A^{n}}.
    


21. 
    ↑ Stefan Brass (2005), S. 19.
    


22. 
    ↑ Die charakteristische Funktion als Wahrheitsfunktion entspricht daher einem logischen Prädikat, und in der Modelltheorie nennt man die Relationssymbole deswegen auch Prädikatsymbole, siehe Stefan Brass (2005) S. 16.
    


23. 
    ↑ englisch: forward relational composition
    


24. 
    ↑ Mathematics Stack Exchange: Forward and backward composition in relational algebra Diskussion der Verkettungsrichtungen im Zusammenhang mit der Verkettung von Funktionen als spezielle Relationen. Für geordnete Paare wird teilweise die Maplet-Notation verwendet: x↦y≡(x,y){displaystyle xmapsto yequiv (x,y)}
    


25. 
    ↑ ^abc Glossary of Z notation §Relations, University of Washington
    


26. 
    ↑ Gelegentlich findet sich auch der Strichpunkt in Konturdarstellung.
    R⨟S{displaystyle R{mbox{⨟}}S} wird in Wikipedia aber hardware- und einstellungsabhängig nicht immer korrekt dargestellt.
    


27. 
    ↑ englisch: backward relational composition
    


28. 
    ↑ ^ab H. König: Entwurf und Strukturtheorie von Steuerungen für Fertigungseinrichtungen. Seite 21.
    


29. 
    ↑ ^abc W. v. O. Quine: Mengenlehre und ihre Logik. Seite 47.
    


30. 
    ↑ Relationsalgebra. In: Mathepedia.de.
    


31. 
    ↑ Als Bijektion auch mit π:{1,2,…,n}↠↣⁡{1,2,…,n}{displaystyle pi colon {1,2,dotsc ,n}operatorname {twoheadrightarrow !!!!!!!!!!;;rightarrowtail } {1,2,dotsc ,n}} notiert.
    


32. 
    ↑ Zur Notation R→,R←{displaystyle R^{to },R^{leftarrow }} siehe Gary Hardegree: Set Theory, Chapter 2: Relations, University of Massachusetts, Amherst, Department of Philosophy, Herbst 2015, S. 11: D16 und D17. Im Gegensatz zu den anderen Notationen referenzieren diese Symbole Abbildungen (Funktionen) zwischen den Potenzmengen P(A),P(B){displaystyle {mathcal {P}}(A),{mathcal {P}}(B)}.
    


33. 
    ↑ Sinngemäß: D. Klaua: Mengenlehre. S. 63, Definition 6 (a).
    


34. 
    ↑ Bei Ordnungsrelationen und ähnlichen sprechen manche Autoren auch von Vorgängermenge oder -klasse, siehe Heike Mildenberger 2015, S. 6, Definition 1.12.
    


35. 
    ↑ W. v. O. Quine: Mengenlehre und ihre Logik. Seite 17. Achtung: Der Ausdruck ist als Bild betitelt, definiert aber klar das Urbild (eine Menge von linksseitigen Koordinaten = Argumenten x{displaystyle x}). Man beachte, dass diese Notation hier im Vergleich zu Funktionen konträr verwendet wird, bei Funktionen steht diese für das Bild (eine Menge von rechtsseitigen Koordinaten = Funktionswerten y{displaystyle y}) einer Menge unter einer Funktion f{displaystyle f}. Dabei sind Funktionen spezielle Relationen. Siehe Bild (Mathematik) §Alternative Notationen.
    


36. 
    ↑ Johannes Köbler: Einführung in die Theoretische Informatik: Relationen. Humboldt-Universität Berlin, Institut für Informatik WS2013/14, S. 68.
    


37. 
    ↑ W. v. O. Quine: Mengenlehre und ihre Logik. Seite 17.
    


38. 
    ↑ Der obigen ausführlichen Relationsdefinition folgend wird man die Diagonale als den Graphen der Identität verstehen: IA=(ΔA,A,A){displaystyle mathrm {I} _{A}=(Delta _{A},A,A)} (Relation) mit ΔA={(a,a)∣a∈A}{displaystyle Delta _{A}={(a,a)mid ain A}} (Graph).
    


39. 
    ↑ Der obigen ausführlichen Relationsdefinition folgend wird man in Analogie zur Diagonalen das Nabla als den Graphen der Allrelation verstehen: UA=(∇A,A,A){displaystyle mathrm {U} _{A}=(nabla _{A},A,A)} (Relation) mit ∇A=A×A{displaystyle nabla _{A}=Atimes A} (Graph)
    


40. 
    ↑ Das kann zu Verwechslungen mit dem kartesischen Produkt Rn=R1×⋯×Rn{displaystyle R^{n}=R_{1}times dotsb times R_{n}} mit R=R1=⋯=Rn{displaystyle R=R_{1}=dotsb =R_{n}} führen. Die Bedeutung ergibt sich jeweils aus dem Sinnzusammenhang.
    


41. 
    ↑ ^ab Gerard O’Regan: Sets, Relations and Functions. S. 39.
    


42. 
    ↑ Siehe dazu auch: Kleenesche Hülle.
    


43. 
    ↑ Zu den Transitivitätseigenschaften dieser Vereinigungen siehe Proving that ⋃n?1∞Rn{displaystyle bigcup _{n?1}^{infty }R^{n}} is a transitive relation on A, auf: StackExchange: Mathematics 2018.
    


44. 
    ↑ Robin Hirsch, Ian Hodkinson: Relation algebras. S. 7, auf: Third Indian Conference on Logic and its Applications (ICLA). 7.–11. Januar 2009, Chennai, India.
    


45. 
    ↑ Von den Verknüpfungen −,⌣{displaystyle {}^{-},{}^{smallsmile }} (einstellig) sowie ∩,∪,∘{displaystyle cap ,cup ,circ } (zweistellig) sind – genau genommen – die Einschränkungen auf A{displaystyle A} bzw. A2{displaystyle A^{2}} gemeint.
    


46. 
    ↑ C. Brink, K. Britz, R. A. Schmidt: Peirce Algebras. (1994), S. 163f. In: M. Nivat, C. Rattray, T. Rus, G. Scollo (Hrsg.): Algebraic Methodology and Software Technology (AMAST’93). Workshops in Computing. Springer, London.
    


47. 
    ↑ Der Begriff Graph im graphentheoretischen Sinn ist zu unterscheiden vom Begriff Graph einer Relation entsprechend der eingangs erwähnten ausführlichen Definition von Relationen (wie auch Abbildungen), welche in der Graphentheorie nicht verwendet wird.
    


48. 
    ↑ Der Begriff Farbe rührt daher, dass man die entsprechend der Multimengentheorie als Multiplizität verstandene Zahl f(v){displaystyle f(v)} in der bildlichen Darstellung als nummerncodierte Farbe der Kante v{displaystyle v} wiedergibt, analog bei gefärbten Knoten e{displaystyle e}.
    Ein Beispiel für Farbnummern wären etwa die RAL-Farben.
    


49. 
    ↑ W.D. Blizard: Real-valued Multisets and Fuzzy Sets. In: Fuzzy Sets and Systems. Vol. 33, 1989, S. 77–97. doi:10.1016/0165-0114(89)90218-2.
    


50. 
    ↑ „Zwei Größen, die einer und derselben dritten gleich sind, sind untereinander gleich.“ Vgl.
    Henri Poincaré: Wissenschaft und Hypothese. Autor. dt. Ausg. m. erl. Anm. v. F. u. L. Lindemann. Teubner, Leipzig 1904, S. 36.
    


51. 
    ↑ Wolfgang Rautenberg: Einführung in Die Mathematische Logik. Ein Lehrbuch. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, S. 42.
    


52. 
    ↑ Das 1. Axiom in Euklids Elementen kann dagegen auch als gleichbedeutend mit drittengleich angesehen werden.
    


53. 
    ↑ Nicht selten wird konnex auch wie total definiert.
    


54. 
    ↑ Man erkennt dies leicht anhand der obigen Tabellen (1. und 2. Spalte) unter Berücksichtigung von ¬(aRb)⟺aR¯b{displaystyle neg (aRb)iff a{overline {R}}b}, d. h. ¬(a,b)∈R⟺(a,b)∉R⟺(a,b)∈R¯{displaystyle neg (a,b)in Riff (a,b)not in Riff (a,b)in {overline {R}}} und der prädikatenlogischen Regeln. Die Umkehrungen gelten wegen Involutivität R¯¯=R{displaystyle {overline {overline {R}}}=R}.
    


55. 
    ↑ Wendt 2013, Seite 31