Relation (Mathematik)

Menge von n-Tupeln
(Weitergeleitet von Allrelation)

Eine Relation (lateinisch relatio „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

Bearbeiten

Zweistellige Relation

Bearbeiten

Eine zweistellige Relation   (auch binäre Relation genannt)[1] zwischen zwei Mengen   und   ist eine Teilmenge des kartesischen Produkts  [2][3][4]

 .

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

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   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[6][7] 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

 .[8][9][10]

Der Wertevorrat, Werte- oder Bild- oder Nachbereich[6][7] 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

 .[11][9][12]

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

 .[13][9]

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,[14]
  • Knotenmenge ( ) 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   ist im Wesentlichen gleich mit   und mit der homogenen Relation  .

n-stellige Relation

Bearbeiten

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

Bearbeiten

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,[15][16] wenn für alle   die Klasse der Vorgänger   (Urbildfaser von  , s. u.) eine Menge (d. h. keine echte Klasse) ist.[17] Die Relation heißt englisch right-narrow (deutsch in etwa nachfolgerklein),[18] 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.[19][20] Die Begriffe Vorgänger und Nachfolger selbst werden üblicherweise im Kontext von Ordnungsrelationen verwendet, siehe Ordnungsrelation §Vorgänger und Nachfolger.

Erläuterungen und Schreibweisen

Bearbeiten

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).[21]

Relationen und Funktionen

Bearbeiten
  • 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:

  1. 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.[22]
  2. Der Fall einstelliger Relationen ist trivial.
  3. 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.
  4. Eine  -stellige Relation   (bzw.  ) entspricht der charakteristischen Funktion  

Es gilt:

  •  .
 .
 .
 .[23]
  • 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

Bearbeiten

Die Vorwärtsverkettung[24] zweier zweistelliger Relationen   ist wie folgt definiert:

 [25][26][27]

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

 .[26][29]

Manche Autoren (W. v. O. Quine) verwenden hierfür alternativ die Notation  .[30]

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

Bearbeiten

Die Umkehrrelation (auch konverse Relation, Konverse oder inverse Relation genannt) ist für eine zweistellige Relation   definiert als

 .[30][26]

Gelegentlich findet sich hierfür auch die Bezeichnung transponierte Relation, in Zeichen  .[31]

  • 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

beides Beispiele (zyklischer) selbstinverser Permutationen.

Sei   eine Permutation (d. h. eine bijektive Abbildung von   auf sich selbst),[32] 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

Bearbeiten

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

 .[33][34][35]

Gelegentlich findet sich hierfür auch die Bezeichnung   (sic!),[30][36] 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.  ;[37] 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

Bearbeiten

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

Bearbeiten

Für zweistellige Relationen   bei festem Vor- und Nachbereich   ist die komplementäre Relation gegeben durch[38]

 ,

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

Bearbeiten

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

Bearbeiten

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.[39]

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.[40]

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.[29]

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.[41]   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:[42]

 .

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[43][42]

  und  [44]

Algebraische Strukturen

Bearbeiten

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

 [45]

Unter Verwendung der Notationen  .[46]

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

Homogene mehrstellige Relationen

Bearbeiten

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

Bearbeiten

Die Graphentheorie beschreibt Mengen mit einer Relation darauf zusammen mit gewissen Verallgemeinerungen unter einem gemeinsamen Oberbegriff, dem Graphen.[48] 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.[49]

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.[50] 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

Bearbeiten

Eigenschaften zweistelliger Relationen

Bearbeiten

Allgemeine Relationen

Bearbeiten

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.

Die Relation   heißt genau dann, wenn (Prädikatenlogik) oder gleichwertig (Mengenschreibweise) und das bedeutet:
linkstotal bzw. definal
(Multifunktion)
    Jedes Element aus   hat mindestens einen Partner in  
rechtstotal bzw. surjektiv     Jedes Element aus   hat mindestens einen Partner in  
linkseindeutig bzw. injektiv     Jedes Element aus   hat höchstens einen Partner in  
(rechts-) eindeutig
(partielle Funktion)
    Jedes Element aus   hat höchstens einen Partner in  
Die Relation   heißt genau dann, wenn (Prädikatenlogik) oder gleichwertig (Mengenschreibweise) und das bedeutet:
bitotal     Jedes Element aus   hat mindestens einen Partner in   und umgekehrt.
eineindeutig     Jedes Element aus   hat höchstens einen Partner in   und umgekehrt.
bijektiv     Jedes Element aus   hat genau einen Partner in  
Abbildung bzw. Funktion     Jedes Element aus   hat genau einen Partner in  

Funktionen

Bearbeiten

Übersicht über Funktionseigenschaften bei Relationen

Bearbeiten

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.

Die Relation   heißt genau dann, wenn sie eine ist oder gleichwertig (Mengenschreibweise) und das bedeutet:
Surjektion surjektive Funktion   Jedes Element aus   hat genau einen Partner in   und jedes Element aus   hat mindestens einen Partner in  
Injektion injektive Funktion   Jedes Element aus   hat genau einen Partner in   und jedes Element aus   hat höchstens einen Partner in  
Bijektion bijektive Funktion   Jedes Element aus   hat genau einen Partner in   und umgekehrt.

Umkehrfunktion

Bearbeiten

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

Bearbeiten

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   heißt genau dann, wenn (Prädikatenlogik) oder gleichwertig (Mengenschreibweise) und das bedeutet:
rechtskomparativ bzw. drittengleich[51]     Stehen zwei Elemente jeweils zu einem gleichen dritten Element in Relation, dann stehen auch sie zueinander in Relation. Z. B. gilt mit   und   stets  
linkskomparativ bzw. euklidisch[52][53]     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   und   stets ebenso  
transitiv     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   und   stets  
intransitiv     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   die (unmittelbare) Vorgängerin von   und   die (unmittelbare) Vorgängerin von   aber   ist nicht (unmittelbare) Vorgängerin von  

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

Die Relation   heißt genau dann, wenn (Prädikatenlogik) oder gleichwertig (Mengenschreibweise) und das bedeutet:
reflexiv     Jedes Element steht in Relation zu sich selbst, z. B. ist stets  
 
irreflexiv     Kein Element steht in Relation zu sich selbst, z. B. gilt   für kein  
Die Relation   heißt genau dann, wenn (Prädikatenlogik) oder gleichwertig (Mengenschreibweise) und das bedeutet:
symmetrisch     Die Relation ist ungerichtet, z. B. folgt aus   stets   (und umgekehrt)
 
antisymmetrisch bzw. identitiv     Es gibt keine zwei verschiedenen Elemente, die in beiden Richtungen in Relation stehen, z. B. folgt aus   und   stets  
asymmetrisch     Es gibt keine zwei Elemente, die in beiden Richtungen in Relation stehen, z. B. folgt aus   stets, dass   nicht gilt.
Die Relation   heißt genau dann, wenn (Prädikatenlogik) oder gleichwertig (Mengenschreibweise) und das bedeutet:
total bzw. vollständig     Je zwei Elemente stehen in Relation, z. B. wenn stets   oder   gilt.
konnex[54] bzw. verbunden     Je zwei verschiedene Elemente stehen in Relation, z. B. wenn stets   oder   (für   ) gilt.
trichotom     Je zwei verschiedene Elemente stehen stets auf genau eine Weise in Relation, z. B. wenn stets entweder   oder   gilt.

Zwischen den Eigenschaften gelten folgende Zusammenhänge:

 
Zusammenhang der Eigenschaften binärer Relationen

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).[55]

Klassen von Relationen

Bearbeiten
 
Zusammenhänge zwischen verschiedenen zweistelligen Relationen

Weitere wichtige Klassen von Relationen und ihre Eigenschaften:

Relationszeichen

Bearbeiten

In der elementaren Mathematik gibt es drei grundlegende Vergleichsrelationen:

  1.   (Beispiel:   „2 ist kleiner als 3“)
  2.   (Beispiel:   „3 ist gleich 3“)
  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

Bearbeiten

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

Bearbeiten

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

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • 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   anstelle von  . Im Artikel hier wird jedoch durchgängig   bzw.   (Graph von  ) 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).
Bearbeiten
Wikibooks: Mathe für Nicht-Freaks: Relation – Lern- und Lehrmaterialien

Einzelnachweise und Anmerkungen

Bearbeiten
  1. a b G. Smolka: Programmierung: Kapitel 2 – Mengenlehre, bei: Universität des Saarlandes, 20. Mai 2003, § 2.5. Binäre Relationen, S. 15.
  2. V A. Zorich & J. Schüle: Analysis 1. Springer-Verlag, 2006, ISBN 978-3-540-33278-7, S. 21 (Google Books).
  3. Dieter Klaua: Mengenlehre. De Gruyter, Berlin 2016, ISBN 978-3-11-084381-1, S. 68 (Google Books).
  4. Jaroslav Nešetril: Diskrete Mathematik. Springer-Verlag, 2013, ISBN 978-3-662-06756-7, S. 36 (Google Books).
  5. Walter Gellert, Herbert Kästner, Siegfried Neuber (Hrsg.): Lexikon der Mathematik. Bibliographisches Institut Leipzig, 1979, S. 484.
  6. a b 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)
  7. a b 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)
  8. Dieter Klaua: Mengenlehre. Seite 62, Definition 5 (1. Teil).
  9. a b c H. König: Entwurf und Strukturtheorie von Steuerungen für Fertigungseinrichtungen. Seite 19.
  10. Weitere Bezeichnungsweisen:  , in der englischsprachigen Literatur:  , siehe:
    Gerard O’Regan: Sets, Relations and Functions. S. 36.
  11. Dieter Klaua: Mengenlehre. Seite 62, Definition 5, (2. Teil).
  12. Weitere Bezeichnungsweisen:  , in der englischsprachigen Literatur:  , siehe:
    Gerard O’Regan: Sets, Relations and Functions. S. 36.
  13. Dieter Klaua: Mengenlehre. Seite 62, Definition 5, (3. Teil).
  14. 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,
  15. auch mengenähnlich, mengenartig, auf engl.: left-narrow bzw. set-like genannt, siehe Wikibooks: Mathematik-Glossar: Mathematische Attribute: vorgängerklein
  16. Heike Mildenberger 2015, S. 59f.
  17. Martin Ziegler: Vorlesung über Mengenlehre, Universität Freiburg, 1992–2014, S. 12.
  18. Azriel Levy: Basic Set Theory (= Dover Books on Mathematics. Band 13). Courier Corporation, Newburyport 2012, ISBN 978-0-486-15073-4, S. 22, (online)
  19. Falls Urelemente zugelassen sind: für Urelemente   ist  , ebenfalls eine Menge.
  20. 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.
  21. Im allgemeinen Fall mit der Trägermengensequenz   ist die Allrelation  , im homogenen Fall mit der n-fachen Trägermenge   ist  .
  22. Stefan Brass (2005), S. 19.
  23. 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.
  24. englisch: forward relational composition
  25. 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:  
  26. a b c Glossary of Z notation §Relations, University of Washington
  27. Gelegentlich findet sich auch der Strichpunkt in Konturdarstellung.
      wird in Wikipedia aber hardware- und einstellungsabhängig nicht immer korrekt dargestellt.
  28. englisch: backward relational composition
  29. a b H. König: Entwurf und Strukturtheorie von Steuerungen für Fertigungseinrichtungen. Seite 21.
  30. a b c W. v. O. Quine: Mengenlehre und ihre Logik. Seite 47.
  31. Relationsalgebra. In: Mathepedia.de.
  32. Als Bijektion auch mit   notiert.
  33. Zur Notation   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  .
  34. Sinngemäß: D. Klaua: Mengenlehre. S. 63, Definition 6 (a).
  35. Bei Ordnungsrelationen und ähnlichen sprechen manche Autoren auch von Vorgängermenge oder -klasse, siehe Heike Mildenberger 2015, S. 6, Definition 1.12.
  36. 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.
  37. Johannes Köbler: Einführung in die Theoretische Informatik: Relationen. Humboldt-Universität Berlin, Institut für Informatik WS2013/14, S. 68.
  38. W. v. O. Quine: Mengenlehre und ihre Logik. Seite 17.
  39. Der obigen ausführlichen Relationsdefinition folgend wird man die Diagonale als den Graphen der Identität verstehen:   (Relation) mit   (Graph).
  40. Der obigen ausführlichen Relationsdefinition folgend wird man in Analogie zur Diagonalen das Nabla als den Graphen der Allrelation verstehen:   (Relation) mit   (Graph)
  41. Das kann zu Verwechslungen mit dem kartesischen Produkt   mit   führen. Die Bedeutung ergibt sich jeweils aus dem Sinnzusammenhang.
  42. a b Gerard O’Regan: Sets, Relations and Functions. S. 39.
  43. Siehe dazu auch: Kleenesche Hülle.
  44. Zu den Transitivitätseigenschaften dieser Vereinigungen siehe Proving that   is a transitive relation on A, auf: StackExchange: Mathematics 2018.
  45. Robin Hirsch, Ian Hodkinson: Relation algebras. S. 7, auf: Third Indian Conference on Logic and its Applications (ICLA). 7.–11. Januar 2009, Chennai, India.
  46. Von den Verknüpfungen   (einstellig) sowie   (zweistellig) sind – genau genommen – die Einschränkungen auf   bzw.   gemeint.
  47. 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.
  48. 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.
  49. Der Begriff Farbe rührt daher, dass man die entsprechend der Multimengentheorie als Multiplizität verstandene Zahl   in der bildlichen Darstellung als nummerncodierte Farbe der Kante   wiedergibt, analog bei gefärbten Knoten  .
    Ein Beispiel für Farbnummern wären etwa die RAL-Farben.
  50. 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.
  51. „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.
  52. Wolfgang Rautenberg: Einführung in Die Mathematische Logik. Ein Lehrbuch. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, S. 42.
  53. Das 1. Axiom in Euklids Elementen kann dagegen auch als gleichbedeutend mit drittengleich angesehen werden.
  54. Nicht selten wird konnex auch wie total definiert.
  55. Man erkennt dies leicht anhand der obigen Tabellen (1. und 2. Spalte) unter Berücksichtigung von  , d. h.   und der prädikatenlogischen Regeln. Die Umkehrungen gelten wegen Involutivität  .
  56. Wendt 2013, Seite 31