Binäre Relation – „Mathe für Nicht-Freaks“

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.

Verständnisfrage: Welche der folgenden Relationen ist homogen und welche sind heterogen?

1. „Die Person $x$ liebt die Person $y$“
2. „Die natürliche Zahl $x$ ist kleiner als die rationale Zahl $y$“
3. „Die natürliche Zahl $x$ teilt die natürliche Zahl $y$“
4. „Die Personen $x$ und $y$ sind in derselben Klasse“
5. „Die Person $x$ studiert das Fach $y$“

Antwort:

1. homogen
2. heterogen
3. homogen
4. homogen
5. heterogen

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"

Verständnisfrage: Erstelle die Pfeildiagramme für folgende binäre Relationen auf der Grundmenge $\{1,2,3,4\}$

1. $x$ ist größer als $y$
2. $x$ ist ein Teiler von $y$
3. $x$ ergibt bei Division mit 2 denselben Rest wie $y$

• 
  Relation „$x$ ist größer als $y$“
• 
  Relation „$x$ ist ein Teiler von $y$“
• 
  Relation „$x$ ergibt bei Division mit 2 denselben Rest wie $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

Verständnisfrage: Erstelle die Relationsmatrizen für folgende binäre Relationen auf der Grundmenge $\{1,2,3,4\}$

1. $x$ ist größer als $y$
2. $x$ ist ein Teiler von $y$
3. $x$ ergibt bei Division mit 2 denselben Rest wie $y$

Relationsmatrix für die Relation „$x$ ist größer als $y$“ auf der Grundmenge $\{1,2,3,4\}$:

	1	2	3	4
1
2	X
3	X	X
4	X	X	X

Relationsmatrix für die Relation „$x$ ist ein Teiler von $y$“ auf der Grundmenge $\{1,2,3,4\}$:

	1	2	3	4
1	X	X	X	X
2		X		X
3			X
4				X

Relationsmatrix für die Relation „$x$ ergibt bei Division mit 2 denselben Rest wie $y$“ auf der Grundmenge $\{1,2,3,4\}$:

	1	2	3	4
1	X		X
2		X		X
3	X		X
4		X		X

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

Definition (Bildmenge eines Elements)

Zu einem $x\in A$ bezeichnet das Bild von $x$ unter $R$ die Menge aller $y\in B$, die mit $x$ in Relation stehen:

$xR:=\{y\in B\mid (x,y)\in R\}$

Verständnisfrage: Was ist $\text{Rhein}{R}_1$, also das Bild vom Rhein unter $R_1$

Es ist $\text{Rhein}{R}_1=\{\text{Deutschland, Niederlande}\}$.

Verständnisfrage: Sei $xRy\iff x=y^2$. Was ist $4R$?

Weil $4=2^2$ und $4=(-2{)}^2$ ist, ist $4R=\{2,-2\}$.

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.

Definition (Bildmenge einer Menge)

Zu $N\subseteq A$ bezeichnet das Bild von $N$ unter $R$ die Menge aller $y\in B$, die mit mindestens einem Element aus $N$ in Relation stehen:

$NR:=\{y\in B\mid \mathrm{\exists }x\in N:(x,y)\in R\}$

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

Definition (Urbildmenge)

Zu einem $y\in B$ bezeichnet das Urbild von $y$ unter $R\subset A\times B$ die Menge aller $x\in A$, die mit $y$ in umgekehrter Relation stehen:

$Ry:=\{x\in A\mid (x,y)\in R\}$

Verständnisfrage: Was ist $R_1\text{Deutschland}$?

$R_1\text{Deutschland}=\{\text{Donau, Elbe, Rhein}\}$.

Einschränkung einer Relation

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:

Definition (Einschränkung einer Relation)

Ist $A^{\prime }\subset A$ und $B^{\prime }\subset B$ so heißt $R^{\prime }:=\{x,y\in A^{\prime }\times B^{\prime }|xRy\}$ die Einschränkung von $R$ auf $A^{\prime }\times B^{\prime }$. Häufig wird die Einschränkung einer Relation $R$ ebenfalls mit $R$ bezeichnet.

Offensichtlich gilt $R^{\prime }\subseteq R$.

Beispiel (Einschränkung einer Relation)

$\le$ sei die Kleiner-Gleich-Relation auf den reellen Zahlen $ℝ$, also $\le \subseteq {ℝ}^2$.

Dann ist $\{x,y\in \mathbb{N}|x\le y\}$ die Kleiner-Gleich-Relation auf den natürlichen Zahlen $\mathbb{N}$ und $\{x,y\in \mathbb{Z}|x\le y\}$ die Kleiner-Gleich-Relation auf den ganzen Zahlen $\mathbb{Z}$.

Konverse Relation

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.

Definition (Konverse Relation)

Sei $R\subseteq A\times B$ eine Relation. Die konverse Relation $R^{-1}\subseteq B\times A$ kehrt alle Tupel aus $R$ um. Es ist genau dann $(y,x)\in R^{-1}$, wenn $(x,y)\in R$ ist.

Beispiel (Konverse Relationen)

Die Relation $W$ „$x$ ist ein Nachfolger von $y$“ hat die konverse Relation „$x$ ist ein Vorgänger von $y$“. Es ist beispielsweise $3W2$ (3 ist Nachfolger von 2). Damit ist $2W^{-1}3$ (2 ist Vorgänger von 3).

Ein weiteres Beispiel: Es gilt $2|8$ (2 teilt 8), also gilt für die Konverse $8{|}^{-1}2$. Konkret heißt das: $8$ ist ein Vielfaches von $2$.

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