Zum Inhalt springen

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

Aus Wikibooks

Binäre Relationen sind zweistellige Relationen, also Teilmengen des kartesischen Produkts der Mengen und .

Homogene und heterogene Relationen

[Bearbeiten]

Eine binäre Relation heißt homogen, wenn die Mengen und identisch sind. Im Fall nennt man die Relation 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 liebt die Person
  2. „Die natürliche Zahl ist kleiner als die rationale Zahl
  3. „Die natürliche Zahl teilt die natürliche Zahl
  4. „Die Personen und sind in derselben Klasse“
  5. „Die Person studiert das Fach

Antwort:

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

Darstellung endlicher binärer Relationen

[Bearbeiten]

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 : „Der Fluss fließt im Land “, wobei ein Fluss der Menge und ein Land der Menge ist.
  • homogene Relation : „ ist ein Nachfolger von “ auf der Grundmenge .

Pfeildiagramm

[Bearbeiten]

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 „Der Fluss fließt im Land “ im Pfeildiagramm so aus:

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

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

Pfeildiagramm der Relation "x ist eine Nachfolger von y"
Pfeildiagramm der Relation "x ist eine Nachfolger von y"

Verständnisfrage: Erstelle die Pfeildiagramme für folgende binäre Relationen auf der Grundmenge

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

Relationsmatrix

[Bearbeiten]

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 „Der Fluss fließt im Land “ sieht als Relationsmatrix so aus:

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

Die Relationsmatrix der Relation ist ein Nachfolger von “ auf der Menge 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 n
1 Haupt-
2 dia-
3 gona-
n le

Verständnisfrage: Erstelle die Relationsmatrizen für folgende binäre Relationen auf der Grundmenge

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

Relationsmatrix für die Relation „ ist größer als “ auf der Grundmenge :

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

Relationsmatrix für die Relation „ ist ein Teiler von “ auf der Grundmenge :

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

Relationsmatrix für die Relation „ ergibt bei Division mit 2 denselben Rest wie “ auf der Grundmenge :

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

Wichtige Begriffe

[Bearbeiten]

Bildmenge

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

Wir betrachten nochmals die Relation „Der Fluss fließt im Land “. 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 aus der Grundmenge alle Elemente heraussuchen, die mit in Relation stehen. Diese Menge wird als Bildmenge oder als das Bild von bezeichnet. Für das Bild von unter der Relation schreibt man . Der Ausdruck bezeichnet also die Menge aller Elemente, die mit in Relation stehen. Er ist eigentlich recht intuitiv, denn ist die Menge aller , die nach dem stehen können, wo also 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 genau ein mit 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 eine binäre Relation zwischen den Mengen und .

Definition (Bildmenge eines Elements)

Zu einem bezeichnet das Bild von unter die Menge aller , die mit in Relation stehen:

Verständnisfrage: Was ist , also das Bild vom Rhein unter

Es ist .

Verständnisfrage: Sei . Was ist ?

Weil und ist, ist .

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 . 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 bezeichnet das Bild von unter die Menge aller , die mit mindestens einem Element aus in Relation stehen:

Urbild

[Bearbeiten]

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 schreibt man . Dabei ist die Menge aller Objekte die vor stehen können, also die Menge aller mit .

Definition (Urbildmenge)

Zu einem bezeichnet das Urbild von unter die Menge aller , die mit in umgekehrter Relation stehen:

Verständnisfrage: Was ist ?

.

Einschränkung einer Relation

[Bearbeiten]

Ist eine Relation auf , so lässt sich diese auf eine Teilmenge reduzieren. Die so entstehende Relation enthält nur die Paare von , deren Elemente in liegen. Die reduzierte Relation heißt Einschränkung:

Definition (Einschränkung einer Relation)

Ist und so heißt die Einschränkung von auf . Häufig wird die Einschränkung einer Relation ebenfalls mit bezeichnet.

Offensichtlich gilt .

Beispiel (Einschränkung einer Relation)

sei die Kleiner-Gleich-Relation auf den reellen Zahlen , also .

Dann ist die Kleiner-Gleich-Relation auf den natürlichen Zahlen und die Kleiner-Gleich-Relation auf den ganzen Zahlen .

Konverse Relation

[Bearbeiten]

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 steht genau dann in Relation zu , wenn bezüglich der ursprünglichen Relation mit in Beziehung steht.

Definition (Konverse Relation)

Sei eine Relation. Die konverse Relation kehrt alle Tupel aus um. Es ist genau dann , wenn ist.

Beispiel (Konverse Relationen)

Die Relation ist ein Nachfolger von “ hat die konverse Relation „ ist ein Vorgänger von “. Es ist beispielsweise (3 ist Nachfolger von 2). Damit ist (2 ist Vorgänger von 3).

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

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 . Das ist aber gemäß unserer bisherigen Definitionen die selbe Menge wie (hier haben wir die Definition der konversen Relation eingesetzt). Der letzte Ausdruck entspricht der Definition des Urbilds für .