1. Foundations

1.1 Mathematical logic

1.2 Set theory

1.1 Mathematical logic

1.1.1 Propositions and formulas

Mathematics begins with the

Agreement: A proposition is a colloquial sentence which is either true (1) or false (0).

The idea of a proposition can not be captured into a definition since such a definition would always make use of other undefined notions, here colloquial, sentence, true and false.

Our agreement contains the following principle of bivalence:

⟶  There is no third possibility other than true or false.

Examples:

• The number \( 3 \) is a prime number.
• The number \( 4 \) is a prime number.
• There are infinitely many prime twin primes.

The first statement is correct, the second is false. We can not decide whether or not the third statement is true but we are convinced that it is either true or false.

We can not assign true or false to every linguistic expression. This concerns in particular congratulations, questions, requests and so on, for example:

• Happy birthday!
• Break a leg!
• Speak of the devil!

Mathematical expressions, such as

• \( x+7=28 \)
• \( {\mathcal R}(0,3,1) \)

are called formulas. A formula turns into a proposition if we replace the ‘placeholder’ \( x \) by a number so that \( x+7=28 \) becomes a true or false statement, or we interpret \( {\mathcal R}(x,y,z) \) as the relation \( x\lt y\lt z, \) and \( {\mathcal R}(0,3,1) \) becomes false.

Exercises

1.1.2 Verknüpfungen von Aussagen

Mathematische Aussagen bezeichnen wir mit kleinen Buchstaben \( a, \) \( b, \) \( c \) usw. Wir ordnen ihnen genau einen der beiden Wahrheitswerte zu

Aussagen setzen wir durch folgende Junktoren miteinander in Beziehung \[ \neg\,,\quad \vee\,,\quad \wedge\,,\quad \to\,,\quad \leftrightarrow\,. \] In dieser Reihenfolge bedeuten sie:

Die Bedeutungen dieser Verknüpfungen definieren wir anhand einer Wahrheitstabelle:

Die Äquivalenz \( \leftrightarrow \) können wir als auch durch \( \to \) ausdrücken: \[ a\leftrightarrow b\quad\mbox{ist gleichbedeutend mit}\quad a\to b\ \mbox{und}\ b\to a. \] Aussagen \( a \) und \( b \) mit denselben Wahrheitstabellen heißen semantisch äquivalent, wir schreiben \( a\equiv b. \) So gelten also beispielsweise \[ (a\leftrightarrow b)\equiv(a\to b)\wedge(b\to a), \] oder aber auch \[ (a\to b)\equiv(\neg a\vee b), \] wie folgende Wahrheitstabelle lehrt:

Die runden Klammern in vorigen Formeln, in welcher Reihenfolge die Verknüpfungen auszuführen sind. Wir vereinbaren: Von der höchsten zur niedrigsten Priorität sind der Reihe nach auszuführen \( \neg, \) \( \wedge, \) \( \vee, \) \( \to, \) \( \leftrightarrow. \)

Satz: Es gelten die Distributivgesetze der Aussagenlogik \[ \begin{array}{l} a\wedge(b\vee c)\equiv(a\wedge b)\vee(a\wedge c), \\ a\vee(b\wedge c)\equiv(a\vee b)\wedge(a\vee c) \end{array} \] sowie die de Morganschen Regeln der Aussagenlogik \[ \begin{array}{l} \neg(a\wedge b)\equiv\neg a\vee\neg b, \\ \neg(a\vee b)\equiv\neg a\wedge\neg b. \end{array} \]

Aufgaben zu diesem Abschnitt

1.1.3 Aussagenlogische Beweisprinzipien

Definition: Unter einer Tautologie verstehen wir eine Aussage, die unabhängig von der Belegung ihrer Variablen durch die Wahrheitswerte \( 0 \) oder \( 1 \) stets wahr ist.

Beispiele solcher Tautologien, die auch gleichzeitig grundlegende mathematische Beweisprinzipien darstellen, beinhaltet der

Satz: Die folgenden Aussagen sind Tautologien:

Hieraus möchten wir vier Beweisprinzipien in Worte wiedergeben:

Im Gegensatz zu Tautologien sind Kontradiktionen Aussagen, die unabhängig von der Belegung ihrer Variablen durch Wahrheitswerte stets falsch sind.

Aufgaben zu diesem Abschnitt

1.1.4 Quantoren

Wir haben wir es stets mit Variablen \( x,y,\ldots \) als Elemente von Individuenmengen zu tun. Für ihre Beschreibung benötigen wir die beiden folgenden Quantoren.

Definition: Es sei \( p \) eine von einer Variablen \( x \) aus einer Individuenmenge \( X \) abhängige Aussageform. Der Allquantor \( \forall \) und der Existenzquantor \( \exists \) sind dann wie folgt definiert:

Im zweiten Punkt bedeutet „es existiert“ die Existenz wenigstens eines Elementes \( x \) aus der Individuenmenge \( X. \)

Beispiel: Eine reellwertige Funktion \( f\colon\Omega\to\mathbb R \) heißt in einem Punkt \( x_0\in\Omega \) stetig, wenn gilt \[ \forall\varepsilon>0\,\exists\delta>0\,\forall x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\to\lvert f(x)-f(x_0)\rvert\lt\varepsilon) \] bzw. in Worten:

Für alle \( \varepsilon\gt 0 \) existiert ein \( \delta\ge 0, \) so dass für alle \( x\in\Omega: \) \( |x-x_0|\lt\delta \) impliziert \( |f(x)-f(x_0)|\lt\varepsilon. \)

Wir benötigen hierin vier Variablen \( x, \) \( x_0, \) \( \delta, \) \( \varepsilon, \) wobei \( x, \) \( \varepsilon, \) \( \delta \) von den Quantoren \( \forall \) bzw. \( \exists \) gebunden werden, während \( x_0 \) frei bleibt.

Die Relationen \( \in \) und \( \lt \) sind Beispiele sogenannter Prädikate. Logische Formeln dieser und ähnlicher Art sind Gegenstand der Prädikatenlogik und werden als prädikatenlogische Formeln bezeichnet.

Definition: Der Allquantor \( \forall \) und der Existenzquantor \( \exists \) werden wie folgt negiert \[ \neg\forall x\,p(x)\equiv\exists x\,\neg p(x),\quad \neg\exists x\,p(x)\equiv\forall x\,\neg p(x). \] Linksseitig wirkt der Negationsoperator jeweils auf die gesamten Ausdrücke \( \forall x\,p(x) \) bzw. \( \exists x\,p(x). \)

Beispiel: Wir ermitteln \[ \neg\forall x\,\exists y\,p(y)\equiv\exists x\,\neg\exists y\,p(y)\equiv\exists x\forall y\,\neg p(y). \]

Aufgaben zu diesem Abschnitt

1.1.5 Aufgaben

Aufgaben zu Aussagen und Aussageformen

Aufgabe 1.1.1: (Beispiele für Aussagen)

Welche der folgenden Sätze sind Aussagen, welche sind keine Aussagen?

Aufgabe 1.1.2: (Aussageformen)

Geben Sie jeweils ein Beispiel einer mathematischen Aussageform \( {\mathcal R}(x) \) mit einer, \( {\mathcal S}(x,y) \) mit zwei und \( {\mathcal T}(x,y,z) \) mit drei freien Variablen, so dass

Aufgaben zu Verknüpfungen von Aussagen

Aufgabe 1.1.3: (Doppelte Verneinung)

Beweisen Sie die aussagenlogische Äquivalenz vermittels einer Wahrheitstabelle \[ \neg\neg a\equiv a. \]

Aufgabe 1.1.4: (Äquivalenzen der Implikation)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

Aufgabe 1.1.5: (Distributivgesetze der Aussagenlogik)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

Aufgabe 1.1.6: (de Morgansche Regeln der Aussagenlogik)

Beweisen Sie die folgenden aussagenlogischen Äquivalenzen vermittels Wahrheitstabellen:

Aufgaben zu Aussagenlogische Beweisprinzipien

Aufgabe 1.1.7: (Beispiele aussagenlogischer Tautologien I)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

Die Aussage (ii) bezeichnet man auch als reductio ad absurdum (indirekter Beweis oder Beweis durch Widerspruch).

Aufgabe 1.1.8: (Beispiele aussagenlogischer Tautologien II)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

Aufgabe 1.1.9: (Beispiele aussagenlogischer Tautologien III)

Beweisen Sie die folgenden aussagenlogischen Tautologien vermittels Wahrheitstabellen:

Aufgaben zu Quantoren

Aufgabe 1.1.10: (Mathematische Aussagen)

Es bezeichne \( \mathbb Z=\{\ldots,-2,-1,0,1,2,\ldots\} \) die Menge der ganzen Zahlen. Schreiben Sie die folgenden Aussagen als prädikatenlogische Formeln. Welche Aussage ist wahr, welche ist falsch?

Aufgabe 1.1.11: (Negation der Stetigkeit)

Negieren Sie obige prädikatenlogische Formel der Stetigkeit einer Funktion in einem Punkt \( x_0\in\Omega, \) d.h. \[ \forall\varepsilon\gt 0\,\exists\delta\gt 0\,\forall x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\to\lvert f(x)-f(x_0)\rvert\lt\varepsilon) \] mit dem Ergebnis \[ \exists\varepsilon>0\,\forall\delta\gt 0\,\exists x\in\Omega\,(\lvert x-x_0\rvert\lt\delta\wedge\lvert f(x)-f(x_0)\rvert\ge\varepsilon). \]

1.1.6 Wiederholungsfragen

1.2 Mengenlehre

1.2.1 Charakterisierung von Mengen

Eine Menge \( M \) lässt sich auf zwei Arten charakterisieren, nämlich:

Beispiele:

Einmal durch Aufzählen der Elemente:

Ein zweites Mal durch Angabe einer charakterisierenden Eigenschaft:

Nach der axiomatischen Mengenlehre von Zermelo und Fraenkel existiert genau eine leere Menge \( \emptyset, \) welche kein Element enthält. Sie ist sie Teilmenge jeder Menge (siehe unten). Es ist insbesondere \[ \{x\in X\,:\,p(x)\} \] gleich der leeren Menge, falls die Aussage \( p(x) \) für kein \( x\in X \) wahr, also widersprüchlich ist. Jede andere Menge, die nicht gleich der leeren Menge ist, besitzt wenigstens ein Element.

Wir sprechen von einer endlichen Menge, falls die Anzahl ihrer Elemente eine endliche Zahl ist, andernfalls von einer unendlichen Menge (für eine genaue Definition siehe Abschnitt 1.2.4 unten).

Aufgaben zu diesem Abschnitt

1.2.2 Mengenrelationen und Mengenoperationen

Zunächst die zentralen Mengenrelationen:

Definition: Seien \( A \) und \( B \) zwei beliebige Mengen. Dann erklären wir

mit \( A\not= B \) für \( \neg(A=B). \)

Die Mengengleichheit \( A=B \) können wir auch so auffassen: \[ A=B\quad\mbox{genau dann, wenn}\quad A\subseteq B\ \mbox{und}\ B\subseteq A. \] Schließlich sind \( A\supseteq B \) gleichbedeutend mit \( B\subseteq A \) und \( A\supset B \) gleichbedeutend mit \( B\subset A. \)

Zweitens die wichtigsten Mengenoperationen:

Definition: Seien \( A \) und \( B \) zwei beliebige Mengen. Dann erklären wir ihre Vereinigung, ihren Durchschnitt und ihre Differenz gemäß

Definition: Seien \( A \) und \( B \) zwei beliebige Mengen. Dann erklären wir ihr kartesisches Produkt gemäß \[ A\times B:=\{(x,y)\,:\,x\in A,\ y\in B\}\,. \]

Das Symbol \( a:=b \) bedeutet, dass der neu einzuführende Ausdruck \( a \) definiert wird als der Ausdruck \( b. \) Dazu muss \( b \) bekannt sein.

Definition: Sei \( A\subseteq X \) Teilmenge einer Obermenge \( X. \) Dann erklären wir ihr Komplement gemäß \[ A^c:=\{x\,:\,x\in X\setminus A\} \]

Vereinigung, Durchschnitt, Differenz, kartesisches Produkt und Komplement von Mengen sind wieder Mengen.

Aufgaben zu diesem Abschnitt

1.2.3 Rechenregeln für Mengen

In Verallgemeinerung der bekannten aussagenlogischen Formeln \[ a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c),\quad a\vee(b\wedge c)=(a\vee b)\wedge(a\vee c) \] gilt der folgende

Satz: (Distributivgesetz der Mengenlehre)

Für drei beliebige Mengen \( A, \) \( B \) und \( C \) gelten \[ A\cap(B\cup C)=(A\cap B)\cup(A\cap C),\quad A\cup(B\cap C)=(A\cup B)\cap(A\cup C). \]

Beweis: Wir zeigen nur die erste Behauptung. Wir wählen ein \( x\in A\cap(B\cup C) \) beliebig. Dann ist unter Verwendung des aussagenlogischen Distributivgesetzes für \( \wedge \) und \( \vee \) in der dritten Zeile, angewandt auf die Aussagen \( x\in A \) usw. (achten Sie darauf, wie die Mengenoperationen \( \cap \) und \( \cup \) aufgelöst werden)

\[ \begin{array}{lll} x\in A\cap(B\cup C) & \longrightarrow & (x\in A)\wedge(x\in B\cup C) \\ & \longrightarrow & (x\in A)\wedge(x\in B\vee x\in C) \\ & \longrightarrow & (x\in A\wedge x\in B)\vee(x\in A\wedge x\in C) \\ & \longrightarrow & (x\in A\cap B)\vee(x\in A\cap C) \\ & \longrightarrow & x\in(A\cap B)\cup(A\cap C). \end{array} \]

Es ist also \( x\in(A\cap B)\cup(A\cap C), \) falls \( x\in A\cap(B\cup C), \) und da \( x \) beliebig gewählt wurde, folgt \[ A\cap(B\cup C)\subseteq(A\cap B)\cup(A\cap C). \] Die umgekehrte Inklusion \( \supseteq \) verbleibt als Übung.\( \qquad\Box \)

Die de Morganschen Regeln der Aussagenlogik übertragen sich wie folgt:

Satz: (de Morgansche Regeln der Mengenlehre)

Sind \( A \) und \( B \) zwei beliebige Teilmengen einer Obermenge \( X, \) so gelten \[ X\setminus(A\cup B)=(X\setminus A)\cap(X\setminus B),\quad X\setminus(A\cap B)=(X\setminus A)\cup(X\setminus B). \]

Aufgaben zu diesem Abschnitt

1.2.4 Abbildungen zwischen Mengen

Wir betrachten Abbildungen \( f\colon A\longrightarrow B. \)

Definition: Eine Abbildung \( f\colon A\to B \) zwischen zwei Mengen \( A \) und \( B \) heißt

Insbesondere ist eine Abbildung \( f\colon A\to B \)

Eine bijektive Abbildung \( f\colon A\to B \) ordnet jedem Element \( a\in A \) genau ein Element \( b\in B \) zu, und umgekehrt wird jedes Element \( b\in B \) auf genau ein Element \( a\in A \) abgebildet, und zwar vermöge der in diesem Fall existierenden Umkehrabbildung \[ f^{-1}\colon B\longrightarrow A. \] Diese Umkehrabbildung besitzt die Eigenschaften \[ \begin{array}{l} f^{-1}\circ f(a):=f^{-1}(f(a))=a\quad\mbox{für alle}\ a\in A, \\ f\circ f^{-1}(b):=f(f^{-1}(b))=b\quad\mbox{für alle}\ b\in B. \end{array} \]

Definition: Eine Menge \( A \) heißt endlich, falls eine natürliche Zahl \( n\in\mathbb N \) und eine bijektive Abbildung \[ f\colon\{1,\ldots,n\}\longrightarrow A \] existieren. In diesem Fall setzen wir \( |A|:=n. \)

Aufgaben zu diesem Abschnitt

1.2.5 Mächtigkeit von Mengen

Unter der Mächtigkeit einer endlichen Menge \( A \) mit Elementen \( a_1,\ldots,a_n \) verstehen wir die Anzahl \( n \) ihrer Elemente und schreiben \[ |A|:=n. \] Im Fall unendlicher Mengen können wir aber nicht von einer solchen Anzahl sprechen. Uns genügt stattdessen die auf G. Cantor zurückgehende

Definition: Zwei Mengen \( A \) und \( B \) heißen gleichmächtig, wenn eine bijektive Abbildung \( f\colon A\to B \) existiert.

Für eine beliebige Menge \( A \) bezeichnen wir nun mit \( {\mathcal P}(A) \) ihre Potenzmenge, d.h. die Menge, deren Elemente genau die Teilmengen von \( A \) sind.

Beispiel: Es ist \[ {\mathcal P}(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\}\,, \] denn \( \emptyset, \) \( \{1\}, \) \( \{2\} \) und \( \{1,2\} \) sind die vier möglichen Teilmengen von \( \{1,2\}. \) Beachte dabei, dass die leere Menge \( \emptyset \) Teilmenge jeder Menge ist.

Tatsächlich gilt für jede endliche Menge \( A \) \[ |A|<|{\mathcal P}(A)|=2^{|A|}\,. \] Der Fall unendlicher Mengen wird uns im zweiten Kapitel begegnen.

Aufgaben zu diesem Abschnitt

1.2.6 Aufgaben

Aufgaben - Charakterisierung von Mengen

Aufgabe 1.2.1: (Darstellung von Mengen)

Welche Elemente besitzen die folgenden Mengen?

Aufgaben - Mengenrelationen und Mengenoperationen

Aufgabe 1.2.2: (Rechenübung zu den Mengenoperationen)

Gegeben seien eine Grundmenge \( \Omega=\{0,1,2,3,4,5,6\} \) sowie die Teilmengen \[ A=\{1,2,3\}\,,\quad B=\{2,3,4\}\,. \] Ermitteln Sie \[ \Omega\setminus A,\quad \Omega\setminus B,\quad A\cup B,\quad A\cap B,\quad A\setminus B,\quad B\setminus A. \]

Aufgabe 1.2.3: (Kartesisches Produkt von Mengen)

Bilden Sie das kartesische Produkt \( M\times N \) der folgenden Mengen:

Aufgaben - Rechenregeln für Mengen

Aufgabe 1.2.4: (Distributivgesetze der Mengenlehre)

Es seien \( A, \) \( B \) und \( C \) drei beliebige Mengen. Beweisen Sie:

Aufgabe 1.2.5: (de Morgansche Regeln der Mengenlehre)

Es seien \( A \) und \( B \) zwei beliebige Teilmengen einer nichtleeren Obermenge \( X. \) Beweisen Sie:

Aufgabe 1.2.6: (Enthalten oder sogar gleich?)

Es seien \( A, \) \( B, \) \( C, \) \( D \) beliebige Mengen. Welche der folgenden Behauptungen ist richtig, welche falsch? Beweisen Sie bzw. begründen Sie durch ein Gegenbeispiel.

Aufgaben - Abbildungen zwischen Mengen

Aufgabe 1.2.7: (Injektive und surjektive Abbildungen)

Finden Sie jeweils Beispiele von Mengen \( A \) und \( B \) sowie eine Abbildung \( f\colon A\to B, \) so dass gilt:

Begründen Sie.

Aufgabe 1.2.8: (Abbildungen von Teilmengen)

Es sei \( f\colon A\to B \) eine Abbildung zwischen den Mengen \( A \) und \( B. \) Weiter seien \( M,N\subseteq A \) zwei Teilmengen von \( A \) mit der Eigenschaft \( M\subseteq N. \) Beweisen Sie \[ f(M)\subseteq f(N). \]

Aufgabe 1.2.9: (Abbildung und Umkehrabbildung)

Es seien \( A \) und \( B \) zwei nichtleere Mengen und \( f\colon A\to B \) sowie \( g\colon B\to A \) zwei Abbildungen mit der Eigenschaft \[ g\circ f(a)=a\quad\mbox{für alle}\ a\in A. \] Beweisen Sie, dass \( f \) injektiv und \( g \) surjektiv ist.

Aufgaben - Mächtigkeit von Mengen

Aufgabe 1.2.10: (Potenzmengen endlicher Mengen)

Bestimmen Sie die Potenzmengen der folgenden Mengen \( M: \)

Aufgabe 1.2.11: (Potenzmenge auf Vereinigung und Durchschnitt)

Es seien \( A \) und \( B \) zwei beliebige Mengen.

1.2.7 Wiederholungsfragen