Kapitel 1
Mengen, Abbildungen, Logik
Kapitel 1
Mengen, Abbildungen, Logik
Kapitel 1 © Beutelspacher
November 2003Seite 2
InhaltInhalt
1.1 Mengen
{ }, , ...
1.2 Logik
, , ...
1.3 Abbildungen
f: X Y
1.1 Mengen
{ }, , ...
1.2 Logik
, , ...
1.3 Abbildungen
f: X Y
Kapitel 1 © Beutelspacher
November 2003Seite 3
1.1 Was ist eine Menge?1.1 Was ist eine Menge?
• Schwierige Frage!
• Der „Vater der Mengenlehre“, Georg Cantor (1845 - 1918), sagte:
„Unter einer Menge verstehen wir jede Zusammenfassung M von
bestimmten, wohlunterschiedenen Objekten m unserer
Anschauung oder unseres Denkens ... zu einem Ganzen.“
• Anstatt genau zu sagen, was eine Menge ist, stellen wir dar, wie
man Mengen beschreiben kann. Dafür gibt es drei Möglichkeiten.
1. Durch Aufzählung
2. Durch Eigenschaften
3. Das kartesische Produkt
• Schwierige Frage!
• Der „Vater der Mengenlehre“, Georg Cantor (1845 - 1918), sagte:
„Unter einer Menge verstehen wir jede Zusammenfassung M von
bestimmten, wohlunterschiedenen Objekten m unserer
Anschauung oder unseres Denkens ... zu einem Ganzen.“
• Anstatt genau zu sagen, was eine Menge ist, stellen wir dar, wie
man Mengen beschreiben kann. Dafür gibt es drei Möglichkeiten.
1. Durch Aufzählung
2. Durch Eigenschaften
3. Das kartesische Produkt
Kapitel 1 © Beutelspacher
November 2003Seite 4
1.1.1 Beschreibung durch Aufzählung1.1.1 Beschreibung durch Aufzählung
• Beispiel: {rot, grün, blau} ist die Menge der Farben rot, grün und
blau.
• Beispiel: Die Menge {Susanne, Yvonne, Ute, Nicole} besteht aus
den Elementen Susanne, Yvonne, Ute, Nicole.
• Beispiel: Wir betrachten oft Mengen von Zahlen:
M = {0, 1, 2, 3, 4} ist die Menge der Zahlen 0, 1, 2, 3, 4.
• Beispiel: {rot, grün, blau} ist die Menge der Farben rot, grün und
blau.
• Beispiel: Die Menge {Susanne, Yvonne, Ute, Nicole} besteht aus
den Elementen Susanne, Yvonne, Ute, Nicole.
• Beispiel: Wir betrachten oft Mengen von Zahlen:
M = {0, 1, 2, 3, 4} ist die Menge der Zahlen 0, 1, 2, 3, 4.
Kapitel 1 © Beutelspacher
November 2003Seite 5
Notation und BemerkungNotation und Bemerkung
• Die Elemente der Menge werden in geschweifte Klammern
geschrieben:
a, b, c sind die Elemente der Menge {a, b, c}.
• Bei einer Menge spielt die Reihenfolge der Elemente keine
Rolle:
{c, a, b} = {b, a, c} = {a, b, c}.
• In einer Menge werden Elemente, die mehrfach auftauchen, nur
einmal betrachtet:
{a, a, a, a, b, b, b, c, c, c, c, c, c, c, c} = {a, b, c}.
• Die Elemente der Menge werden in geschweifte Klammern
geschrieben:
a, b, c sind die Elemente der Menge {a, b, c}.
• Bei einer Menge spielt die Reihenfolge der Elemente keine
Rolle:
{c, a, b} = {b, a, c} = {a, b, c}.
• In einer Menge werden Elemente, die mehrfach auftauchen, nur
einmal betrachtet:
{a, a, a, a, b, b, b, c, c, c, c, c, c, c, c} = {a, b, c}.
Kapitel 1 © Beutelspacher
November 2003Seite 6
Unendliche MengenUnendliche Mengen
• N: Menge der natürlichen Zahlen:
N = {0, 1, 2, 3, 4, ...}.
• Z: Menge der ganzen Zahlen:
Z = {..., –3, –2, –1, 0, 1, 2, 3, ...}.
• Q: Menge der rationalen Zahlen („Brüche”).
• R: Menge der reellen Zahlen.
• N: Menge der natürlichen Zahlen:
N = {0, 1, 2, 3, 4, ...}.
• Z: Menge der ganzen Zahlen:
Z = {..., –3, –2, –1, 0, 1, 2, 3, ...}.
• Q: Menge der rationalen Zahlen („Brüche”).
• R: Menge der reellen Zahlen.
Kapitel 1 © Beutelspacher
November 2003Seite 7
Elemente, TeilmengenElemente, Teilmengen
• m M: Das Element m ist in der Menge M enthalten.
• m M: Das Element m ist nicht in der Menge M enthalten.
• M1 M2 („Teilmenge“): Jedes Element von M1 ist auch ein Element
von M2.
• Beispiel:
M1 = {rot, blau} ist Teilmenge von M2 = {rot, blau, grün}.
• Die leere Menge enthält kein Element. Sie wird mit {} oder
bezeichnet.
• m M: Das Element m ist in der Menge M enthalten.
• m M: Das Element m ist nicht in der Menge M enthalten.
• M1 M2 („Teilmenge“): Jedes Element von M1 ist auch ein Element
von M2.
• Beispiel:
M1 = {rot, blau} ist Teilmenge von M2 = {rot, blau, grün}.
• Die leere Menge enthält kein Element. Sie wird mit {} oder
bezeichnet.
Kapitel 1 © Beutelspacher
November 2003Seite 8
1.1.2 Beschreibung einer Menge durch Eigenschaften1.1.2 Beschreibung einer Menge durch Eigenschaften
• Wichtiges Prinzip: Man sondert man aus einer schon vorhandenen
Menge eine Teilmenge aus.
• Man nennt das auch „Mengenbildung durch Aussonderung“
• Beispiele:
1. T = Menge aller Tiere. M = {t T t ist intelligent}. (Klassische
Definition des Menschen)
2. G = {z Z z ist gerade}.
Eigenschaft: „gerade sein“. Es ist G = {..., –4, –2, 0, 2, 4, ...}.
• Wichtiges Prinzip: Man sondert man aus einer schon vorhandenen
Menge eine Teilmenge aus.
• Man nennt das auch „Mengenbildung durch Aussonderung“
• Beispiele:
1. T = Menge aller Tiere. M = {t T t ist intelligent}. (Klassische
Definition des Menschen)
2. G = {z Z z ist gerade}.
Eigenschaft: „gerade sein“. Es ist G = {..., –4, –2, 0, 2, 4, ...}.
Kapitel 1 © Beutelspacher
November 2003Seite 9
Thema der WocheThema der Woche
• Was ist das Thema?
• Zeichnung
• Beispiele: Umwelt und Mathematik
• Historische Bemerkung
• …
• 1. Thema: Definition einer Menge durch Eigenschaften
• Was ist das Thema?
• Zeichnung
• Beispiele: Umwelt und Mathematik
• Historische Bemerkung
• …
• 1. Thema: Definition einer Menge durch Eigenschaften
Kapitel 1 © Beutelspacher
November 2003Seite 10
Durchschnitt (Schnittmenge)Durchschnitt (Schnittmenge)
• Der Durchschnitt zweier Mengen M1 und M2 ist so definiert:
M1 M2 = {m M1 m M2} (= {m M2 m M1}).
Eigenschaft: “m M2” .
• Beispiel: M1: Menge der Biologiestudenten, M2: Menge der Mathe-
matikstudenten. Dann ist M1 M2 die Menge der Studenten, die
sowohl Bio als auch Mathe studieren.
• Beispiel: G = Menge der geraden natürlichen Zahlen, D = Menge
der durch 3 teilbaren natürlichen Zahlen. Dann ist G D die Menge
der durch 6 teilbaren natürlichen Zahlen.
• Der Durchschnitt zweier Mengen M1 und M2 ist so definiert:
M1 M2 = {m M1 m M2} (= {m M2 m M1}).
Eigenschaft: “m M2” .
• Beispiel: M1: Menge der Biologiestudenten, M2: Menge der Mathe-
matikstudenten. Dann ist M1 M2 die Menge der Studenten, die
sowohl Bio als auch Mathe studieren.
• Beispiel: G = Menge der geraden natürlichen Zahlen, D = Menge
der durch 3 teilbaren natürlichen Zahlen. Dann ist G D die Menge
der durch 6 teilbaren natürlichen Zahlen.
Kapitel 1 © Beutelspacher
November 2003Seite 11
Disjunkte MengenDisjunkte Mengen
• Zwei Mengen heißen disjunkt (oder auch „elementfremd“),
wenn sie kein Element gemeinsam haben.
Formaler: M1 und M2 werden disjunkt genannt, falls M1 M2 = {}
gilt.
• Beispiel: Sei C die Menge der Mitglieder der CDU, S die Menge
der Mitglieder der SPD. Dann sind C und S disjunkte Mengen.
• Beispiel: Die Menge der durch 4 teilbaren Zahlen und die Menge
der Primzahlen sind disjunkt.
• Zwei Mengen heißen disjunkt (oder auch „elementfremd“),
wenn sie kein Element gemeinsam haben.
Formaler: M1 und M2 werden disjunkt genannt, falls M1 M2 = {}
gilt.
• Beispiel: Sei C die Menge der Mitglieder der CDU, S die Menge
der Mitglieder der SPD. Dann sind C und S disjunkte Mengen.
• Beispiel: Die Menge der durch 4 teilbaren Zahlen und die Menge
der Primzahlen sind disjunkt.
Kapitel 1 © Beutelspacher
November 2003Seite 12
VereinigungsmengeVereinigungsmenge
• Die Vereinigung zweier Mengen M1 und M2 ist so definiert:
M1 M2 = {m m M1 oder m M2}.
• Beispiel: M1: Menge der Biologiestudenten, M2: Menge der
Mathematikstudenten. Dann ist M1 M2 die Menge der Studenten,
die Bio oder Mathe (oder beides) studieren.
Bemerkung: Wenn wir „oder“ sagen meinen wir immer das nicht-
ausschließliche Oder.
• Beispiel: G = Menge der geraden natürlichen Zahlen, U = Menge
der ungeraden Zahlen. Dann ist G U = N.
• Die Vereinigung zweier Mengen M1 und M2 ist so definiert:
M1 M2 = {m m M1 oder m M2}.
• Beispiel: M1: Menge der Biologiestudenten, M2: Menge der
Mathematikstudenten. Dann ist M1 M2 die Menge der Studenten,
die Bio oder Mathe (oder beides) studieren.
Bemerkung: Wenn wir „oder“ sagen meinen wir immer das nicht-
ausschließliche Oder.
• Beispiel: G = Menge der geraden natürlichen Zahlen, U = Menge
der ungeraden Zahlen. Dann ist G U = N.
Kapitel 1 © Beutelspacher
November 2003Seite 13
Differenz von MengenDifferenz von Mengen
• Die Differenz zweier Mengen M1 und M2 ist so definiert:
M1\M2 = {m M1 m M2}.
• Eigenschaft: “m M2”.
• Beispiele: {rot, blau, gelb}\{grün, weiß, rot} = {blau, gelb}
Z\G = Menge der ungeraden ganzen Zahlen
N\G = Menge der ungeraden natürlichen Zahlen.
• Bemerkungen: 1. Wir benutzen “\” anstelle von “–”.
• 2. Man darf M1\M2 auch dann bilden,
wenn M2 keine Teilmenge von M1 ist.
• Die Differenz zweier Mengen M1 und M2 ist so definiert:
M1\M2 = {m M1 m M2}.
• Eigenschaft: “m M2”.
• Beispiele: {rot, blau, gelb}\{grün, weiß, rot} = {blau, gelb}
Z\G = Menge der ungeraden ganzen Zahlen
N\G = Menge der ungeraden natürlichen Zahlen.
• Bemerkungen: 1. Wir benutzen “\” anstelle von “–”.
• 2. Man darf M1\M2 auch dann bilden,
wenn M2 keine Teilmenge von M1 ist.
Kapitel 1 © Beutelspacher
November 2003Seite 14
Komplement einer MengeKomplement einer Menge
• Wenn die Menge M2 eine Teilmenge von M1 ist, so nennt man die
Differenz M1\M2 das Komplement von M2 in M1.
• Zwei Teilmengen M2 und M1 einer Menge M werden
komplementär genannt, wenn gilt
M1 M2 = M und M1 M2 = {}.
(Man kann auch sagen: … wenn M2 = M\M1 ist.)
• Beispiel: M1 = {2, 4, 6}, M2 = {1, 3, 5} sind komplementäre Teil-
mengen von {1, 2, 3, 4, 5, 6}.
• Wenn die Menge M2 eine Teilmenge von M1 ist, so nennt man die
Differenz M1\M2 das Komplement von M2 in M1.
• Zwei Teilmengen M2 und M1 einer Menge M werden
komplementär genannt, wenn gilt
M1 M2 = M und M1 M2 = {}.
(Man kann auch sagen: … wenn M2 = M\M1 ist.)
• Beispiel: M1 = {2, 4, 6}, M2 = {1, 3, 5} sind komplementäre Teil-
mengen von {1, 2, 3, 4, 5, 6}.
Kapitel 1 © Beutelspacher
November 2003Seite 15
1.1.3 Das kartesische Produkt1.1.3 Das kartesische Produkt
• Ziel: Mengen ganz neuen Typs!
• Seien M1 und M2 zwei Mengen mit M1, M2 {}. Dann ist das
kartesische Produkt die Menge M1M2, die aus allen geordneten
Paaren (m1, m2) mit m1 M1 und m2 M2 besteht.
• Beispiel: Ist M1 = {0, 1, 2} und M2 = {a, b}, so gilt
M1M2 = {(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}.
• Achtung: Bei den Paaren kommt es auf die Reihenfolge an! Zum
Beispiel ist das Paar (a, 0) kein Element der obigen Menge M1M2.
• Ziel: Mengen ganz neuen Typs!
• Seien M1 und M2 zwei Mengen mit M1, M2 {}. Dann ist das
kartesische Produkt die Menge M1M2, die aus allen geordneten
Paaren (m1, m2) mit m1 M1 und m2 M2 besteht.
• Beispiel: Ist M1 = {0, 1, 2} und M2 = {a, b}, so gilt
M1M2 = {(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}.
• Achtung: Bei den Paaren kommt es auf die Reihenfolge an! Zum
Beispiel ist das Paar (a, 0) kein Element der obigen Menge M1M2.
Kapitel 1 © Beutelspacher
November 2003Seite 16
Das allgemeine kartesische ProduktDas allgemeine kartesische Produkt
• Seien M1, M2, ..., Mn nichtleere Mengen, dann ist das kartesische
Produkt dieser Mengen definiert durch:
M1M2 . . . Mn = {(m1, m2, ..., mn) m1 M1, m2 M2, ..., mn Mn}
• Beispiel: Seien He, Ho, S die Mengen der Hemden, Hosen und
Schuhen von Professor X. Dann beschreibt die Menge HeHoS
die Möglichkeiten von Professor X, sich zu kleiden.
• Beispiel: Seien V die Menge der Vorspeisen, H die Menge der
Hauptspeisen, N die Menge der Nachspeisen einer Speisekarte.
Dann ist VHN die Menge aller mögliche Speisefolgen.
• Seien M1, M2, ..., Mn nichtleere Mengen, dann ist das kartesische
Produkt dieser Mengen definiert durch:
M1M2 . . . Mn = {(m1, m2, ..., mn) m1 M1, m2 M2, ..., mn Mn}
• Beispiel: Seien He, Ho, S die Mengen der Hemden, Hosen und
Schuhen von Professor X. Dann beschreibt die Menge HeHoS
die Möglichkeiten von Professor X, sich zu kleiden.
• Beispiel: Seien V die Menge der Vorspeisen, H die Menge der
Hauptspeisen, N die Menge der Nachspeisen einer Speisekarte.
Dann ist VHN die Menge aller mögliche Speisefolgen.
Kapitel 1 © Beutelspacher
November 2003Seite 17
Das kartesische Produkt: BemerkungenDas kartesische Produkt: Bemerkungen
• Die Bezeichnung “kartesisch” (früher auch „cartesisch“) geht auf den
Mathematiker und Philosophen René Descartes (1596 - 1650)
zurück.
In der Mathematik wird sein Name damit verbunden, dass er die
Punkte der Ebene durch Paare von Zahlen dargestellt hat (siehe
Kapitel 3).
• Die Elemente von M1M2 . . . Mn tragen vielfältige Namen:
n-Tupel, Folgen der Länge n.
Statt 2-Tupel sagt man Paar, statt 3-Tupel sagt man Tripel.
• Die Bezeichnung “kartesisch” (früher auch „cartesisch“) geht auf den
Mathematiker und Philosophen René Descartes (1596 - 1650)
zurück.
In der Mathematik wird sein Name damit verbunden, dass er die
Punkte der Ebene durch Paare von Zahlen dargestellt hat (siehe
Kapitel 3).
• Die Elemente von M1M2 . . . Mn tragen vielfältige Namen:
n-Tupel, Folgen der Länge n.
Statt 2-Tupel sagt man Paar, statt 3-Tupel sagt man Tripel.
Kapitel 1 © Beutelspacher
November 2003Seite 18
1.1.4 Mächtigkeiten1.1.4 Mächtigkeiten
• Sei M eine Menge.
Wir bezeichnen wir die Anzahl der Elemente von M mit M. Diese
Zahl heißt Mächtigkeit (oder Kardinalität) von M.
• Beispiel: {0,1,2,3} = 4.
• Eine Menge wird endlich genannt, wenn ihre Mächtigkeit eine
natürliche Zahl ist.
• Sonst heißt die Menge unendlich. Wenn M eine unendliche Menge
ist, so schreiben wir M = .
• Beispiel: N = und Z = .
• Sei M eine Menge.
Wir bezeichnen wir die Anzahl der Elemente von M mit M. Diese
Zahl heißt Mächtigkeit (oder Kardinalität) von M.
• Beispiel: {0,1,2,3} = 4.
• Eine Menge wird endlich genannt, wenn ihre Mächtigkeit eine
natürliche Zahl ist.
• Sonst heißt die Menge unendlich. Wenn M eine unendliche Menge
ist, so schreiben wir M = .
• Beispiel: N = und Z = .
Kapitel 1 © Beutelspacher
November 2003Seite 19
Mächtigkeit des KomplementsMächtigkeit des Komplements
1.1.1 Satz. Sei M1 eine endliche Menge, und sei M2 eine Teilmenge
von M1. Dann gilt:
M1\M2 = M1 – M2.
Beispiel: Anzahl der männlichen Einwohner der Bundesrepublik =
Gesamtbevölkerungszahl minus Anzahl der Frauen.
Beweis. Zu zeigen: Auf beiden Seiten steht die gleiche Zahl!
Linke Seite: Anzahl der Element von M1\M2.
Rechte Seite: Wir zählen zuerst die Anzahl der Elemente von M1, dann
ziehen wir die Elemente von M2 wieder ab. Daher erhalten wir auch
auf der rechten Seite die Anzahl der Elemente von M1\M2.
1.1.1 Satz. Sei M1 eine endliche Menge, und sei M2 eine Teilmenge
von M1. Dann gilt:
M1\M2 = M1 – M2.
Beispiel: Anzahl der männlichen Einwohner der Bundesrepublik =
Gesamtbevölkerungszahl minus Anzahl der Frauen.
Beweis. Zu zeigen: Auf beiden Seiten steht die gleiche Zahl!
Linke Seite: Anzahl der Element von M1\M2.
Rechte Seite: Wir zählen zuerst die Anzahl der Elemente von M1, dann
ziehen wir die Elemente von M2 wieder ab. Daher erhalten wir auch
auf der rechten Seite die Anzahl der Elemente von M1\M2.
Kapitel 1 © Beutelspacher
November 2003Seite 20
SummenformelSummenformel
1.1.2 Satz. Seien M1 und M2 endliche Mengen. Dann gilt
M1 M2 = M1 + M2 – M1 M2.
Beispiel: Für die Anzahl der Studierenden, die Mathematik
studieren oder Sport studieren, muß man wissen, (a) wie viele Leute
Mathe-matik studieren, (b) wie viele Sport studieren und (c) wie viele
Mathematik und Sport studieren.
1.1.2 Satz. Seien M1 und M2 endliche Mengen. Dann gilt
M1 M2 = M1 + M2 – M1 M2.
Beispiel: Für die Anzahl der Studierenden, die Mathematik
studieren oder Sport studieren, muß man wissen, (a) wie viele Leute
Mathe-matik studieren, (b) wie viele Sport studieren und (c) wie viele
Mathematik und Sport studieren.
Kapitel 1 © Beutelspacher
November 2003Seite 21
Summenformel: Der BeweisSummenformel: Der Beweis
Beweis (= warum ist das so?).
Zu zeigen: Auf beiden Seiten steht die gleiche Zahl! Linke Seite: Jedes Element von M1 M2 wird genau einmal gezählt.
Rechte Seite: In M1 + M2 wird jedes Element von M1 und jedes
Element von M2 einmal gezählt,
die Elemente von M1M2 werden also doppelt gezählt.
Dies wird dadurch korrigiert, dass M1 M2 wieder abgezogen
wird.
Daher wird auch auf der rechten Seite jedes Element genau einmal
gezählt.
Beweis (= warum ist das so?).
Zu zeigen: Auf beiden Seiten steht die gleiche Zahl! Linke Seite: Jedes Element von M1 M2 wird genau einmal gezählt.
Rechte Seite: In M1 + M2 wird jedes Element von M1 und jedes
Element von M2 einmal gezählt,
die Elemente von M1M2 werden also doppelt gezählt.
Dies wird dadurch korrigiert, dass M1 M2 wieder abgezogen
wird.
Daher wird auch auf der rechten Seite jedes Element genau einmal
gezählt.
Kapitel 1 © Beutelspacher
November 2003Seite 22
Die ProduktformelDie Produktformel
1.1.3 Satz. Seien M1, M2 nichtleere endliche Mengen. Dann gilt:
M1M2 = M1 M2.
Beispiel: In einem Raum befinden sich 6 Frauen und 4 Männer.
Dann kann man genau 64 = 24 getrenntgeschlechtliche Paare
bilden.
Beispiel: Die Anzahl aller Paare (x, y),
wobei x aus der Menge {0, 1, 2, ..., 9}
und y aus der Menge {a, b, c, d, ..., z} stammt,
ist 1026 = 260.
1.1.3 Satz. Seien M1, M2 nichtleere endliche Mengen. Dann gilt:
M1M2 = M1 M2.
Beispiel: In einem Raum befinden sich 6 Frauen und 4 Männer.
Dann kann man genau 64 = 24 getrenntgeschlechtliche Paare
bilden.
Beispiel: Die Anzahl aller Paare (x, y),
wobei x aus der Menge {0, 1, 2, ..., 9}
und y aus der Menge {a, b, c, d, ..., z} stammt,
ist 1026 = 260.
Kapitel 1 © Beutelspacher
November 2003Seite 23
Die Produktformel: Der BeweisDie Produktformel: Der Beweis
Beweis (= warum ist die Formel richtig?).
Die Menge M1M2 besteht aus allen Paaren (m1, m2) mit m1 M1
und m2 M2. Wir müssen die Anzahl dieser Paare berechnen.
Für die erste Komponente (also für m1) haben wir genau M1
Möglichkeiten zu Auswahl.
Für jede dieser Möglichkeiten können wir die zweite Komponente m2
in M2 ohne jede Einschränkung wählen.
Dafür gibt es M2 viele Möglichkeiten.
Um ein Paar (m1, m2) zu wählen gibt es insgesamt also genau M1
M2 Möglichkeiten.
Beweis (= warum ist die Formel richtig?).
Die Menge M1M2 besteht aus allen Paaren (m1, m2) mit m1 M1
und m2 M2. Wir müssen die Anzahl dieser Paare berechnen.
Für die erste Komponente (also für m1) haben wir genau M1
Möglichkeiten zu Auswahl.
Für jede dieser Möglichkeiten können wir die zweite Komponente m2
in M2 ohne jede Einschränkung wählen.
Dafür gibt es M2 viele Möglichkeiten.
Um ein Paar (m1, m2) zu wählen gibt es insgesamt also genau M1
M2 Möglichkeiten.
Kapitel 1 © Beutelspacher
November 2003Seite 24
Allgemeine ProduktformelAllgemeine Produktformel
1.1.4 Satz. Seien M1, M2, ..., Mn endliche nichtleere Mengen. Dann
ist
M1M2 ... Mn = M1M2 ... Mn.
Beispiel. Wenn Professor X genau 8 Hemden, 3 Hosen und 4 Paar
Schuhe hat, so kann er sich auf 834 = 96 Weisen kleiden.
Beispiel. Bei Geldausgabeautomaten besteht die Geheimzahl aus
vier Dezimalstellen, von denen die erste nicht 0 sein darf. Wie viele
solche PINs gibt es?
Antwort: 9101010 = 9000.
1.1.4 Satz. Seien M1, M2, ..., Mn endliche nichtleere Mengen. Dann
ist
M1M2 ... Mn = M1M2 ... Mn.
Beispiel. Wenn Professor X genau 8 Hemden, 3 Hosen und 4 Paar
Schuhe hat, so kann er sich auf 834 = 96 Weisen kleiden.
Beispiel. Bei Geldausgabeautomaten besteht die Geheimzahl aus
vier Dezimalstellen, von denen die erste nicht 0 sein darf. Wie viele
solche PINs gibt es?
Antwort: 9101010 = 9000.
Kapitel 1 © Beutelspacher
November 2003Seite 25
1.2 Logik1.2 Logik
• Aussagen
• Zusammengesetzte Aussagen
• Wahrheitstafeln
• Allaussagen
• Existenzaussagen
• Aussagen
• Zusammengesetzte Aussagen
• Wahrheitstafeln
• Allaussagen
• Existenzaussagen
Kapitel 1 © Beutelspacher
November 2003Seite 26
AussagenAussagen
• Eine Aussage ist ein sprachliches Konstrukt, das prinzipiell falsch
oder wahr ist.
• Beispiele für Aussagen:
Alle Mathematikstudenten sind intelligent.
Es gibt unendlich viele Primzahlen.
2+2 = 5.
• Keine Aussagen sind zum Beispiel:
Guten Morgen!
5+3
Howgh, ich habe gesprochen!
• Eine Aussage ist ein sprachliches Konstrukt, das prinzipiell falsch
oder wahr ist.
• Beispiele für Aussagen:
Alle Mathematikstudenten sind intelligent.
Es gibt unendlich viele Primzahlen.
2+2 = 5.
• Keine Aussagen sind zum Beispiel:
Guten Morgen!
5+3
Howgh, ich habe gesprochen!
Kapitel 1 © Beutelspacher
November 2003Seite 27
Zusammengesetzte AussagenZusammengesetzte Aussagen
• Wir bezeichnen Aussagen mit Großbuchstaben, wie A, B, C.
• Aus einer oder zwei Aussagen A und B kann man eine dritte
machen. Die wichtigsten „zusammengesetzten” Aussagen sind:
A (nicht A)
• A B (A oder B)
• A B (A und B)
• A B (wenn A, dann B)
• A B (A genau dann, wenn B)
• Wir bezeichnen Aussagen mit Großbuchstaben, wie A, B, C.
• Aus einer oder zwei Aussagen A und B kann man eine dritte
machen. Die wichtigsten „zusammengesetzten” Aussagen sind:
A (nicht A)
• A B (A oder B)
• A B (A und B)
• A B (wenn A, dann B)
• A B (A genau dann, wenn B)
Kapitel 1 © Beutelspacher
November 2003Seite 28
WahrheitstafelnWahrheitstafeln
• Wie kann man eine zusammengesetzte Aussage beschreiben?
• Wir müssen für zusammengesetzte Aussagen nur festlegen, wann
sie wahr und wann sie falsch sein sollen.
• Das hängt davon ab, ob die Aussagen A und B wahr oder falsch
sind.
• Dies können wir mit Hilfe von Wahrheitstafeln ausdrücken.
• Wie kann man eine zusammengesetzte Aussage beschreiben?
• Wir müssen für zusammengesetzte Aussagen nur festlegen, wann
sie wahr und wann sie falsch sein sollen.
• Das hängt davon ab, ob die Aussagen A und B wahr oder falsch
sind.
• Dies können wir mit Hilfe von Wahrheitstafeln ausdrücken.
Kapitel 1 © Beutelspacher
November 2003Seite 29
A B („A und B“)A B („A und B“)
• A B A Bw w w
w f f
f w f
f f f
• Wenn A und B wahr sind, dann ist A B wahr.
Wenn A wahr und B falsch ist, dann ist A B falsch.
Wenn A falsch und B wahr ist, dann ist A B falsch.
Wenn A und B falsch sind, dann ist A B falsch.
• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist falsch.
• A B A Bw w w
w f f
f w f
f f f
• Wenn A und B wahr sind, dann ist A B wahr.
Wenn A wahr und B falsch ist, dann ist A B falsch.
Wenn A falsch und B wahr ist, dann ist A B falsch.
Wenn A und B falsch sind, dann ist A B falsch.
• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist falsch.
Kapitel 1 © Beutelspacher
November 2003Seite 30
A B („A oder B“)A B („A oder B“)
• A B A Bw w w
w f w
f w w
f f f
• Wenn A und B wahr sind, dann ist A B wahr.
Wenn A wahr und B falsch ist, dann ist A B wahr.
Wenn A falsch und B wahr ist, dann ist A B wahr.
Wenn A und B falsch sind, dann ist A B falsch.
• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist wahr.
• A B A Bw w w
w f w
f w w
f f f
• Wenn A und B wahr sind, dann ist A B wahr.
Wenn A wahr und B falsch ist, dann ist A B wahr.
Wenn A falsch und B wahr ist, dann ist A B wahr.
Wenn A und B falsch sind, dann ist A B falsch.
• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist wahr.
Kapitel 1 © Beutelspacher
November 2003Seite 31
A („nicht A“)A („nicht A“)
A A
w f
f w
• Das bedeutet: A ist genau dann eine wahre Aussage, wenn A
falsch ist.
• Beispiel: (2+2=5) ist eine wahre Aussage.
A A
w f
f w
• Das bedeutet: A ist genau dann eine wahre Aussage, wenn A
falsch ist.
• Beispiel: (2+2=5) ist eine wahre Aussage.
Kapitel 1 © Beutelspacher
November 2003Seite 32
A B („wenn A, dann B“)A B („wenn A, dann B“)
A B A B
w w w
w f f
f w w
f f w
• Wenn A und B wahr sind, dann ist A B eine wahre Aussage.
Wenn A wahr und B falsch ist, dann ist A B falsch.
Wenn A falsch und B wahr ist, dann ist A B wahr.
Wenn A und B falsch sind, dann ist A B eine wahre Aussage.
• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist wahr.
A B A B
w w w
w f f
f w w
f f w
• Wenn A und B wahr sind, dann ist A B eine wahre Aussage.
Wenn A wahr und B falsch ist, dann ist A B falsch.
Wenn A falsch und B wahr ist, dann ist A B wahr.
Wenn A und B falsch sind, dann ist A B eine wahre Aussage.
• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist wahr.
Kapitel 1 © Beutelspacher
November 2003Seite 33
A B („A genau dann, wenn B“)A B („A genau dann, wenn B“)
A B A B
w w w
w f f
f w f
f f w
• A B ist genau dann eine wahre Aussage, wenn A und B beide
wahr oder beide falsch sind.
• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist eine
falsche Aussage, aber die Aussage (2+2=5) (6 ist eine Primzahl)
ist eine wahre Aussage.
A B A B
w w w
w f f
f w f
f f w
• A B ist genau dann eine wahre Aussage, wenn A und B beide
wahr oder beide falsch sind.
• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist eine
falsche Aussage, aber die Aussage (2+2=5) (6 ist eine Primzahl)
ist eine wahre Aussage.
Kapitel 1 © Beutelspacher
November 2003Seite 34
Aussagen: BemerkungenAussagen: Bemerkungen
• Wenn zwei Aussagen den gleichen Wahrheitswert haben (also beide
wahr oder beide falsch sind), so schreiben wir A = B. (Man könnte
auch A B schreiben.)
• Bemerkung. Obige Festlegungen sind zum Teil willkürlich.
Aber so sind die Symbole und der Sprachgebrauch in der
Mathematik festgelegt!
• Wenn zwei Aussagen den gleichen Wahrheitswert haben (also beide
wahr oder beide falsch sind), so schreiben wir A = B. (Man könnte
auch A B schreiben.)
• Bemerkung. Obige Festlegungen sind zum Teil willkürlich.
Aber so sind die Symbole und der Sprachgebrauch in der
Mathematik festgelegt!
Kapitel 1 © Beutelspacher
November 2003Seite 35
SätzeSätze
• Wahrheitstafeln dienen nicht nur der Definition von Aussagen,
sondern können auch dazu verwendet werden, Sätze zu beweisen.
• Was ist ein mathematischer Satz?
Ein mathematischer Satz ist eine zusammengesetzte Aussage, die
immer wahr ist.
Das heißt, dass sie unabhängig von der Verteilung der
Wahrheitswerte der Einzelaussagen wahr ist.
• Ein mathematischer Satz besteht immer aus einer Voraussetzung
und einer Behauptung.
Das heißt: Jeder Satz ist eine „Wenn-dann-Aussage“.
• Wahrheitstafeln dienen nicht nur der Definition von Aussagen,
sondern können auch dazu verwendet werden, Sätze zu beweisen.
• Was ist ein mathematischer Satz?
Ein mathematischer Satz ist eine zusammengesetzte Aussage, die
immer wahr ist.
Das heißt, dass sie unabhängig von der Verteilung der
Wahrheitswerte der Einzelaussagen wahr ist.
• Ein mathematischer Satz besteht immer aus einer Voraussetzung
und einer Behauptung.
Das heißt: Jeder Satz ist eine „Wenn-dann-Aussage“.
Kapitel 1 © Beutelspacher
November 2003Seite 36
Ein einfacher SatzEin einfacher Satz
Satz. Für alle Aussagen A und B gilt:
(A B) A.
„Gelten” bedeutet, dass die Gesamtaussage stets wahr ist, unab-
hängig davon, ob die Aussagen A und B wahr oder falsch sind.
Beweis.
A B A B (A B) A
w w w w
w f f w
f w f w
f f f w
Satz. Für alle Aussagen A und B gilt:
(A B) A.
„Gelten” bedeutet, dass die Gesamtaussage stets wahr ist, unab-
hängig davon, ob die Aussagen A und B wahr oder falsch sind.
Beweis.
A B A B (A B) A
w w w w
w f f w
f w f w
f f f w
Kapitel 1 © Beutelspacher
November 2003Seite 37
Die de Morganschen GesetzeDie de Morganschen Gesetze
1.2.1 Satz (Augustus de Morgan). Seien A und B Aussagen. Dann
gilt
(a) (A B) = A B (erstes de Morgansches Gesetz).
(b) (A B) = A B (zweites de Morgansches Gesetz).
Beweisidee. (a) Wir zeigen diese Behauptung dadurch, dass wir
zeigen, dass für jede Belegung der Wahrheitswerte von A und B
die beiden Seiten (A B) und A B stets den gleichen
Wahrheitswert haben.
1.2.1 Satz (Augustus de Morgan). Seien A und B Aussagen. Dann
gilt
(a) (A B) = A B (erstes de Morgansches Gesetz).
(b) (A B) = A B (zweites de Morgansches Gesetz).
Beweisidee. (a) Wir zeigen diese Behauptung dadurch, dass wir
zeigen, dass für jede Belegung der Wahrheitswerte von A und B
die beiden Seiten (A B) und A B stets den gleichen
Wahrheitswert haben.
Kapitel 1 © Beutelspacher
November 2003Seite 38
Beweis des ersten de Morganschen GesetzesBeweis des ersten de Morganschen Gesetzes
Wahrheitstafel für (A B) und A B
A B (A B) A B A B
w w f f f f
w f w f w w
f w w w f w
f f w w w w
Die beiden Seiten haben genau an den gleichen Stellen w und f
stehen; also sind die Aussagen gleich.
Wahrheitstafel für (A B) und A B
A B (A B) A B A B
w w f f f f
w f w f w w
f w w w f w
f f w w w w
Die beiden Seiten haben genau an den gleichen Stellen w und f
stehen; also sind die Aussagen gleich.
Kapitel 1 © Beutelspacher
November 2003Seite 39
Beweis des zweiten de Morganschen GesetzesBeweis des zweiten de Morganschen Gesetzes
Wahrheitstafel für (A B) und A B:
A B (A B) A B A B
w w f f f f
w f f f w f
f w f w f f
f f w w w w
Die beiden Seiten haben genau an den gleichen Stellen w und f
stehen; also sind die Aussagen gleich.
Wahrheitstafel für (A B) und A B:
A B (A B) A B A B
w w f f f f
w f f f w f
f w f w f f
f f w w w w
Die beiden Seiten haben genau an den gleichen Stellen w und f
stehen; also sind die Aussagen gleich.
Kapitel 1 © Beutelspacher
November 2003Seite 40
AllaussagenAllaussagen
Allaussagen: Aussagen über alle Elemente einer Menge.
Beispiel: Alle Primzahlen > 2 sind ungerade.
In jedem Dreieck schneiden sich die Mittellote in einem Punkt.
Formal schreiben wir dafür
Für alle x gilt ...
x ...
Beispiele:
Für alle Dreiecke gilt: Die Winkelsumme ist 180°
Sei M = {1, 3, 5, 7}. Dann gilt: Für alle m M ist m eine ungerade
Zahl.
Allaussagen: Aussagen über alle Elemente einer Menge.
Beispiel: Alle Primzahlen > 2 sind ungerade.
In jedem Dreieck schneiden sich die Mittellote in einem Punkt.
Formal schreiben wir dafür
Für alle x gilt ...
x ...
Beispiele:
Für alle Dreiecke gilt: Die Winkelsumme ist 180°
Sei M = {1, 3, 5, 7}. Dann gilt: Für alle m M ist m eine ungerade
Zahl.
Kapitel 1 © Beutelspacher
November 2003Seite 41
Allaussagen: BemerkungenAllaussagen: Bemerkungen
1. Es gibt keinen logischen Unterschied zwischen „Für alle Elemente
gilt ...“ und „für jedes Element gilt ...“.
Sprachlich ist manchmal das eine, manchmal das andere besser.
2. Eine Allaussage ist eine lange und-Aussage.
Beispiel: Sei M = {1, 3, 5, 7}. Dann gilt: Für alle m M ist m eine
ungerade Zahl.
Stattdessen kann man auch sagen und schreiben:
(1 ist ungerade) (3 ist ungerade) (5 ist ungerade)
(7 ist ungerade).
1. Es gibt keinen logischen Unterschied zwischen „Für alle Elemente
gilt ...“ und „für jedes Element gilt ...“.
Sprachlich ist manchmal das eine, manchmal das andere besser.
2. Eine Allaussage ist eine lange und-Aussage.
Beispiel: Sei M = {1, 3, 5, 7}. Dann gilt: Für alle m M ist m eine
ungerade Zahl.
Stattdessen kann man auch sagen und schreiben:
(1 ist ungerade) (3 ist ungerade) (5 ist ungerade)
(7 ist ungerade).
Kapitel 1 © Beutelspacher
November 2003Seite 42
ExistenzaussagenExistenzaussagen
Existenzaussage: Es gibt mindestens ein Element der betreffenden
Menge, das eine gewisse Eigenschaft hat.
Beispiele: (a) Es gibt eine gerade Primzahl.
(b) Sei M = {1, 4, 9, 16}. Dann gilt
m M: m ist gerade.
Jede Existenzaussage ist eine sehr lange oder-Aussage. Statt
m M, das gerade ist
kann man auch sagen:
(1 ist gerade) (4 ist gerade) (9 ist gerade) (16 ist gerade).
Existenzaussage: Es gibt mindestens ein Element der betreffenden
Menge, das eine gewisse Eigenschaft hat.
Beispiele: (a) Es gibt eine gerade Primzahl.
(b) Sei M = {1, 4, 9, 16}. Dann gilt
m M: m ist gerade.
Jede Existenzaussage ist eine sehr lange oder-Aussage. Statt
m M, das gerade ist
kann man auch sagen:
(1 ist gerade) (4 ist gerade) (9 ist gerade) (16 ist gerade).
Kapitel 1 © Beutelspacher
November 2003Seite 43
Verneinung von All- und ExistenzaussagenVerneinung von All- und Existenzaussagen
1.2.2 Satz. (a) Die Negation einer Allaussage ist eine
Existenzaussage. Genauer gilt:
( x gilt ...) = x, für das nicht gilt ...
(b) Die Negation einer Existenzaussage ist eine Allaussage.
Genauer gilt:
( x, für das gilt ) = x gilt nicht ...
Beispiele: (a) Alle Schwäne sind weiß
Negation: Es gibt einen nichtweißen Schwan.
(b) Es gibt einen dummen Studenten
Negation: Alle Studenten sind intelligent.
1.2.2 Satz. (a) Die Negation einer Allaussage ist eine
Existenzaussage. Genauer gilt:
( x gilt ...) = x, für das nicht gilt ...
(b) Die Negation einer Existenzaussage ist eine Allaussage.
Genauer gilt:
( x, für das gilt ) = x gilt nicht ...
Beispiele: (a) Alle Schwäne sind weiß
Negation: Es gibt einen nichtweißen Schwan.
(b) Es gibt einen dummen Studenten
Negation: Alle Studenten sind intelligent.
Kapitel 1 © Beutelspacher
November 2003Seite 44
1.3 Abbildungen1.3 Abbildungen
• Ziel: Vergleich von Mengen.
Feststellung von Ähnlichkeiten und Unterschieden.
Um Dinge vergleichen zu können, muss man sie zusammenbringen.
Dazu braucht man Abbildungen.
• Definition. Seien X und Y Mengen.
Eine Abbildung von X nach Y ist eine Vorschrift,
die jedem Element von X
genau ein Element von Y zuordnet.
• Ziel: Vergleich von Mengen.
Feststellung von Ähnlichkeiten und Unterschieden.
Um Dinge vergleichen zu können, muss man sie zusammenbringen.
Dazu braucht man Abbildungen.
• Definition. Seien X und Y Mengen.
Eine Abbildung von X nach Y ist eine Vorschrift,
die jedem Element von X
genau ein Element von Y zuordnet.
Kapitel 1 © Beutelspacher
November 2003Seite 45
Beispiele von AbbildungenBeispiele von Abbildungen
• Zuordnung Ware Preis ist eine Abbildung.
Hier ist X die Menge der Waren und Y die Menge der Preise. Jede
Ware hat einen eindeutigen Preis; also ist die Zuordnung eine
Abbildung.
• Zuordnung Person Körpergröße ist eine Abbildung.
X: Menge aller Personen, Y: Menge der natürlichen Zahlen.
Die Körpergröße einer Person ist eindeutig.
Es kann sein, dass mehrere Personen dieselbe Größe haben; das
ist nicht verboten.
• Zuordnung Ware Preis ist eine Abbildung.
Hier ist X die Menge der Waren und Y die Menge der Preise. Jede
Ware hat einen eindeutigen Preis; also ist die Zuordnung eine
Abbildung.
• Zuordnung Person Körpergröße ist eine Abbildung.
X: Menge aller Personen, Y: Menge der natürlichen Zahlen.
Die Körpergröße einer Person ist eindeutig.
Es kann sein, dass mehrere Personen dieselbe Größe haben; das
ist nicht verboten.
Kapitel 1 © Beutelspacher
November 2003Seite 46
Sprache der AbbildungenSprache der Abbildungen
• Für eine Abbildung f von X nach Y schreiben wir f: X Y.
• Jedem Element x X wird genau ein y Y zugeordnet. Dieses y
bezeichnen wir mit f(x).
• Bezeichnung:
f: X Y: y = f(x)
oder
f: X Y: x f(x).
X: Definitionsbereich, Y: Bildbereich.
• Für eine Abbildung f von X nach Y schreiben wir f: X Y.
• Jedem Element x X wird genau ein y Y zugeordnet. Dieses y
bezeichnen wir mit f(x).
• Bezeichnung:
f: X Y: y = f(x)
oder
f: X Y: x f(x).
X: Definitionsbereich, Y: Bildbereich.
Kapitel 1 © Beutelspacher
November 2003Seite 47
Mathematische BeispieleMathematische Beispiele
• Sei f die Abbildung der Menge {1,2,3} in sich, die folgendermaßen
erklärt ist
1 1, 2 3, 3 2.
• Die Vorschrift f: R R, definiert durch f(x) = x2, ist eine Abbildung.
• Wir ordnen jeder nichtleeren Teilmenge von N ihr kleinstes Element
zu. Das ergibt eine Abbildung; Definitionsbereich: Menge aller
nichtleeren Teilmengen von N, Bildbereich: N.
• Sei p/q eine rationale Zahl, das heißt p, q Z, q 0. Wir nehmen
an, dass q positiv ist und der Bruch so weit wie möglich gekürzt ist.
Dann wird durch f(p/q) = q eine Abbildung f von Q in N definiert.
• Sei f die Abbildung der Menge {1,2,3} in sich, die folgendermaßen
erklärt ist
1 1, 2 3, 3 2.
• Die Vorschrift f: R R, definiert durch f(x) = x2, ist eine Abbildung.
• Wir ordnen jeder nichtleeren Teilmenge von N ihr kleinstes Element
zu. Das ergibt eine Abbildung; Definitionsbereich: Menge aller
nichtleeren Teilmengen von N, Bildbereich: N.
• Sei p/q eine rationale Zahl, das heißt p, q Z, q 0. Wir nehmen
an, dass q positiv ist und der Bruch so weit wie möglich gekürzt ist.
Dann wird durch f(p/q) = q eine Abbildung f von Q in N definiert.
Kapitel 1 © Beutelspacher
November 2003Seite 48
Die IdentitätDie Identität
• Wir betrachten Abbildungen einer Menge X in sich.
• Identität: ordnet jedem Element x aus X
wieder das Element x zu.
• Bezeichnung: id oder genauer idX .
• Es gilt also
idX(x) = x für alle x X.
• Wir betrachten Abbildungen einer Menge X in sich.
• Identität: ordnet jedem Element x aus X
wieder das Element x zu.
• Bezeichnung: id oder genauer idX .
• Es gilt also
idX(x) = x für alle x X.
Kapitel 1 © Beutelspacher
November 2003Seite 49
Hintereinanderausführung von AbbildungenHintereinanderausführung von Abbildungen
• Ziel: Vergleich der Menge X mit der Menge Y, Vergleich von Y mit
Z ergibt Vergleich von X mit Z.
• Definition: Sei g: X Y eine Abbildung von X nach Y, und sei f: Y
Z eine Abbildung von Y nach Z. Dann ist f g eine Abbildung von
X nach Z, wenn wir definieren
f g: X Z: x f(g(x)).
• Man spricht von Hintereinanderausführung von Abbildungen; (oder:
Verknüpfung, Verkettung, Komposition oder Produkt).
• Achtung Reihenfolge! Für f g muss man zuerst g und dann f
ausführen. Man liest „f g“ als „f nach g” oder „erst g, dann f”.
• Ziel: Vergleich der Menge X mit der Menge Y, Vergleich von Y mit
Z ergibt Vergleich von X mit Z.
• Definition: Sei g: X Y eine Abbildung von X nach Y, und sei f: Y
Z eine Abbildung von Y nach Z. Dann ist f g eine Abbildung von
X nach Z, wenn wir definieren
f g: X Z: x f(g(x)).
• Man spricht von Hintereinanderausführung von Abbildungen; (oder:
Verknüpfung, Verkettung, Komposition oder Produkt).
• Achtung Reihenfolge! Für f g muss man zuerst g und dann f
ausführen. Man liest „f g“ als „f nach g” oder „erst g, dann f”.
Kapitel 1 © Beutelspacher
November 2003Seite 50
BeispieleBeispiele
Beispiel: Sei X = {0, 1, 2}, Y = {a, b, c}, Z = {, , }. Seien g: X Y
und f: Y Z die folgendermaßen definierten Abbildungen:
g(0) = c, g(1) = a, g(2) = c; f(a) = , f(b) = , f(c) = .
Dann ist f g wie folgt definiert:
(f g)(0) = f(g(0)) = f(c) = , (f g)(1) = f(g(1)) = f(a) = ,
(f g)(2) = f(g(2)) = f(c) = .
Beispiel: Sei g die Abbildung, die einem Kraftfahrzeug seinen
Hubraum und f die Abbildung, die einem Hubraum die Steuerklasse
zuordnet. Dann ist f g die Abbildung, die einem Kraftfahrzeug
seine Steuerklasse zuordnet.
Beispiel: Sei X = {0, 1, 2}, Y = {a, b, c}, Z = {, , }. Seien g: X Y
und f: Y Z die folgendermaßen definierten Abbildungen:
g(0) = c, g(1) = a, g(2) = c; f(a) = , f(b) = , f(c) = .
Dann ist f g wie folgt definiert:
(f g)(0) = f(g(0)) = f(c) = , (f g)(1) = f(g(1)) = f(a) = ,
(f g)(2) = f(g(2)) = f(c) = .
Beispiel: Sei g die Abbildung, die einem Kraftfahrzeug seinen
Hubraum und f die Abbildung, die einem Hubraum die Steuerklasse
zuordnet. Dann ist f g die Abbildung, die einem Kraftfahrzeug
seine Steuerklasse zuordnet.
Kapitel 1 © Beutelspacher
November 2003Seite 51
Injektiv, surjektiv, bijektivInjektiv, surjektiv, bijektiv
• Sei f eine Abbildung von X nach Y.
• Definition: Man nennt f injektiv, wenn keine zwei verschiedenen
Elemente von X auf dasselbe Element von Y abgebildet werden.
Bei keinem Element von Y enden zwei oder mehr Pfeile.
• Definition: Man nennt f surjektiv, wenn es zu jedem Element y Y
ein x X gibt mit f(x) = y.
An jedem Element von Y endet mindestens ein Pfeil.
• Definition: Eine Abbildung heißt bijektiv, wenn sie injektiv und
surjektiv ist.
An jedem Element von Y endet genau ein Pfeil.
• Sei f eine Abbildung von X nach Y.
• Definition: Man nennt f injektiv, wenn keine zwei verschiedenen
Elemente von X auf dasselbe Element von Y abgebildet werden.
Bei keinem Element von Y enden zwei oder mehr Pfeile.
• Definition: Man nennt f surjektiv, wenn es zu jedem Element y Y
ein x X gibt mit f(x) = y.
An jedem Element von Y endet mindestens ein Pfeil.
• Definition: Eine Abbildung heißt bijektiv, wenn sie injektiv und
surjektiv ist.
An jedem Element von Y endet genau ein Pfeil.
Kapitel 1 © Beutelspacher
November 2003Seite 52
BeispieleBeispiele
• Die Abbildung, die einer Person ihr Alter (in Jahren) zuordnet, ist
nicht injektiv, da es verschiedene Personen desselben Alters gibt.
• Die Abbildung, die jedem Kraftfahrzeug sein Kennzeichen zuordnet,
ist injektiv.
• Die Abbildung, die jedem ehemaligen Studenten seine Examensnote
zuordnet, ist (vermutlich) surjektiv, aber nicht injektiv.
• Die Abbildung f der Menge {0, 1, 2} in die Menge {a, b, c}
f(0) = b, f(1) = c, f(2) = a
ist sowohl injektiv als auch surjektiv, also bijektiv.
• Die Abbildung, die einer Person ihr Alter (in Jahren) zuordnet, ist
nicht injektiv, da es verschiedene Personen desselben Alters gibt.
• Die Abbildung, die jedem Kraftfahrzeug sein Kennzeichen zuordnet,
ist injektiv.
• Die Abbildung, die jedem ehemaligen Studenten seine Examensnote
zuordnet, ist (vermutlich) surjektiv, aber nicht injektiv.
• Die Abbildung f der Menge {0, 1, 2} in die Menge {a, b, c}
f(0) = b, f(1) = c, f(2) = a
ist sowohl injektiv als auch surjektiv, also bijektiv.
Kapitel 1 © Beutelspacher
November 2003Seite 53
UmkehrabbildungenUmkehrabbildungen
• Beispiel: Wie können wir die Abbildung f mit f(0) = b, f(1) = c und
f(2) = a rückgängig machen? – Ganz einfach dadurch, dass wir
jedem Bild sein Urbild zuordnen.
Die Umkehrabbildung muss b auf 0, c auf 1 und a auf 2
abbilden.
• Die Umkehrabbildung von f ist eine Abbildung von Y = {a, b, c} in
X = {0, 1, 2}, die wir mit f–1 bezeichnen. Sie ist definiert durch
f–1(a) = 2, f–1(b) = 0, f–1(c) = 1.
• Kurz: Wenn wir mit f die Pfeile von links nach rechts durchlaufen,
so durchlaufen wir mit f–1 die Pfeile von rechts nach links.
• Beispiel: Wie können wir die Abbildung f mit f(0) = b, f(1) = c und
f(2) = a rückgängig machen? – Ganz einfach dadurch, dass wir
jedem Bild sein Urbild zuordnen.
Die Umkehrabbildung muss b auf 0, c auf 1 und a auf 2
abbilden.
• Die Umkehrabbildung von f ist eine Abbildung von Y = {a, b, c} in
X = {0, 1, 2}, die wir mit f–1 bezeichnen. Sie ist definiert durch
f–1(a) = 2, f–1(b) = 0, f–1(c) = 1.
• Kurz: Wenn wir mit f die Pfeile von links nach rechts durchlaufen,
so durchlaufen wir mit f–1 die Pfeile von rechts nach links.
Kapitel 1 © Beutelspacher
November 2003Seite 54
Der Satz über die UmkehrfunktionDer Satz über die Umkehrfunktion
1.3.1 Satz. Sei f: X Y eine bijektive Abbildung. Dann gibt es eine
Abbildung f–1, die die Wirkung von f rückgängig macht. Genauer
gesagt muss f–1 also eine Abbildung von Y X sein, die folgende
Eigenschaften hat:
ff–1 = idY und f–1f = idX.
Das bedeutet, dass für alle x X und für alle y Y gilt
ff–1(y) = y und f–1f(x) = x.
Mit anderen Worten: Jede bijektive Abbildung f ist umkehrbar (oder
invertierbar).
1.3.1 Satz. Sei f: X Y eine bijektive Abbildung. Dann gibt es eine
Abbildung f–1, die die Wirkung von f rückgängig macht. Genauer
gesagt muss f–1 also eine Abbildung von Y X sein, die folgende
Eigenschaften hat:
ff–1 = idY und f–1f = idX.
Das bedeutet, dass für alle x X und für alle y Y gilt
ff–1(y) = y und f–1f(x) = x.
Mit anderen Worten: Jede bijektive Abbildung f ist umkehrbar (oder
invertierbar).
Kapitel 1 © Beutelspacher
November 2003Seite 55
Beweis des Satzes über die UmkehrfunktionBeweis des Satzes über die Umkehrfunktion
Beweis. Wir müssen die Abbildung f–1 : Y X finden.
Das heißt: für jedes y Y müssen wir f–1(y) definieren –
und zwar so, dass die Wirkung von f rückgängig gemacht wird,
dass also f(x) = y gilt.
Da f ist eine surjektive Abbildung ist, gibt es zu jedem y Y
(mindestens) ein x X mit f(x) = y.
Da f injektiv ist, gibt es nur ein einziges solches x.
Also können wir die Abbildung f–1 von Y nach X definieren durch
f–1(y) := x.
Dann gilt nach Definition f f–1(y) = f(x) = y und f–1f(x) = f–1(y) = x für
alle y Y und alle x X.
Beweis. Wir müssen die Abbildung f–1 : Y X finden.
Das heißt: für jedes y Y müssen wir f–1(y) definieren –
und zwar so, dass die Wirkung von f rückgängig gemacht wird,
dass also f(x) = y gilt.
Da f ist eine surjektive Abbildung ist, gibt es zu jedem y Y
(mindestens) ein x X mit f(x) = y.
Da f injektiv ist, gibt es nur ein einziges solches x.
Also können wir die Abbildung f–1 von Y nach X definieren durch
f–1(y) := x.
Dann gilt nach Definition f f–1(y) = f(x) = y und f–1f(x) = f–1(y) = x für
alle y Y und alle x X.