Kapitel 1 Mengen, Abbildungen, Logik. Kapitel 1 © Beutelspacher November 2003 Seite 2 Inhalt 1.1...

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

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

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

• 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

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

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

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.

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.

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

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

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.

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 = {}

• 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 = {}

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

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.

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.

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

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.

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.

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.

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

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.

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.

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

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

Daher wird auch auf der rechten Seite jedes Element genau einmal

gezählt.

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.

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.

Allgemeine ProduktformelAllgemeine Produktformel

1.1.4 Satz. Seien M1, M2, ..., Mn endliche nichtleere Mengen. Dann

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

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.2 Logik1.2 Logik

• Aussagen

• Zusammengesetzte Aussagen

• Wahrheitstafeln

• Allaussagen

• Existenzaussagen

• Aussagen

• Zusammengesetzte Aussagen

• Wahrheitstafeln

• Allaussagen

• Existenzaussagen

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!

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!

Howgh, ich habe gesprochen!

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)

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

• 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

• Dies können wir mit Hilfe von Wahrheitstafeln ausdrücken.

A B („A und B“)A B („A und B“)

• A B A Bw w w

• 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

Wenn A falsch und B wahr ist, dann ist A B falsch.

• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist falsch.

A B („A oder B“)A B („A oder B“)

• A B A Bw w w

Wenn A wahr und B falsch ist, dann ist A B wahr.

Wenn A falsch und B wahr ist, dann ist A B wahr.

• Beispiel: Die Aussage (2+2=5) (5 ist eine Primzahl) ist wahr.

• A B A Bw w w

Wenn A wahr und B falsch ist, dann ist A B wahr.

A („nicht A“)A („nicht A“)

• Das bedeutet: A ist genau dann eine wahre Aussage, wenn A

falsch ist.

• Beispiel: (2+2=5) ist eine wahre Aussage.

• Das bedeutet: A ist genau dann eine wahre Aussage, wenn A

falsch ist.

• Beispiel: (2+2=5) ist eine wahre Aussage.

A B („wenn A, dann B“)A B („wenn A, dann B“)

A B A B

• Wenn A und B wahr sind, dann ist A B eine wahre Aussage.

Wenn A und B falsch sind, dann ist A B eine wahre Aussage.

A B A B

• Wenn A und B wahr sind, dann ist A B eine wahre Aussage.

Wenn A und B falsch sind, dann ist A B eine wahre Aussage.

A B („A genau dann, wenn B“)A B („A genau dann, wenn B“)

A B A B

• 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

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

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!

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

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

Die de Morganschen GesetzeDie de Morganschen Gesetze

1.2.1 Satz (Augustus de Morgan). Seien A und B Aussagen. Dann

(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

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

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

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

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

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

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

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

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

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

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

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.

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.

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.

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)

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)

f: X Y: x f(x).

X: Definitionsbereich, Y: Bildbereich.

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.

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.

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

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.

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.

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.

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.

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

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.

Kapitel 1 Mengen, Abbildungen, Logik. Kapitel 1 © Beutelspacher November 2003 Seite 2 Inhalt 1.1...

Documents

Stoffzusammenfassung: Lineare AlgebraINHALTSVERZEICHNIS 1 Grundbegriffe 3 1.1 Mengen, Abbildungen Gruppen, Ringe, Korper¨ . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Mengen

Logik f¨ur Informatiker 1. Grundlegende Beweisstrategiensofronie/logik-ss-2012/slides/... · Logik f¨ur Informatiker 1. Grundlegende Beweisstrategien Viorica Sofronie-Stokkermans

Schmitz Hegels Logik

Logik für Informatiker - KIT · Vorlesung Logik für Informatiker 6. Aussagenlogik – Resolution – Bernhard Beckert Universität Koblenz-Landau Sommersemester 2006 Logik für

Analysis für Physiker - TU Dresdenkoksch/lectures/Physik/physik5.pdf · 1 Mengen und Abbildungen 1.1 Grundbegriffe der mathematischen Logik 1.1.1 Aussagenlogische Ausdrücke Eine

Lineare Algebra - RWTH Aachen University€¦ · 2 KAPITEL I. GRUNDLAGEN Abbildungen Es seien Mengen X und Y gegeben. Eine Abbildung (oder Funktion) von X nach Y besteht aus X und

Logik und Argumentation - Leibniz Universität Hannover · 2019-08-27 · Logik und Argumentation Materialien zu einführenden Vorlesungen über formale Logik und Argumentationstheorie

Logik, Mengen, Relationen

Angewandte Mathematik und Statistik · AMAS Grundlagen Logik Mengen Abbildungen Zahlen unFktionen ektorgeo LA Analysis Statistik Einfache Verknüpfung von Aussagen Seien A und B Aussagen

Mengen und Kosten im Griff. Jedes Gebäude hat seinen Preis.entegra.de/include/produkte/Autodesk_Quantity_Takeoff.pdf · Mengen- und Kostenermittlung im Handumdrehen Mengen- und Kostenermittler

Logik f¨ur Informatiker - userpages.uni-koblenz.desofronie/logik-ss-2012/slides/pred-logik-08.pdf · Pr¨adikatenlogische Resolution Grundidee Vor Resolutionsschritt durch geeignete

Mathematik f ur Physiker I - Ruhr University Bochum · 2011-02-21 · Mengen, Abbildungen und Zahlen (ii)Auch kommt es bei mehrfachen Vereinigungen und Durchschnitten nicht darauf

Georg Wilhelm Friedrich Hegel - Die Wissenschaft der Logik. Die subjektive Logik (1834)

Menschliche Logik AND Boolsche Logik = NOT Logisch

Fachschaft Mathematik & Informatik Mengen & Logik Mathe-Vorkurs August 2007 Fachschaft Mathematik und Informatik

Lineare Algebra, Teil I - mathematik.tu-dortmund.de · Lineare Algebra, Teil I 11. Oktober 2010 0. Kapitel I. Grundbegriﬀe Inhalt: 1. Logik 2. Mengen und Abbildungen 3. Primfaktorzerlegung

Fuzzy-MengenalsAlternativezum Wahrscheinlichkeitsbegriﬀ · 1 Fuzzy-Mengen 1.2 VerallgemeinerungvonMengenoperationenaufFuzzy-Mengen DasichimvorherigenAbschnittdieklassischenMengenalsspezielleFuzzy-Mengen

Lineare Algebra I - math.uni-leipzig.dediem/la/zusammenfassung-la-I.pdf · Inhaltsverzeichnis Kapitel I – Grundlegende Strukturen Vorbemerkungen Mengen Abbildungen Relationen Halbgruppen,

Kombinatorik - fileTechnische Universität München Kombinatorik • Teilgebiet der Mathematik • Zählen der Anzahl von Abbildungen, Elemente von Mengen, Anzahl von möglichen Anordnungen

Br uckenkurs Mathematik Vorlesung Logik, Mengen, Zahlen · 2 Br uckenkurs Mathematik, c K.Rothe, Vorlesung Logik, Mengen, Zahlen Bemerkungen Entscheidend ist, dass jeder Aussage ein