Kurs:Mathematik (Osnabrück 2009-2011)/Teil I/Vorlesung 2

Hintereinanderschaltung und Umkehrabbildung

Lemma

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

$F\colon L\longrightarrow M$

eine Abbildung. Dann sind folgende Aussagen äquivalent.

1. ${}F$ ist bijektiv.
2. Es gibt eine Abbildung

   $G\colon M\longrightarrow L$

   mit

   $G\circ F=\operatorname {Id} _{L}{\text{ und }}F\circ G=\operatorname {Id} _{M}.$

3. Es gibt eine Abbildung ${}G\colon M\rightarrow L$ mit ${}G\circ F=\operatorname {Id} _{L}$ und es gibt eine Abbildung ${}H\colon M\rightarrow L$ mit ${}F\circ H=\operatorname {Id} _{M}$.

Beweis

(1) ${}\Rightarrow$ (2). Es sei also ${}F$ bijektiv und wir müssen eine Abbildung ${}G$ mit den angegebenen Eigenschaften finden. Wir behaupten, dass die Umkehrabbildung ${}F^{-1}$ diese Eigenschaften erfüllt. Für jedes ${}x\in L$ ist ${}{\left(F^{-1}\circ F\right)}(x)=F^{-1}(F(x))$. Das Element ${}x$ wird auf ${}F(x)$ abgebildet und es ist das einzige Element aus ${}L$ mit dieser Eigenschaft. Daher ist nach Definition der Umkehrabbildung ${}x=F^{-1}(F(x))$. Also ist ${}F^{-1}\circ F=\operatorname {Id} _{L}$.

Für jedes ${}y\in M$ ist ${}(F\circ F^{-1})(y)=F(F^{-1}(y))$. Nach der Definition von ${}F^{-1}$ ist ${}F^{-1}(y)$ dasjenige Element aus ${}L$, dass von ${}F$ auf ${}y$ abgebildet wird. Also ist ${}F(F^{-1}(y))=y$ und damit ist

${}F\circ F^{-1}=\operatorname {Id} _{M}\,.$

(2) ${}\Rightarrow$ (3) ist trivial, da das ${}G$ aus (2) sowohl die Eigenschaft von ${}G$ aus (3) als auch die Eigenschaft von ${}H$ aus (3) erfüllt.

(3) ${}\Rightarrow$ (1). Es gebe nun die Abbildungen ${}G$ und ${}H$ mit den beschriebenen Eigenschaften. Wir möchten zeigen, dass dann ${}F$ bijektiv ist, also sowohl injektiv als auch surjektiv ist. Zum Nachweis der Injektivität seien

$x,x'\in L{\text{ gegeben mit }}F(x)=F(x').$

Wir wenden darauf die Abbildung ${}G$ an und erhalten

${}G(F(x))=G(F(x'))\,.$

Da

${}G\circ F=\operatorname {Id} _{L}\,$

ist, folgt direkt ${}x=x'$.

Zum Nachweis der Surjektivität sei ${}y\in M$ beliebig vorgegeben. Wir behaupten, dass ${}H(y)\in L$ durch ${}F$ auf ${}y$ abgebildet wird. Dies folgt direkt aus

${}F(H(y))=\operatorname {Id} _{M}(y)=y\,.$

$\Box$

Relationen

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

Definition (Relation)

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 ${}xRy$ und sagt, dass „${}x$ in Relation ${}R$ zu ${}y$ steht“. Typische mathematische Relationen sind: ist gleich, ist größer als, ist Teilmenge von, ist disjunkt zu, usw.

Abbildungen kann man als spezielle Relationen auffassen.

Definition (Graph einer Abbildung)

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

$F\colon L\longrightarrow M$

eine Abbildung. Dann nennt man

${}\Gamma =\Gamma _{F}={\left\{(x,F(x))\mid x\in L\right\}}\subseteq L\times M\,$

den Graphen der Abbildung ${}F$.

Abbildungen und ihre Graphen sind im wesentlichen äquivalente Objekte. Formal kann man auch Abbildungen als Graphen (spezielle Relationen) einführen. Man muss den Graphen von seiner visuellen Realisierung unterscheiden, eine solche ist nicht immer möglich und hängt davon ab, ob man die Produktmenge aus Definitionsmenge und Wertemenge gut visualisieren kann.

Beispiel (Inzidenzrelation)

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){\text{ 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.

Relationen auf einer Menge

In den Beispielen oben hatten die beteiligten Mengen 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 einer 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 (Relation auf einer Menge)

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 ${}xRy,\,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.

Äquivalenzrelationen oder die Kunst des Identifizierens

Definition (Äquivalenzrelation)

Eine Äquivalenzrelation auf einer Menge ${}M$ ist eine Relation ${}R\subseteq M\times M$, die die folgenden drei Eigenschaften besitzt (für beliebige ${}x,y,z\in M$).

1. Es ist ${}x\sim x$ (reflexiv).
2. Aus ${}x\sim y$ folgt ${}y\sim x$ (symmetrisch).
3. Aus ${}x\sim y$ und ${}y\sim z$ folgt ${}x\sim z$ (transitiv).

Dabei bedeutet ${}x\sim y$, dass das Paar ${}(x,y)$ zu ${}R$ gehört.

Bei einer Äquivalenzrelation ${}R$ sagt man, dass ${}x$ und ${}y$ zueinander äquivalent sind, wenn ${}xRy$ gilt.

Beispiel (Gleichheit)

Das Urbeispiel für eine Äquivalenzrelation ist die Gleichheit auf einer beliebigen Menge ${}M$. Unter der Gleichheit ist jedes Element nur mit sich selbst äquivalent.

Beispiel

Es seien ${}M$ und ${}N$ Mengen und sei ${}f\colon M\rightarrow N$ eine Abbildung. In einer solchen Situation hat man immer eine Äquivalenzrelation auf dem Definitionsbereich ${}M$ der Abbildung, und zwar erklärt man zwei Elemente ${}x,y\in M$ als äquivalent, wenn sie unter ${}f$ auf das gleiche Element abgebildet werden, wenn also ${}f(x)=f(y)$ ist. Wenn die Abbildung ${}f$ injektiv ist, so ist die durch ${}f$ auf ${}M$ definierte Äquivalenzrelation die Gleichheit. Wenn die Abbildung konstant ist, so sind unter der zugehörigen Äquivalenzrelation alle Elemente aus ${}M$ untereinander äquivalent.

Beispiel

Visualisierung des Beispiels. Die Äquivalenzklassen bekommen verschiedene Farben.

Wir betrachten die Produktmenge ${}M=\mathbb {N} \times \mathbb {N}$, die wir uns als ein Punktgitter vorstellen. Wir fixieren die Sprünge (man denke an Springmäuse, die alle diese Sprünge ausführen können)

$\pm (2,0)\,\,{\text{ und }}\,\,\pm (3,3),$

und sagen, dass zwei Punkte ${}P=(a,b),\,Q=(c,d)\in M$ äquivalent sind, wenn man ausgehend von ${}P$ den Punkt ${}Q$ mit einer Folge von solchen Sprüngen erreichen kann. Dies ist eine Äquivalenzrelation (dafür ist entscheidend, dass bei den Sprüngen auch der entgegengesetzte Sprung dazu gehört). Typische Fragestellungen sind: Wie kann man äquivalente Felder charakterisieren, wie entscheiden, ob zwei Felder äquivalent sind oder nicht? Wie viele Äquivalenzklassen gibt es überhaupt, gibt es für sie ein schönes Repräsentantensystem?

Unter der Äquivalenzrelation „erreichbar auf dem Landweg“ sind Inseln und Kontinente die Äquivalenzklassen.

Beispiel (Symmetrische Erreichbarkeitsrelation)

Es sei eine Situation gegeben, wo gewisse Orte (oder Objekte) von gewissen anderen Orten aus erreichbar sind oder nicht. Die Erreichbarkeit kann dabei durch die Wahl eines Verkehrsmittels oder durch eine abstraktere (Bewegungs)-Vorschrift festgelegt sein. Solche Erreichbarkeitsrelationen liefern häufig eine Äquivalenzrelation. Dass ein Ort von sich selbst aus erreichbar ist, sichert die Reflexivität. Die Symmetrie der Erreichbarkeit besagt, dass wenn man von ${}A$ nach ${}B$ kommen kann, dass man dann auch von ${}B$ nach ${}A$ kommen kann. Das ist nicht für jede Erreichbarkeit selbstverständlich, für die meisten aber schon. Die Transitivität gilt immer dann, wenn man die Bewegungsvorgänge hintereinander ausführen kann, also zuerst von ${}A$ nach ${}B$ und dann von ${}B$ nach ${}C$.

Wenn erreichbar beispielsweise dadurch gegeben ist, dass man auf dem Landweg von einem Ort zu einem anderen kommen kann, so sind zwei Ortspunkte genau dann äquivalent, wenn sie auf der gleichen Insel (oder dem gleichen Kontinent) liegen. Inseln und Kontinente sind dann die Äquivalenzklassen. In der Topologie spielt der Begriff des Wegzusammenhangs eine wichtige Rolle: Zwei Punkte sind wegzusammenhängend, wenn man sie durch einen stetigen Weg verbinden kann. Oder: Auf den ganzen Zahlen lebe eine Kolonie von Flöhen, und jeder Flohsprung geht fünf Einheiten weit (in beide Richtungen). Wie viele Flohpopulationen gibt es, welche Flöhe können sich begegnen?

Äquivalenzklassen, Quotientenmenge, Identifizierungsabbildung

Beispiel

In der Wohnung liegt eine große Menge von Wäsche herum, die gewaschen werden soll. Natürlich kann nicht alles in den gleichen Waschgang, sondern nur Sachen, die sowohl gleichfarbig sind als auch die gleiche Waschtemperatur vertragen. Dies definiert insgesamt die Äquivalenzrelation der Waschgangverträglichkeit. Man kann jetzt die Wäsche dadurch sortieren, dass man waschgangverträgliche Sachen jeweils zu einem Haufen zusammenfasst. So entstehen verschiedene Haufen, die jeweils aus untereinander waschgangverträglichen Sachen bestehen, und zwei Sachen landen genau dann auf dem gleichen Haufen, wenn sie waschgangverträglich sind. Eine wichtige Beobachtung dabei ist, dass die Haufen nicht anhand einer vorgegebenen Liste (Menge) von möglichen Waschkombinationen entstehen, sondern allein durch die Verträglichkeitsüberprüfung der Objekte untereinander.

Für den weiteren Ablauf (beispielsweise in welcher Reihenfolge gewaschen wird) kommt es auf die Einzelsachen nicht mehr an, sondern nur noch auf die einzelnen Haufen. Es ist daher sinnvoll, die entstandene Situation dadurch zu erfassen, dass man die Menge der Haufen bildet. Jeder Haufen wird zu genau einem Element in dieser Haufenmenge. Das Sortieren kann man dann auffassen als eine Abbildung von der Wäschemenge in die Haufenmenge, wobei jedem Wäschestück der zugehörige Haufen zugeordnet wird. Bei diesem Übergang werden waschgangverträgliche Sachen miteinander identifiziert.

Definition (Äquivalenzklasse)

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation und ${}x\in M$. Dann ist

${}[x]:={\left\{y\in M\mid (x,y)\in R\right\}}\,$

die Äquivalenzklasse von ${}x$ bezüglich ${}R$.

Definition (Quotientenmenge)

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation. Dann heißt

${}M/R:={\left\{[x]\mid x\in M\right\}}\,$

die Quotientenmenge von ${}R$.

Definition (Identifizierungsabbildung)

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation und ${}M/R$ die Quotientenmenge. Die Abbildung

$q_{R}\colon M\longrightarrow M/R,\,x\longmapsto [x],$

heißt kanonische Projektion  (oder Identifizierungsabbildung) von ${}R$.

In der Sprache der Identifizierungen heißt dies: ${}[x]$ ist die Teilmenge aller Elemente von ${}M$, die zu ${}x$ äquivalent sind. Zwei Elemente sind genau dann zu identifizieren, wenn sie der gleichen Äquivalenzklasse angehören. Die Quotientenmenge besteht aus den verschiedenen Äquivalenzklassen, d.h. die Elemente in der Quotientenmenge stehen für die möglichen Werte (Haufen, Schubladen, Klassen, Kategorien) unter der Identifizierung. Die Identifizierungsabbildung ordnet jedem Element die Klasse zu, zu der es gemäß der Identifizierung gehört. Dies wird präzisiert durch die folgende Aussage.

Lemma

Es sei ${}M$ eine Menge und ${}\sim$ eine Äquivalenzrelation auf ${}M$ mit den Äquivalenzklassen ${}[x]$, ${}x\in M$, und der Quotientenmenge ${}M/\sim$. Dann gelten folgende Aussagen.

1. Es ist ${}x\sim y$ genau dann, wenn ${}[x]=[y]$ ist, und dies gilt genau dann, wenn ${}[x]\cap [y]\neq \emptyset$.
2. Die Identifikationsabbildung

   $q\colon M\longrightarrow M/\sim ,\,x\longmapsto [x],$

   ist surjektiv.
3. Es ist ${}q^{-1}(\{[x]\})=[x]$.

Beweis

1. Seien ${}x$ und ${}y$ äquivalent und ${}u\in [x]$. Dann ist ${}x\sim u$ und nach der Transitivität auch ${}y\sim u$, also ${}u\in [y]$. Damit stimmen die Äquivalenzklasssen überein. Die Implikation von der Mitte nach rechts ist klar, da wegen ${}x\sim x$ Äquivalenzklassen nicht leer sind. Es sei nun ${}[x]\cap [y]\neq \emptyset$, und sei ${}z$ ein Element im Durchschnitt. Dann ist ${}x\sim z$ und ${}y\sim z$ und wegen der Transitivität ist ${}x\sim y$.
2. Die Surjektivität ist klar aufgrund der Definition der Quotientenmenge, und da ${}x$ auf die Klasse ${}[x]$ geschickt wird.
3. Es ist

   ${}q^{-1}(\{[x]\})={\left\{y\in M\mid q(y)=[x]\right\}}={\left\{y\in M\mid [y]=[x]\right\}}={\left\{y\in M\mid y\sim x\right\}}=[x]\,.$

$\Box$

Fußnoten

<< | Kurs:Mathematik (Osnabrück 2009-2011)/Teil I | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)