Mathe für Nicht-Freaks: Binäre Relation

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

Binäre Relationen sind zweistellige Relationen, also Teilmengen des kartesischen Produkts $A\times B$ der Mengen $A$ und $B$.

Homogene und heterogene Relationen

Eine binäre Relation $R\subseteq A\times B$ heißt homogen, wenn die Mengen $A$ und $B$ identisch sind. Im Fall $A\ne B$ nennt man die Relation $R\subseteq A\times B$ heterogen.

Homogene Relationen beschreiben damit Beziehungen innerhalb einer Menge und heterogene Relationen beschreiben Beziehungen von Objekten aus unterschiedlichen Mengen.

Darstellung endlicher binärer Relationen

Es gibt zwei wesentliche Möglichkeiten, binäre Relationen zwischen endlichen Mengen darzustellen: Pfeildiagramme und Relationsmatrizen. Diese möchten wir dir anhand der folgenden Relationen vorstellen:

• heterogene Relation $R_1$: „Der Fluss $x$ fließt im Land $y$“, wobei $x$ ein Fluss der Menge $\{\text{Nil, Elbe, Donau, Rhein}\}$ und $y$ ein Land der Menge $\{\text{Irland, Deutschland, Niederlande, Ukraine}\}$ ist.
• homogene Relation $R_2$: „$x$ ist ein Nachfolger von $y$“ auf der Grundmenge $\{1,2,3,4\}$.

Pfeildiagramm

Die erste Möglichkeit der Darstellung sind Pfeildiagramme. Hier werden alle Objekte, die in Relation zueinander stehen, durch Pfeile miteinander verbunden. So sieht die heterogene Relation $R_1$ „Der Fluss $x$ fließt im Land $y$“ im Pfeildiagramm so aus:

Pfeildiagramm der Relation "Fluss x fließt im Land y"

Da die zweite Relation $R_2$ „$x$ ist ein Nachfolger von $y$“ homogen ist, kann hier auf die Darstellung zweier Mengen verzichtet werden:

Pfeildiagramm der Relation "x ist eine Nachfolger von y"

Relationsmatrix

Bei der Relationsmatrix wird eine Tabelle für die Relation aufgestellt. Hier wird in jeder Zelle eingetragen, ob das Objekt der aktuellen Spalte mit dem Objekt der aktuellen Zeile in Relation steht. Die Relation $R_1$ „Der Fluss $x$ fließt im Land $y$“ sieht als Relationsmatrix so aus:

	Irland	Deutschland	Niederlande	Ukraine
Donau		X		X
Elbe		X
Nil
Rhein		X	X

Die Relationsmatrix der Relation $R_2$ „$x$ ist ein Nachfolger von $y$“ auf der Menge $\{1,2,3,4\}$ ist folgende:

	1	2	3	4
1
2	X
3		X
4			X

Die Hauptdiagonale in der Relationsmatrix zu einer homogenen Relation ist die Menge der Zellen, bei denen die Objekte der Spalte dieselben sind wie die Objekte der Zeile:

	1	2	3	$\dots$	n
1	Haupt-
2		dia-
3			gona-
$⋮$				$\ddots$
n					le

Wichtige Begriffe

Bildmenge

Pfeildiagramm der Relation "Fluss x fließt im Land y"

Wir betrachten nochmals die Relation $R_1$ „Der Fluss $x$ fließt im Land $y$“. Wir möchten jetzt zu einem bestimmten Fluss alle Länder wissen, durch die er fließt. Für die Donau stellen wir beispielsweise fest, dass sie durch Deutschland und die Ukraine fließt. Anders ausgedrückt: Die Donau steht mit Deutschland und der Ukraine in Relation.

Wir können zu einem beliebigen Element $x$ aus der Grundmenge alle Elemente heraussuchen, die mit $x$ in Relation stehen. Diese Menge wird als Bildmenge oder als das Bild von $x$ bezeichnet. Für das Bild von $x$ unter der Relation $R$ schreibt man $xR$. Der Ausdruck $xR$ bezeichnet also die Menge aller Elemente, die mit $x$ in Relation stehen. Er ist eigentlich recht intuitiv, denn $xR$ ist die Menge aller $y$, die nach dem $xR$ stehen können, wo also $xRy$ eine wahre Aussage ist.

Du wirst vielleicht schon den Bildbegriff für Funktionen kennen, welcher die Menge aller Funktionswerte für eine gegebene Menge von Argumenten ist. Dies ist kein Zufall, denn Funktionen können als spezielle binäre Relationen aufgefasst werden (solche, bei dem es für jedes $x$ genau ein $y$ mit $xRy$ gibt). Der Begriff der Bildmenge für Relationen ist in diesem Fall mit der Bildmenge der Funktion identisch. Der Begriff des Bildes einer Relation ist damit eine Verallgemeinerung des Bildes von Funktionen.

Im Folgenden bezeichnet $R\subseteq A\times B$ eine binäre Relation zwischen den Mengen $A$ und $B$.

Die obige Definition von Bild beschränkt sich auf einen einzigen Eingabewert. Es sollte auch möglich sein ein Bild für beliebig viele Elemente zu erhalten, also für eine Menge von Eingabewerten. Dazu suchen wir uns einfach alle Elemente heraus, die mindestens mit einem dieser Eingabewerten in Relation stehen. Wenn wir beispielsweise das Bild der Donau und des Rheins wissen wollen, dann ist dies die Menge $\{\text{Deutschland, Ukraine, Niederlande}\}$. Deutschland steht sowohl mit der Donau und dem Rhein in Relation und gehört somit zur gesuchten Bildmenge. Die Ukraine steht mit der Donau in Relation, womit es auch Element der Bildmenge ist (es steht mit mindestens einem Eingabewert in Relation). Gleiches gilt für Niederlande, die mit dem Rhein in Relation steht.

Urbild

Wenn wir für ein beliebiges Objekt die Objekte heraussuchen können, die mit diesem in Relation stehen, können wir das natürlich in „beide Richtungen“ tun. Stelle dir vor, wir suchen jetzt nicht mehr zu einem Fluss die dazugehörigen Länder, sondern wir haben ein Land und wollen die Flüsse wissen, die in diesem Land fließen. Dies entspricht der Suche nach dem Urbild. Beispielsweise ist das Urbild der Ukraine die Donau. Für das Urbild von $y$ schreibt man $Ry$. Dabei ist $Ry$ die Menge aller Objekte die vor $Ry$ stehen können, also die Menge aller $x$ mit $xRy$.

Einschränkung einer Relation Vorlage:Anker

Ist $R$ eine Relation auf $A\times B$, so lässt sich diese auf eine Teilmenge $A^{\prime }\times B^{\prime }$ reduzieren. Die so entstehende Relation $R^{\prime }$ enthält nur die Paare $(x,y)$ von $R$, deren Elemente in $A^{\prime }\times B^{\prime }$ liegen. Die reduzierte Relation heißt Einschränkung:

Konverse Relation Vorlage:Anker

Es ist auch möglich, eine Relation umzukehren. Eine solche umgekehrte Relation wird konverse oder auch inverse Relation genannt. Sie entsteht anschaulich dadurch, dass man alle Pfeile im Pfeildiagramm umdreht. Bezüglich der konversen Relation $R^{-1}$ steht $x$ genau dann in Relation zu $y$, wenn $y$ bezüglich der ursprünglichen Relation $R$ mit $x$ in Beziehung steht.

Bei der Definition des Urbildes haben wir gesagt, dass wir alle Elemente suchen, die in umgekehrter Richtung in Relation stehen. Dies war wenig intuitiv. Allerdings kann man sich das jetzt mithilfe der konversen Relation klar machen. Denn das Urbild einer Relation ist einfach das Bild der konversen Relation. Beschrieben ist es aber schon fast schwerer zu sehen als wenn man einfach die Definitionen hinschreibt und umformt:

Das Bild der konversen Relation ist $x{R}^{-1}=\{y\in B\mid (x,y)\in R^{-1}\}$. Das ist aber gemäß unserer bisherigen Definitionen die selbe Menge wie $\{y\in B|(y,x)\in R\}$ (hier haben wir die Definition der konversen Relation eingesetzt). Der letzte Ausdruck entspricht der Definition des Urbilds für $R$.

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}