Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil II/Vorlesung 37

Relationen

Es sei $P$ eine Menge von Personen und $E$ 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 das Ganze auch in eine Tabelle schreiben, wo die eine Leiste die Personen und die andere Leiste die Eigenschaften repräsentieren, 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 eine Person und eine Eigenschaft genau dann durch eine Strecke oder eine Kurve verbunden werden, wenn die Eigenschaft auf die Person zutrifft.

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

Definition

Es seien $M$ und $N$ Mengen. Eine Relation $R$ zwischen den Mengen $M$ und $N$ ist eine Teilmenge der Produktmenge $M \times N$ , also $R \subseteq M \times N$ .

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

Wenn $R \subseteq M \times N$ eine Relation ist, so heißt für jedes $m \in M$ die Menge

N_{m} = {y \in N ∣ R (m, y)}

die Faser durch $m$ und für jedes $n \in N$ heißt die Menge

M_{n} = {x \in M ∣ R (x, n)}

die Faser durch $n$ .

Beispiel

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

E = {Hecht, Nudeln, Kartoffelgratin, Zupfkuchen}

und

G = {Rotwein, heiße Schokolade, Wasser, Kamillentee, Kaffee} .

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 passen zu Zupfkuchen, aber nicht zu den anderen Gerichten.

Beispiel

Es sei $S$ die Menge der Städte und $A$ die Menge der Autobahnen. Dann ist die Beziehung „liegt an“ eine Relation $L$ zwischen $S$ und $A$ . Zwischen einer Stadt $s \in S$ und einer Autobahn $a \in A$ bedeutet

s L a oder L (s, a)

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

A_{s} = {a \in A ∣ L (s, a)}

die Menge der Autobahnen, an denen $s$ liegt, und zu $a \in A$ ist

S_{a} = {s \in S ∣ L (s, a)}

die Teilmenge der Städte, an denen die Autobahn $a$ vorbeifährt. Für $s = Osnabr \ddot{u} ck$ ergibt sich also

A_{Osnabr \ddot{u} ck} = {A 1, A 30, A 33}

und für die $A 1$ ergibt sich

S_{A 1} = {\dots, Hamburg, Bremen, Osnabr \ddot{u} ck, \dots} .

Diese Relation wird vollständig beschrieben, wenn man zu jeder Stadt die daran vorbeiführenden Autobahnen oder 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 $(s, a)$ genau dann ein Kreuz gemacht wird, wenn $L (s, a)$ gilt. Die Aussage

\forall s (\exists a L (s, a))

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

\forall a (\exists s L (s, a))

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

Beispiel

Es sei $E = ℝ^{2}$ die reelle Ebene und $G$ die Menge aller Geraden in der Ebene. Die Produktmenge

E \times G

besteht aus allen Paaren $(P, g)$ , wobei $P$ ein Punkt der Ebene und $g$ 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

((2, - 5), {(u, v) ∣ 4 u - 3 v = 6})

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

I = {(P, g) \in E \times G ∣ P liegt auf g} .

Statt „liegt auf“ kann man auch einfach $P \in g$ schreiben.

Beispiel

Es sei $M$ eine Menge und $P$ die Potenzmenge von $M$ . Dann wird auf $M \times P$ die Inzidenzrelation $I$ erklärt durch

I (x, T) genau dann, wenn x \in T .

Die Inzidenzrelation drückt also aus, ob ein Element $x$ zu einer bestimmten Teilmenge $T$ 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 und Abbildungen

Abbildungen kann man als spezielle Relationen auffassen.

Definition

Es seien $L$ und $M$ Mengen und es sei

F : L ⟶ M

eine Abbildung. Dann nennt man

Γ = Γ_{F} = {(x, F (x)) ∣ x \in L} \subseteq L \times M

den Graphen der Abbildung $F$ .

Abbildungen und ihre Graphen sind im wesentlichen äquivalente Objekte. Um Abbildungen innerhalb der Relationen herauszustellen, sind die folgenden Begriffsbildungen sinnvoll (die Begriffe sind sinnvoll, ob die gewählten Bezeichnungen sinnvoll sind, ist eine andere Frage).

Definition

Eine Relation $R \subseteq M \times N$ heißt linkseindeutig, wenn es zu jedem $y \in N$ maximal ein $x \in M$ mit $(x, y) \in R$ gibt.

Definition

Eine Relation $R \subseteq M \times N$ heißt rechtseindeutig, wenn es zu jedem $x \in M$ maximal ein $y \in N$ mit $(x, y) \in R$ gibt.

Definition

Eine Relation $R \subseteq M \times N$ heißt linksvollständig, wenn es zu jedem $x \in M$ ein $y \in N$ mit $(x, y) \in R$ gibt.

Definition

Eine Relation $R \subseteq M \times N$ heißt rechtsvollständig, wenn es zu jedem $y \in N$ ein $x \in M$ mit $(x, y) \in R$ gibt.

Wenn ein Paar $(x, y) \in R$ gegeben ist, so meint rechtseindeutig, dass (bei gegebenem) $x$ die rechte Seite, also das $y$ , eindeutig bestimmt ist. Wenn man sich aber die Relation auf $M \times N$ dadurch gegeben denkt, dass zwischen den Elementen der linken Menge $M$ und den Elementen der rechten Menge $N$ genau dann eine verbindende Strecke (kein Pfeil) vorliegt, wenn das entsprechende Paar zu $R$ gehört, so hat rechtseindeutig die Auswirkung, dass von jedem Punkt der linken Seite (!) aus maximal eine Verbindungsstrecke abgeht.

Lemma

Eine Relation $R \subseteq M \times N$

ist genau dann eine (der Graph einer) Abbildung, wenn sie linksvollständig und rechtseindeutig ist.

Beweis

Eine Abbildung

φ : M ⟶ N

ordnet jedem $x \in M$ genau ein $y \in N$ zu, das ist nach Definition die Linksvollständigkeit und die Rechtseindeutigkeit.

◻

Eine rechtseindeutige Relation, die nicht unbedingt linksvollständig ist, nennt man auch manchmal eine „partielle Abbildung“, eine (insbesondere linksvollständige) Relation nennt man manchmal auch eine „mehrdeutige Abbildung“.

Bemerkung

Eine Abbildung $f : M \to N$ ist genau dann surjektiv, wenn der Graph der Abbildung (als Relation aufgefasst) rechtsvollständig ist, und genau dann injektiv, wenn der Graph linkseindeutig ist.

Relationen auf einer Menge

Im eingangs erwähnten 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 häufig ü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.

Definition

Eine Relation $R$ auf einer Menge $M$ ist eine Teilmenge der Produktmenge $M \times M$ , also $R \subseteq M \times M$ .

Wenn ein Paar $(x, y)$ zu $R$ gehört, so sagt man auch, dass $x$ und $y$ in der Relation $R$ stehen. Statt $(x, y) \in R$ verwendet man häufig suggestivere Schreibweisen wie $x R y, x \sim y$ oder $x \leq y$ . 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 $M$ eine Menge und $R \subseteq M \times M$ eine Relation auf $M$ . Man nennt $R$

reflexiv, wenn

$(x, x) \in R$ gilt für alle $x \in M$ .

transitiv, wenn für beliebige

$x, y, z \in M$ aus $(x, y) \in R$ und aus $(y, z) \in R$ stets $(x, z) \in R$ folgt.

symmetrisch, wenn für beliebige

$x, y \in M$ aus $(x, y) \in R$ auch $(y, x) \in R$ folgt.

antisymmetrisch, wenn für beliebige

$x, y \in M$ aus $(x, y) \in R$ und $(y, x) \in R$ die Gleichheit $x = y$ folgt.

Eine wichtige Darstellungsmöglichkeit für eine Relation auf einer Menge ist durch ein Pfeildiagramm gegeben, man spricht auch von einem gerichteten Graphen. Dabei werden die Elemente der Grundmenge $M$ als Punkte (Knoten) gezeichnet, und es wird genau dann ein Pfeil von Punkt $x$ zu Punkt $y$ gezeichnet, wenn $x R y$ gilt. Die Richtung des Pfeiles ist dabei wichtig. Wenn allerdings die Relation symmetrisch ist, so gibt es zu jedem Pfeil den entsprechenden Rückpfeil. Daher drückt man symmetrische Relationen direkt durch ungerichtete Pfeile (Kanten, Verbindungsstrecken) aus und spricht von ungerichteten Graphen.

Beispiel

Eine (Fußball-)Spielgruppe bei einer Europa- oder Weltmeisterschaft besteht aus vier Mannschaften, und jede spielt gegen jede. Ein Spiel kann unentschieden oder mit einem Sieg für eine der beiden Mannschaften enden. Wir interessieren uns für die Gewinnrelation in einer Spielgruppe, die man durch einen gerichteten Graphen beschreiben kann, wobei man einen Sieg von $A$ über $B$ durch einen Pfeil von $A$ nach $B$ (und ein Unentschieden durch keine Verbindung) ausdrücken kann.

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 $\geq, \leq, ≼, \subseteq$ verwendet. Diese haben wir schon im Kontext von angeordneten Ringen besprochen.

Definition

Eine Relation $≼$ auf einer Menge $I$ heißt Ordnungsrelation oder Ordnung, wenn die drei folgenden Bedingungen erfüllt sind.

Es ist $i ≼ i$ für alle $i \in I$ .
Aus $i ≼ j$ und $j ≼ k$ folgt stets $i ≼ k$ .
Aus $i ≼ j$ und $j ≼ i$ folgt $i = j$ .

Eine Menge mit einer fixierten Ordnung darauf heißt geordnete Menge. Wenn zusätzlich gilt, dass für je zwei Elemente $x \leq y$ oder $y \leq x$ 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 $\geq$ . 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 $k$ die Zahl $n$ teilt, geschrieben

k ∣ n,

wenn es eine weitere natürliche Zahl

m

mit

$n = k m$ 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 $n ∣ n$ ist, wie $m = 1$ zeigt. Die Transitivität sieht man so: sei $k ∣ n$ und $n ∣ m$ mit $n = a k$ und $m = b n$ . Dann ist $m = b n = b a k$ und daher $k ∣ m$ . Die Antisymmetrie folgt so: Aus $n = a k$ und $k = b n$ folgt $n = (a b) n$ . Da wir uns auf positive natürliche Zahlen beschränken, folgt $a b = 1$ und daraus $a = b = 1$ . Also ist $k = n$ Einfache Beispiele wie $2$ und $3$ zeigen, dass hier keine totale Ordnung vorliegt, da weder $2$ von $3$ noch umgekehrt geteilt wird.

Beispiel

Es sei $M$ eine beliebige Menge und $R = 𝔓 (M)$ die Potenzmenge davon. Dann sind die Elemente aus $R = 𝔓 (M)$ - also die Teilmengen von $M$ - durch die Inklusionsbeziehung $\subseteq$ geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus $T_{1} \subseteq T_{2}$ und $T_{2} \subseteq T_{3}$ die Inklusion $T_{1} \subseteq T_{3}$ folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen $T_{1}, T_{2}$ sind genau dann gleich, wenn $T_{1} \subseteq T_{2}$ und umgekehrt $T_{2} \subseteq T_{1}$ gilt.

Beispiel

Es sei $X$ eine Menge (beispielsweise ein reelles Intervall, oder ein topologischer Raum), so ist die Menge der (stetigen) Funktionen $f : X \to ℝ$ geordnet, indem man $f \geq g$ dadurch definiert, dass $f (x) \geq g (x)$ für jeden Punkt $x \in X$ sein muss. Dies ist offensichtlich keine totale Ordnung.

<< | Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil II | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)