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

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

Homogene und heterogene RelationenBearbeiten

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 RelationenBearbeiten

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  .

PfeildiagrammBearbeiten

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:

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

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  

RelationsmatrixBearbeiten

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 BegriffeBearbeiten

BildmengeBearbeiten

 
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:

 

UrbildBearbeiten

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  .