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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Hintereinanderschaltung und Umkehrabbildung



Lemma  

Es seien und Mengen und es sei

eine Abbildung. Dann sind folgende Aussagen äquivalent.

  1. ist bijektiv.
  2. Es gibt eine Abbildung
    mit
  3. Es gibt eine Abbildung mit und es gibt eine Abbildung mit .

Beweis  

(1) (2). Es sei also bijektiv und wir müssen eine Abbildung mit den angegebenen Eigenschaften finden. Wir behaupten, dass die Umkehrabbildung diese Eigenschaften erfüllt. Für jedes ist . Das Element wird auf abgebildet und es ist das einzige Element aus mit dieser Eigenschaft. Daher ist nach Definition der Umkehrabbildung . Also ist .

Für jedes ist . Nach der Definition von ist dasjenige Element aus , dass von auf abgebildet wird. Also ist und damit ist .

(2) (3) ist trivial,[1] da das aus (2) sowohl die Eigenschaft von aus (3) als auch die Eigenschaft von aus (3) erfüllt.

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

Wir wenden darauf[2] die Abbildung an und erhalten

Da ist, folgt direkt .

Zum Nachweis der Surjektivität sei beliebig vorgegeben. Wir behaupten, dass durch auf abgebildet wird. Dies folgt direkt aus




Relationen

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


Definition (Relation)  

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 Teilmenge von, ist disjunkt zu, usw.

Abbildungen kann man als spezielle Relationen auffassen.


Definition (Graph einer Abbildung)  

Es seien und Mengen und es sei

eine Abbildung. Dann nennt man

den Graphen der Abbildung .

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 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.




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 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  

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.



    Äquivalenzrelationen oder die Kunst des Identifizierens

    Definition (Äquivalenzrelation)  

    Eine Äquivalenzrelation auf einer Menge ist eine Relation , die die folgenden drei Eigenschaften besitzt (für beliebige ).

    1. Es ist (reflexiv).
    2. Aus folgt (symmetrisch).
    3. Aus und folgt (transitiv).

    Dabei bedeutet , dass das Paar zu gehört.

    Bei einer Äquivalenzrelation sagt man, dass und zueinander äquivalent sind, wenn gilt.


    Beispiel (Gleichheit)  

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



    Beispiel  

    Seien und Mengen und sei eine Abbildung. In einer solchen Situation hat man immer eine Äquivalenzrelation auf dem Definitionsbereich der Abbildung, und zwar erklärt man zwei Elemente als äquivalent, wenn sie unter auf das gleiche Element abgebildet werden, wenn also ist. Wenn die Abbildung injektiv ist, so ist die durch auf definierte Äquivalenzrelation die Gleichheit. Wenn die Abbildung konstant ist, so sind unter der zugehörigen Äquivalenzrelation alle Elemente aus untereinander äquivalent.



    Beispiel  

    Visualisierung des Beispiels

    Wir betrachten die Produktmenge , 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)

    und sagen, dass zwei Punkte äquivalent sind, wenn man ausgehend von den Punkt 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 nach kommen kann, dass man dann auch von nach 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 nach und dann von nach .

    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)  

    Sei eine Äquivalenzrelation und . Dann ist

    die Äquivalenzklasse von bezüglich .


    Definition (Quotientenmenge)  

    Sei eine Äquivalenzrelation. Dann heißt

    die Quotientenmenge von .


    Definition (Identifizierungsabbildung)  

    Sei eine Äquivalenzrelation und die Quotientenmenge. Die Abbildung

    heißt kanonische Projektion  (oder Identifizierungsabbildung) von .

    In der Sprache der Identifizierungen heißt dies: ist die Teilmenge aller Elemente von , die zu ä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  

    Sei eine Menge und eine Äquivalenzrelation auf mit den Äquivalenzklassen , , und der Quotientenmenge . Dann gelten folgende Aussagen.

    1. Es ist genau dann, wenn ist, und dies gilt genau dann, wenn .
    2. Die Identifikationsabbildung
      ist surjektiv.
    3. Es ist .

    Beweis  

    1. Seien und äquivalent und . Dann ist und nach der Transitivität auch , also . Damit stimmen die Äquivalenzklasssen überein. Die Implikation von der Mitte nach rechts ist klar, da wegen Äquivalenzklassen nicht leer sind. Sei nun , und sei ein Element im Durchschnitt. Dann ist und und wegen der Transitivität ist .
    2. Die Surjektivität ist klar aufgrund der Definition der Quotientenmenge, und da auf die Klasse geschickt wird.
    3. Es ist




    Fußnoten
    1. Das Wort „trivial“ kommt in Beweisen häufig vor, und drückt aus, dass eine (Teil-)Aussage sich von selbst versteht und dafür keine Argumentation durchgeführt wird. Lassen Sie sich von diesem Wort nicht abschrecken; als Studienanfänger braucht man eine gewisse Erfahrung mit häufig wiederkehrenden Argumentationsmustern, Beweise als trivial einschätzen und bei Bedarf selbst produzieren zu können.

    2. Wenn zwei Benennungen das gleiche Element bezeichnen, so kann man darauf eine Abbildung anwenden und erhält dann eine Gleichheit in der Wertemenge, da die Abbildung den Elementen der Menge ein wohldefiniertes Element zuordnet.



    << | Kurs:Mathematik (Osnabrück 2009-2011)/Teil I | >>

    PDF-Version dieser Vorlesung

    Arbeitsblatt zur Vorlesung (PDF)