Relation (Mathematik)

Eine Relation ( „Beziehung“, „Verhältnis“) ist allgemein eine Beziehung, die zwischen Dingen bestehen kann. Bei Relationen im Sinne der Mathematik ist stets klar, ob sie bestehen oder nicht, sodass Objekte nicht „bis zu einem gewissen Grade“ in einer Relation zueinander stehen. Damit ist eine einfache mengentheoretische Definition des Begriffs möglich: Eine Relation  ist eine Menge von -Tupeln. In der Relation  zueinander stehende Dinge bilden -Tupel, die Element von  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  und  ein geordnetes Paar  Stammen dabei  und  aus verschiedenen Grundmengen  und , so heißt die Relation heterogen oder „Relation zwischen den Mengen  und  Stimmen die Grundmengen überein  dann heißt die Relation homogen oder „Relation in bzw. auf der Menge 

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  (auch binäre Relation genannt) zwischen zwei Mengen  und  ist eine Teilmenge des kartesischen Produkts 
.

Die Menge  wird als Quellmenge (englisch: set of departure) der Relation  bezeichnet, die Menge  als Zielmenge (englisch: set of destination).

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)  der Relation genannt. Eine zweistellige Relation  ist dann definiert als Tripel
 mit .
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 einer gegebenen zweistelligen Relation  wird der kleinstmögliche Vorbereich zum Graphen  verstanden, dessen Elemente alle in den geordneten Paaren von  tatsächlich auf der linken Seite auftreten, in Zeichen
.
Der Wertevorrat, Werte- oder Bild- oder Nachbereich bezeichnet in diesem Sinne den kleinsten Nachbereich zu  bei gegebenem , dessen Elemente also alle in den Paaren von  auf der rechten Seite auftreten, in Zeichen
.
Gelegentlich wird für die Vereinigungsmenge die Bezeichnung Feld (oder  Knotenmenge) benutzt, in Zeichen
.

Darüber hinaus finden sich folgende Bezeichnungen:
 Domäne (englisch domain)  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)  entweder für die Zielmenge oder für die Bildmenge,
 Knotenmenge () für das Feld einer Relation.

Stimmen zwei Relationen in ihren Graphen überein, so sagt man auch, sie seien im Wesentlichen gleich.Beispiel: Jede Relation  ist im Wesentlichen gleich mit  und mit der homogenen Relation .

n-stellige Relation 
Allgemeiner ist eine -stellige Relation  eine Teilmenge des kartesischen Produkts von  Mengen 
 mit .
Dabei bezeichnet  die endliche Folge der Mengen, und  das kartesische Produkt.

Die ausführlichere Definition lässt sich auch auf -stellige Relationen verallgemeinern und man erhält dann das -Tupel
 mit .

Die Mengen  heißen Trägermengen der Relation mit den minimalen Trägermengen zum Graphen , nämlich
.

Das Feld einer -stelligen Relation ist gegeben durch
.

Wesentliche Gleichheit ist analog definiert wie für zweistellige Relationen durch Übereinstimmung der Graphen, insbesondere ist jede -stellige Relation  im Wesentlichen gleich mit  und mit der homogenen Relation .

 Einstellige und nullstellige Relation
Eine einstellige Relation auf einer Menge  ist somit einfach eine Teilmenge , in der ausführlichen Definition  mit .

Die nullstelligen Relationen sind demnach die Teilmengen des leeren kartesischen Produkts  bzw. , also  und , ausführlich  und .

Relationen zwischen oder auf echten Klassen 
Häufig sind die Trägerbereiche  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 (, im zweistelligen Fall Definitions- und Wertemenge ) sind tatsächlich Mengen, aber es ist nicht nötig, sich von vornherein auf Quellmenge, Zielmenge, … () 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  mit Quellklasse  und Zielklasse  heißt vorgängerklein,
wenn für alle  die Klasse der Vorgänger  (Urbildfaser von , s. u.) eine Menge (d. h. keine echte Klasse) ist.
Die Relation heißt englisch right-narrow (deutsch in etwa nachfolgerklein),
wenn für alle  die Klasse der Nachfolger  (Bildfaser von ) 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  ist für jede Klasse  vorgängerklein, da die  keine echten Klassen sein können, sondern Mengen sind und damit  ebenfalls eine Menge ist. 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  und  ist die Menge aller geordneten Paare von  und  wobei  irgendein Element aus der Menge  und  eines aus  darstellt. Bei dem geordneten Paar ist die Reihenfolge wichtig, d. h.  unterscheidet sich von  im Gegensatz zum ungeordneten Paar  das identisch ist mit  Für  schreibt man auch , um zu verdeutlichen, dass jene Beziehung zwischen den Objekten besteht (wie in ).
Die Leermenge als Teilmenge des kartesischen Mengenprodukts als Relation aufgefasst heißt Nullrelation ,
das volle Produkt heißt Allrelation (auch Universalrelation)  (auch als  bezeichnet).

Relationen und Funktionen 
 Eine Funktion  ist eine spezielle, nämlich eine linkstotale und rechtseindeutige (zweistellige) Relation, näheres siehe unten.
 Eine Multifunktion  ist eine linkstotale Relation .
 Eine partielle Funktion  ist eine (im Allgemeinen nicht linkstotale) rechtseindeutige Relation .
In allen Fällen ist  (beziehungsweise  wenn die ausführliche Definition zugrunde gelegt wird).

Für Funktionen und Multifunktionen gilt:
 Bei der ausführlicheren Definition  kann, weil  durch  eindeutig bestimmt ist (linkstotal), auch  weggelassen und einfacher  genommen werden.

Für Funktionen und partielle Funktionen gilt:
 Für  bzw.  wird auch  (englisch: maplet), oder  geschrieben.

Allgemein gilt:
 Die nullstelligen Relationen  (als nullstellige Nullrelation) und  (als nullstellige Vollrelation) haben als charakteristische Funktionen die booleschen oder logischen Konstanten  und , wie immer für Nullrelation und Allrelation.
 Der Fall einstelliger Relationen ist trivial.
 Eine Relation  (bzw. ) entspricht auf eindeutige Weise einer Wahrheitsfunktion . Diese Funktion ist auch als Indikatorfunktion oder charakteristische Funktion der Teilmenge  (bzw. ) bekannt, wobei  durch  ersetzbar ist.
 Eine -stellige Relation  (bzw. ) entspricht der charakteristischen Funktion 

Es gilt:
 .
 .
 .
 .
 Eine Relation  lässt sich ebenso als eine Abbildung  von  in die Potenzmenge von  auffassen,  man spricht dann oft von einer Korrespondenz, und für  von einer Transitionsrelation.

Verkettung von Relationen 
Die Vorwärtsverkettung zweier zweistelliger Relationen  ist wie folgt definiert:
 

Die Verkettung in der umgekehrten Reihenfolge wird als Rückwärtsverkettung bezeichnet:
 .
Manche Autoren (W. v. O. Quine) verwenden hierfür alternativ die Notation .

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  (leere Menge) auftreten, nämlich wenn  und  disjunkt sind, in Zeichen: .

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  definiert als
 .
Gelegentlich findet sich hierfür auch die Bezeichnung transponierte Relation, in Zeichen .

 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 -stellige Relationen ist die Permutation der Koordinaten der in ihr enthaltenen -Tupel, speziell
 die Vertauschungen von lediglich 2 Koordinaten (Transpositionen) und
 die Umkehrung der Reihenfolge (Spiegelung),
beides Beispiele (zyklischer) selbstinverser Permutationen.

Sei  eine Permutation (d. h. eine bijektive Abbildung von  auf sich selbst), und sei  eine -stellige Relation, dann ist  die nach Anwenden der Permutation  sich ergebende Relation (man verstehe  als Familie). Im Fall der Spiegelung
 
ist .

Bild und Urbild 
Bei einer zweistelligen Relation  bezeichnet man als das Bild einer Menge oder Klasse  die Menge bzw. Klasse
 .

Das Urbild einer Menge oder Klasse  ist die Menge bzw. Klasse
.
Gelegentlich findet sich hierfür auch die Bezeichnung  (sic!),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 ). 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 ) einer Menge unter einer Funktion . Dabei sind Funktionen spezielle Relationen. Siehe Bild (Mathematik) §Alternative Notationen.
oft auch mit eckigen Klammern als  notiert. Bei Korrespondenzen ist für die Bildfaser einer Einermenge (Singleton)  auch die Schreibweise  im Gebrauch, wofür teilweise ebenfalls die Notation mit eckigen Klammern verwendet wird, d. h.  im Fall symmetrischer Relationen, d. h. (ggf. partieller) Äquivalenz- bzw. Verträglichkeitsrelationen ist die Notation  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  bei festem Vor- und Nachbereich  ist die komplementäre Relation gegeben durch
,
analog für -stellige Relationen  bei festen Trägerbereichen . Auf den reellen Zahlen  ist beispielsweise  die komplementäre Relation zu .

Wird die komplexe Notation  zugrunde gelegt, so ist
 ,
wobei  jetzt keine äußeren Zugaben mehr sind, sondern Bestandteile der Relation; analog für -stellige Relationen in dieser Notation.

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

Homogene Relationen 
Ist , also , dann nennt man die Relation homogen. Manche Autoren definieren eine allgemeine Relation bereits als homogene Relation, denn eine allgemeine Relation  kann immer auch als Einschränkung einer homogenen betrachtet werden: .

Spezielle homogene Relationen und Operationen auf homogenen Relationen 
Eine spezielle homogene Relation in einer Menge  ist die Gleichheits- oder Identitätsrelation oder Diagonale
 
Alternative Notationen für die Diagonale sind  oder ; wenn  bereits bekannt ist, wird sie einfach mit ,  oder  bezeichnet.

Eine weitere spezielle homogene Relation ist die Allrelation oder Universalrelation
  (auch mit Nabla als  bezeichnet).
Wenn  bereits bekannt ist, wird wie bei der Identitätsrelation auch hier der Index weggelassen.

Die Allrelation spielt eine Rolle in der Graphentheorie (siehe unten). Ein Anwendungsbeispiel ist folgender Satz:
 Ist  ein gerichteter Graph mit einer Menge  von Ecken und einer (assoziierten) Relation  von Kanten, so ist  genau dann (stark) zusammenhängend, wenn die reflexiv-transitive Hülle von  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.

Im Fall einer homogenen Relation  ist die Verkettung  ebenfalls eine homogene Relation, sodass die homogenen Relationen in  ein Monoid mit der multiplikativen Verknüpfung  und dem neutralen Element  bilden. Somit kann  und können allgemeiner Potenzen  für  definiert werden, wobei  ist.
 wird daher auch Einsrelation auf der Menge  genannt.

In Erweiterung der Notation  anstelle von  für die Umkehrrelation bezeichnet man deren Potenzen mit negativen Exponenten:
 .

Damit sind beliebige ganze Zahlen  als Exponent zulässig.

Zudem besitzt jedes Monoid homogener Relationen mit der leeren Relation (Nullrelation)
 
noch ein absorbierendes Element.

Durch Vereinigung der verschiedenen Potenzen entstehen die Relationen
  und .

Algebraische Strukturen 
Alles zusammengefasst, bilden die zweistelligen Relationen auf einer Menge  eine Relationsalgebra
 

Unter Verwendung der Notationen .

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

Homogene mehrstellige Relationen 
Homogene mehrstellige Relationen sind (mit ihrem Graphen) Teilmengen von . Für festes  sind die Allrelation  (auch ) und die Identitätsrelation (Diagonale)  (auch ) gegeben durch
 .
Die als Verallgemeinerung der Konversenbildung beschriebene Anwendung von Permutationen auf ihre -Tupel sind hier von besonderer Bedeutung, da man auf diese Weise immer innerhalb der Teilmengen von  bleibt (Abgeschlossenheit). M. a. W. sind diese Operationen bijektive Abbildungen in . 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. Die in der Graphentheorie betrachteten Fälle sind (wenn nicht anders angegeben) üblicherweise endlich (finit).

1. Eine relationale Struktur  bestehend aus einer Menge  zusammen mit einer Relation  darauf wird als gerichteter (auch orientierter) Graph  bezeichnet.  wird Knotenmenge des Graphen genannt, ihre Elemente heißen Knoten.  wird als Teilmenge von  als Kantenmenge bezeichnet, ihre Elemente (geordnete Paare aus ) heißen gerichtete (d. h. orientierte) Kanten.

2. Symmetrische Graphen , d. h. Mengen  mit einer symmetrischen Relation , sind äquivalent einem ungerichteten Graphen , dessen Kantenmenge  aus (ungerichteten) Kanten, nämlich den (ungeordnete) Mengen  mit  (hier äquivalent zu ) 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  dargestellt werden: eine Abbildung  mit einer Menge  und einer Abbildung , die jedem Knoten  eine Farbe genannte positive Zahl  zuordnet. Ähnlich sind Graphen mit gefärbte Knoten und/oder Kanten.

4. Von gewichteten Knoten und/oder Kanten: Von Gewichten anstelle von Farben spricht man, wenn die Abbildung  reellwertig ist. Bei  gewichteten Knoten entspricht dies einer Fuzzymenge , bei  ist  ein real valued multiset.
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

Eigenschaften zweistelliger Relationen

Allgemeine Relationen 
Die folgenden Relationen sind für Funktionen (dargestellt als spezielle Relationen) wichtig. Im Allgemeinen besteht hier die Relation  zwischen zwei verschiedenen Mengen  der Fall  ist natürlich auch möglich.

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)  genau dann bijektiv, wenn sie surjektiv und injektiv ist, also wenn ihre Umkehrrelation  eine Funktion ist.

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.

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

Zwischen den Eigenschaften gelten folgende Zusammenhänge:

Zwischen den Eigenschaften einer Relation  und denen ihres Komplements  bestehen folgende Zusammenhänge:
  ist reflexiv   ist irreflexiv (und umgekehrt).
  ist symmetrisch   ist symmetrisch.
  ist antisymmetrisch   ist konnex (und umgekehrt).
  ist total   ist asymmetrisch (und umgekehrt).

Klassen von 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)  (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:
  (Beispiel:  „2 ist kleiner als 3“)
  (Beispiel:  „3 ist gleich 3“)
  (Beispiel:  „3 ist größer als 2“)
mit .

Zwei reelle Zahlen stehen immer in genau einer dieser Relationen zueinander. Mit diesen Relationszeichen lassen sich auch weitere bilden. Es gilt:
 , falls  oder  (Beispiel:  „4 ist nicht größer als 5“)
 , falls  oder  (Beispiel:  „5 ist nicht kleiner als 5“)
 , falls  oder  (Beispiel:  „4 ist nicht gleich 5“)
für alle .

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  mit Nullelement  und Einselement  ist folgendes  eine Kategorie:
 .
 Ein Morphismus  ist eine Funktion .
 Für Objekte  gilt
 .
 Das ist identisch mit dem Kronecker-Delta: .
 Für Objekte  und Morphismen  gilt
 .

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

Im Sonderfall  gilt , d. h.,  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

Weblinks

Einzelnachweise und Anmerkungen 

Mathematischer Grundbegriff
Mengenlehre