Relation (Mathematik)

Grundidee und Definition

Eine mathematische Relation beschreibt eindeutig, welche Objekte miteinander in Beziehung stehen. Formal ist eine Relation R eine Menge von n-Tupeln: Die Tupel, die zu R gehören, geben genau die bestehenden Beziehungen an.

Meist ist mit „Relation“ eine zweistellige oder binäre Relation gemeint. Zwischen Mengen A und B ist sie eine Teilmenge des kartesischen Produkts:

R ⊆ A × B, wobei A × B = {(a,b) | a ∈ A, b ∈ B}.

Gilt (a,b) ∈ R, schreibt man auch a R b und sagt: „a steht in Relation zu b.“ Die Reihenfolge ist wichtig: Das geordnete Paar (a,b) ist im Allgemeinen nicht dasselbe wie (b,a). A heißt Quellmenge und B Zielmenge. Für A ≠ B heißt die Relation heterogen; für A = B heißt sie homogen.

In einer genaueren Definition wird die Relation als Tripel R = (G_R,A,B) aufgefasst. Dabei ist G_R = Graph(R) ⊆ A × B die Menge der tatsächlich enthaltenen Paare. Zwei Relationen mit demselben Graphen heißen im Wesentlichen gleich.

Der Definitionsbereich oder Urbildbereich ist die Menge aller tatsächlich links vorkommenden Elemente: Db(R) = {a | ∃b: (a,b) ∈ G_R} ⊆ A. Der Bildbereich oder Wertevorrat enthält alle tatsächlich rechts vorkommenden Elemente: Wb(R) = {b | ∃a: (a,b) ∈ G_R} ⊆ B. Das Feld ist ihre Vereinigung: Fd(R) = Db(R) ∪ Wb(R).

Die leere Teilmenge des Produkts heißt Nullrelation O = ∅. Das gesamte kartesische Produkt heißt Allrelation oder Universalrelation U.

Mehrstellige Relationen und Darstellungen

Eine n-stellige Relation ist eine Teilmenge eines Produkts von n Mengen:

R ⊆ A₁ × … × Aₙ.

Ihre Elemente sind Tupel (a₁,…,aₙ) mit aᵢ ∈ Aᵢ. In der ausführlichen Form gilt R = (G_R,A₁,…,Aₙ). Die Mengen A₁,…,Aₙ heißen Trägermengen. Die minimale i-te Trägermenge Trᵢ(R) besteht aus allen Elementen, die im Graphen tatsächlich an der i-ten Stelle vorkommen. Das Feld ist die Vereinigung aller minimalen Trägermengen.

Eine einstellige Relation auf A ist einfach eine Teilmenge R ⊆ A. Beispielsweise wird „Person x ist weiblich“ als Teilmenge einer Grundmenge von Personen modelliert. Eine dreistellige Relation wie „Person x lernt das Fach y beim Lehrer z“ ist eine Menge von 3-Tupeln. Nullstellige Relationen sind die beiden Teilmengen des leeren kartesischen Produkts {∅}, also ∅ und {∅}; sie entsprechen den Wahrheitswerten falsch und wahr.

Jede Relation besitzt eine charakteristische Funktion. Für R ⊆ A₁ × … × Aₙ ist χ_R: A₁ × … × Aₙ → {wahr,falsch}, wobei χ_R(a₁,…,aₙ) genau dann wahr ist, wenn (a₁,…,aₙ) ∈ R. Bei binären Relationen gilt somit χ_R(a,b) ⇔ a R b ⇔ (a,b) ∈ R.

Eine binäre Relation R ⊆ A × B kann außerdem als Korrespondenz κ_R: A → P(B) verstanden werden. Jedem a wird die Menge {b ∈ B | (a,b) ∈ R} seiner Partner zugeordnet. Sind Trägerbereiche keine Mengen, sondern echte Klassen, spricht man von Klassenrelationen. Dabei können zusätzliche Größenbedingungen wie vorgängerklein oder nachfolgerklein erforderlich sein.

Operationen auf Relationen

Für R ⊆ A × B und S ⊆ B × C ist die Verkettung, Nacheinanderausführung oder das relative Produkt definiert durch

S ∘ R = {(a,c) ∈ A × C | ∃b ∈ B: (a,b) ∈ R ∧ (b,c) ∈ S}.

Dabei wird zuerst R und danach S angewendet. Als Beispiel lässt sich „Schwägerin sein von“ aus passenden Verkettungen der Beziehungen „Bruder sein von“, „Ehefrau sein von“, „Ehepartner(in) sein von“ und „Schwester sein von“ zusammensetzen.

Die Umkehrrelation vertauscht die beiden Einträge jedes Paares: R⁻¹ = {(b,a) ∈ B × A | (a,b) ∈ R}. So ist die Umkehrung von „ist Nachkomme von“ die Beziehung „ist Vorfahre von“, die Umkehrung von „ist kleiner als“ ist „ist größer als“. Bei n-stelligen Relationen wird dies durch Permutationen der Koordinaten verallgemeinert; eine Spiegelung ersetzt (a₁,…,aₙ) durch (aₙ,…,a₁).

Für X bezeichnet R→(X) = {y | ∃x ∈ X: (x,y) ∈ R} das Bild von X. Für Y ist R←(Y) = R⁻¹→(Y) = {x | ∃y ∈ Y: (x,y) ∈ R} das Urbild von Y.

Bei festem A und B ist die komplementäre Relation R̅ = (A × B) \ R. Sie enthält genau die Paare, die nicht in R liegen. Das Komplementieren ist involutiv: R̅̅ = R. Auf den reellen Zahlen ist beispielsweise ≤ die komplementäre Relation zu >. Relationen können außerdem auf Teilmengen ihrer Trägermengen eingeschränkt werden.

Relationen als Funktionen

Funktionen sind spezielle binäre Relationen R ⊆ A × B. Vier grundlegende Eigenschaften beschreiben, wie viele Partner die Elemente besitzen:

• linkstotal: Jedes a ∈ A hat mindestens einen Partner in B. • rechtstotal oder surjektiv: Jedes b ∈ B hat mindestens einen Partner in A. • linkseindeutig oder injektiv: Jedes b ∈ B hat höchstens einen Partner in A. • rechtseindeutig: Jedes a ∈ A hat höchstens einen Partner in B.

Eine Relation ist genau dann eine totale Funktion, wenn sie linkstotal und rechtseindeutig ist: Zu jedem a ∈ A existiert genau ein b ∈ B. Dann schreibt man f(a) = b oder f: a ↦ b. Eine Multifunktion ist linkstotal, darf einem Element aber mehrere Werte zuordnen. Eine partielle Funktion ist rechtseindeutig, muss jedoch nicht für jedes Element von A einen Wert besitzen.

Eine Funktion ist surjektiv, wenn jedes Element von B mindestens einmal als Wert auftritt. Sie ist injektiv, wenn verschiedene Elemente aus A verschiedene Werte besitzen. Sie ist bijektiv, wenn sie injektiv und surjektiv ist; dann hat jedes Element aus A genau einen Partner in B und umgekehrt.

Als Relation besitzt jede Funktion eine Umkehrrelation. Eine Umkehrfunktion existiert jedoch genau dann, wenn die Funktion bijektiv ist, denn nur dann ist auch R⁻¹ wieder eine Funktion.

Homogene Relationen und ihre Eigenschaften

Eine homogene Relation erfüllt R ⊆ A × A. Wichtige Beispiele sind die Identitätsrelation I_A = {(a,a) | a ∈ A} und die Universalrelation U_A = A × A.

Für homogene Relationen werden besonders folgende Eigenschaften unterschieden:

• reflexiv: Für jedes a gilt (a,a) ∈ R, also I_A ⊆ R. Irreflexiv bedeutet, dass kein (a,a) enthalten ist. • symmetrisch: Aus a R b folgt b R a, also R⁻¹ = R. • antisymmetrisch: Aus a R b und b R a folgt a = b. • asymmetrisch: Aus a R b folgt, dass b R a nicht gilt. • transitiv: Aus a R b und b R c folgt a R c; gleichwertig gilt R ∘ R ⊆ R. • intransitiv: Aus a R b und b R c folgt, dass a R c nicht gilt. Intransitivität ist nicht dasselbe wie bloße Nichttransitivität. • total: Für alle a,b gilt a R b oder b R a. • konnex: Für alle verschiedenen a,b gilt a R b oder b R a. • trichotom: Je zwei verschiedene Elemente stehen in genau einer der beiden Richtungen in Relation.

Daraus entstehen wichtige Relationsklassen: Eine Quasiordnung ist reflexiv und transitiv. Eine Äquivalenzrelation ist reflexiv, symmetrisch und transitiv. Eine Halbordnung ist reflexiv, antisymmetrisch und transitiv. Eine Vollordnung ist zusätzlich total. Bei einer Wohlordnung besitzt jede nichtleere Teilmenge von A ein kleinstes Element. Eine Striktordnung ist transitiv, irreflexiv und asymmetrisch; eine strenge Vollordnung ist zusätzlich konnex.

Für homogene Relationen sind Potenzen definiert: R⁰ = I_A und Rⁿ = R ∘ Rⁿ⁻¹. Ferner gelten R* = ⋃{n∈N₀} Rⁿ und R+ = ⋃{n∈N} Rⁿ. Mit Verkettung und I_A bilden die homogenen Relationen auf A ein Monoid; zusammen mit Durchschnitt, Vereinigung, Komplement und Umkehrung bilden sie eine Relationsalgebra.

Graphen, Relationszeichen und Anwendung

Ein gerichteter Graph kann als Menge M zusammen mit einer homogenen Relation R dargestellt werden: G = (M,R). Die Elemente von M sind Knoten, die geordneten Paare in R sind gerichtete Kanten. Ist R symmetrisch, entspricht dies einem ungerichteten Graphen mit ungeordneten Kanten {a,b}. Ein gerichteter Graph ist genau dann stark zusammenhängend, wenn die reflexiv-transitive Hülle seiner Kantenrelation die Universalrelation ist. Erweiterungen erlauben Mehrfachkanten, Farben oder reelle Gewichte; dadurch können Knoten- oder Kantenmengen als Multimengen oder Fuzzymengen auftreten.

Für reelle Zahlen sind <, = und > grundlegende Vergleichsrelationen. Zwei reelle Zahlen stehen immer in genau einer dieser drei Beziehungen. Außerdem gilt x ≤ y genau dann, wenn x < y oder x = y; x ≥ y genau dann, wenn x > y oder x = y; und x ≠ y genau dann, wenn x < y oder x > y. Für komplexe Zahlen existieren diese Ordnungsrelationen nicht. Das Zeichen ≤ wird auch für abstrakte Ordnungsrelationen verwendet, während < keine Ordnungsrelation im Sinne der hier verwendeten reflexiven Definition ist. Äquivalenzrelationen werden häufig mit ≈, ~ oder ≡ bezeichnet.

In der Kategorientheorie entsteht die Kategorie Rel als Spezialfall einer Matrixkonstruktion über dem booleschen Halbring ({0,1},∨,∧). Ihre Morphismen entsprechen Relationen; ihre Komposition entspricht der Relationsverkettung beziehungsweise einer Matrixmultiplikation mit ∨ und ∧.

Operationen auf vollständigen Relationen untersucht die relationale Algebra. In der Informatik sind Relationen insbesondere die Grundlage relationaler Datenbanken.