Kurs:Lineare Algebra (Osnabrück 2017-2018)/Teil II/Anhang/Relationen



Relationen

Sei eine Menge von Personen und eine Menge von Eigenschaften, die eine Person haben kann oder auch nicht, und zwar sollen hier nur solche Eigenschaften betrachtet werden, wo es nur die beiden Möglichkeiten des Zukommens oder des Nichtzukommens gibt. Die Gesamtinformation, welche der beteiligten Personen welche Eigenschaft besitzt, kann man dann auf verschiedene Arten ausdrücken. Man kann beispielsweise eine Liste von allen zutreffenden Person-Eigenschafts-Paaren erstellen, also

(Anna, klug), (Hans, schön), (Berta, schön), (Hans, lustig), (Anna, lustig)

oder man kann zu jeder Person die ihr zukommenden Eigenschaften auflisten, also

Anna: klug, lustig
Berta: schön
Hans: schön, lustig

oder umgekehrt zu einer Eigenschaft die Personen auflisten, die diese Eigenschaft erfüllen, also

Schön: Berta, Hans
Klug: Anna
Lustig: Anna, Hans

Man kann auch das ganze in eine Tabelle schreiben, wo die eine Leiste die Personen und die andere Leiste die Eigenschaften repräsentiert, und dann diejenigen Kreuzungspunkte, die eine zutreffende Beziehung repräsentieren, ankreuzen, also

Anna Berta Hans
Schön x x
Klug x
Lustig x x

Eine weitere Möglichkeit besteht darin, die Information durch ein Verbindungsdiagramm auszudrücken, bei dem Person und Eigenschaft genau dann durch eine Strecke oder eine Kurve verbunden werden, wenn die Eigenschaft zutrifft.

Der mathematische Begriff, um Beziehungen zwischen den Elementen von zwei Mengen zu beschreiben, heißt Relation.


Definition  

Es seien und Mengen. Eine Relation zwischen den Mengen und ist eine Teilmenge der Produktmenge , also .

Statt schreibt man häufig auch oder und sagt, dass „ in Relation zu steht“. Typische mathematische Relationen sind: ist gleich, ist größer als, ist Element von, ist Teilmenge von, ist disjunkt zu, usw.

Wenn eine Relation ist, so heißt für jedes die Menge

die Faser durch und für jedes heißt die Menge

die Faser durch .


Beispiel  

Wir betrachten auf einer Auswahl von Speisen und Getränken die Relation, die angibt, ob ein Gericht zu einem Getränk passt. Sei

und

Wasser passt zu allen Gerichten, Kamillentee zu keinem der Gerichte. Rotwein passt zu Nudeln und Kartoffelgratin, aber nicht zu Hecht oder zu Zupfkuchen. Heiße Schokolade und Kaffee passt zu Zupfkuchen, nicht zu den anderen Gerichten.



Beispiel  

Es sei die Menge der Städte und die Menge der Autobahnen. Dann ist die Beziehung „liegt an“ eine Relation zwischen und . Zwischen einer Stadt und einer Autobahn bedeutet

einfach, dass die konkrete Stadt an der Autobahn liegt. Zu ist dann die Menge

die Menge der Autobahnen, an denen liegt, und zu ist

die Teilmenge der Städte, an denen die Autobahn vorbeifährt. Für ergibt sich also

und für die ergibt sich

Diese Relation wird vollständig beschrieben, wenn man zu jeder Stadt die daran vorbeiführenden Autobahnen oder aber wenn man zu jeder Autobahn die daran liegenden Städte aufführt. Genauso gut kann man die Relation durch eine Tabelle ausdrücken mit einer Leitzeile für die Autobahnen und einer Leitspalte für die Städte, und wo im Kreuzungspunkt ein Kreuz gemacht wird genau dann, wenn gilt. Die Aussage

bedeutet, dass jede Stadt an einer Autobahn liegt (wohl falsch) und die Aussage

bedeutet, dass jede Autobahn an mindestens einer Stadt vorbeiführt (wohl wahr).



Beispiel  

Es sei die reelle Ebene und die Menge aller Geraden in der Ebene. Die Produktmenge

besteht aus allen Paaren , wobei ein Punkt der Ebene und eine Gerade ist. Es gibt mehrere Möglichkeiten, eine Gerade zu beschreiben, und damit auch mehrere Möglichkeiten, ein solches Paar zu beschreiben. Beispielsweise ist

ein Paar, wobei der Punkt vorne durch die beiden Koordinaten und die Gerade hinten durch eine Geradengleichung angegeben wird. Bei einem solchen Paar besteht keine Bedingung zwischen dem Punkt und der Geraden.

Die Inzidenzrelation zwischen Punkten und Geraden wird ausgedrückt durch

Statt „liegt auf“ kann man auch einfach schreiben.



Beispiel  

Es sei eine Menge und die Potenzmenge von . Dann wird auf die Inzidenzrelation erklärt durch

Die Inzidenzrelation drückt also aus, ob ein Element zu einer bestimmten Teilmenge gehört oder nicht. Die Faser zu einem Element besteht aus sämtlichen Teilmengen, die dieses Element enthalten, und die Faser zu einer Teilmenge besteht aus allen Elementen dieser Teilmenge.




Relationen auf einer Menge

Im obigen Beispiel gab es einerseits Personen und andererseits Eigenschaften, die diese Personen haben konnten oder nicht. Die beiden beteiligten Mengen hatten also eine unterschiedliche Funktion. Wenn man aber z.B. zwischenmenschliche Beziehungen ausdrücken möchte, so stimmen die beiden Mengen überein, und es ergeben sich neuartige strukturelle Möglichkeiten, da ein Element sowohl vorne als auch hinten stehen kann. Betrachten wir in der studentischen Dreier-WG die Relation „kann gut leiden“. Die zugehörige Relationstabelle sieht vielleicht so aus.

Anna Berta Hans
Anna x x
Berta x x
Hans x x x

Hier ist zunächst wichtig, die Bedeutung der Spalte und der Zeile festzulegen; sagen wir, dass die Tabelle so zu verstehen ist, dass in der Leitspalte das grammatische Subjekt und in der Leitzeile das grammatische Objekt steht. Damit besagt die Tabelle, dass Hans alle Personen der WG gut leiden kann, dass Berta sich und Anna gut leiden kann, aber nicht Hans, und dass Anna ihre beiden Mitbewohner gut leiden kann, aber nicht sich selbst. Die Relation ist also weder „reflexiv“, da sich Anna nicht gut leiden kann, noch „symmetrisch“, da Hans zwar Berta gut leiden kann, aber nicht umgekehrt.

Ein Pfeildiagramm ist eine Möglichkeit, eine Relation darzustellen.


Definition  

Eine Relation auf einer Menge ist eine Teilmenge der Produktmenge , also .

Wenn ein Paar zu gehört, so sagt man auch, dass und in der Relation stehen. Statt verwendet man häufig suggestivere Schreibweisen wie oder . Dabei werden manche Symbole nur verwendet, wenn die Relation gewisse zusätzliche Eigenschaften erfüllt. Die wichtigsten Eigenschaften fasst die folgende Definition zusammen (die bei zwei verschiedenen Mengen keinen Sinn ergeben).


Definition  

Es sei eine Menge und eine Relation auf . Man nennt

    • reflexiv, wenn

    gilt für alle .

    • transitiv, wenn für beliebige

    aus und aus stets folgt.

    • symmetrisch, wenn für beliebige

    aus auch folgt.

    • antisymmetrisch, wenn für beliebige

    aus und die Gleichheit folgt.

    Wir besprechen nun verschiedene mathematische Relationen, die mit diesen Eigenschaften definiert werden können.



    Ordnungsrelationen

    Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie verwendet.


    Definition  

    Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

    1. Es ist für alle .
    2. Aus und folgt stets .
    3. Aus und folgt .

    Eine Menge mit einer fixierten Ordnung darauf heißt geordnete Menge. Wenn zusätzlich gilt, dass für je zwei Elemente oder gilt, so spricht man von einer total geordneten Menge.


    Beispiel  

    Die reellen Zahlen (ebenso die rationalen Zahlen und die ganzen Zahlen) sind total geordnet durch die Größergleichrelation . Dies gehört zum Begriff des angeordneten Körpers, der nicht nur verlangt, dass eine totale Ordnung erklärt ist, sondern auch, dass diese mit den algebraischen Operationen verträglich ist. Die strikte Größerrelation ist keine Ordnungsrelation, da sie nicht reflexiv ist. Der Körper der komplexen Zahlen ist nicht angeordnet (und lässt sich auch nicht anordnen).



    Beispiel  

    Wir betrachten die positiven ganzen Zahlen zusammen mit der Teilbarkeitsbeziehung. Man sagt, dass eine Zahl die Zahl teilt, geschrieben

    wenn es eine weitere natürliche Zahl mit

    gibt. Die Bezeichnung ist nicht sonderlich glücklich gewählt, da ein symmetrisches Symbol für eine nichtsymmetrische Relation verwendet wird. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ist, wie zeigt. Die Transitivität sieht man so: sei und mit und . Dann ist und daher . Die Antisymmetrie folgt so: Aus und folgt . Da wir uns auf positive natürliche Zahlen beschränken, folgt und daraus . Also ist Einfache Beispiele wie und zeigen, dass hier keine totale Ordnung vorliegt, da weder von noch umgekehrt geteilt wird.



    Beispiel  

    Es sei eine beliebige Menge und die Potenzmenge davon. Dann sind die Elemente aus - also die Teilmengen von - durch die Inklusionsbeziehung geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus und die Inklusion folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen sind genau dann gleich, wenn und umgekehrt gilt.