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 statement which is either true (1) or false (0).

The idea of a proposition can not be covered by a definition. For example, our formulation makes use of other undefined notions, here statement, 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 twin primes.

The first proposition is correct, the second is false. We can not decide whether or not the third proposition 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 proposition, or we interpret \( {\mathcal R}(x,y,z) \) as the relation \( x\lt y\lt z, \) and \( {\mathcal R}(0,3,1) \) becomes false.

Exercise: Give examples of formulas \( {\mathcal R}(x) \) with one, \( {\mathcal S}(x,y) \) with two, and \( {\mathcal T}(x,y,z) \) with three variables such that

Video tutorial

1.1.2 Logical connectives

We want to denote propositions by small letters \( a, \) \( b, \) \( c \) etc. To each proposition we assign a truth value

Propositions can be connected by the following connectives \[ \neg\,,\quad \vee\,,\quad \wedge\,,\quad \to\,,\quad \leftrightarrow\,. \] In this order they stand for

We define the meaning of this connectives by means of the following truth table:

The equivalence \( \leftrightarrow \) can be written using \( \to \) and \( \wedge \) as follows \[ a\leftrightarrow b\quad\mbox{means}\quad(a\to b)\wedge(b\to a). \] The round brackets indicate the order of the operations. We reach the agreement: From the highest to the lowest priority are to be performed in the following order \( \neg, \) \( \wedge, \) \( \vee, \) \( \to, \) \( \leftrightarrow. \)

Definition: Two propositions \( a \) and \( b \) with the same truth table are called semantically equivalent, written as \( a\equiv b. \)

Example: There hold \[ (a\leftrightarrow b)\equiv(a\to b)\wedge(b\to a), \] and also \[ (a\to b)\equiv(\neg a\vee b) \] as the following truth table shows:

Video tutorial

1.1.3 Propositional laws of equivalence

In this paragraph we want to provide some important propositional laws of equivalence. We start with the following law of double negation.

Proposition: It holds \[ \neg\neg a\equiv a. \]

The propositions \( \neg\neg a \) and \( a \) are clearly semantically equivalent: if \( \neg\neg a \) has truth value \( 0 \) then \( a \) is \( 1, \) and vice versa. Next we state the so-called idempotence laws of propositional logic.

Proposition: There hold \[ a\equiv a\vee a,\quad a\equiv a\wedge a. \]

We omit a proof and come to the following commutative laws and associative laws of propositional logic.

Proposition: The connectives \( \vee \) and \( \wedge \) are commutative, i.e. \[ a\vee b\equiv b\vee a,\quad a\wedge b\equiv b\wedge a, \] and associative, i.e. \[ a\vee(b\vee c)\equiv(a\vee b)\vee c,\quad a\wedge(b\wedge c)\equiv(a\wedge b)\wedge c. \]

The following distributive laws form our next set of equivalences.

Proposition: There hold

Disjunction \( \vee \) and conjunction \( \wedge \) merge as formulated in the

Proposition: There hold \[ a\equiv a\wedge(a\vee b),\quad a\equiv a\vee(a\wedge b). \]

Furthermore, we will often use certain equivalences for the implication, provided by our next

Proposition: There hold

The first statement (i) is known from → this paragraph, (ii) can be verified by means of a truth table, and (iii) is a compilation of \( a\to b \) and \( b\to a \) together with (i). Finally, we come to the following de Morgan's laws of propositional logic which prescribe how to negate disjunction and conjunction.

Proposition: There hold

Exercise: Proof all the above propositions by means of truth tables.

Video tutorial

1.1.4 Methods of proof

Definition: A tautology is a proposition which is always true or a propositional formula which is always true independent of the truth values of its variables.

We give examples of tautologies which are at the same time important methods of mathematical proofs.

Theorem: The following propositions are tautologies:

We want to clarify the following four principle in our own words:

Theorem: The following proposition is a tautology \[ (a\to b)\wedge(a\to\neg b)\to\neg a. \]

In our own words: If \( b \) follows from \( a \) and \( \neg b \) also follows from \( a, \) then \( a \) must be false. This is the so-called reductio ad absurdum.

The opposite of a tautology is a contradiction which is always false.

Exercise: Prove all tautologies from the theorems by means of truth tables.

Exercise: Prove that the following propositions are tautologies.

Video tutorium

1.1.5 Quantifiers

We will always work with variables \( x,y,\ldots \) as elements from a set \( X,Y,\ldots, \) written as \[ x\in X,\quad y\in Y \quad\mbox{etc.} \] The following quantifiers are necessary for our investigations.

Definition: Let \( p(x) \) be a propositional formula depending on a variable \( x \) from a set \( X. \) Then we define the universal quantifier \( \forall \) and the existential quantifier \( \exists \) as follows:

„There exists“ means that there is at least one element \( x \) from \( X, \) and there could be more elements than only one.

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

Video tutorium

1.1.5 Aufgaben

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

1.2.1 Characterisation of sets

We do not define the term set. Rather, we give two possibilities to characterise sets, namely,

\[ M=\{m_1,m_2,m_3,\ldots\}, \]

\[ M=\{x\in X\,:\,p(x)\}, \]

The relation \( \in \) is a dichotomy in the following sense \[ \mbox{either}\quad x\in X\quad\mbox{or}\quad\neg(x\in X), \] there is no third possibility, and so, for example, the proposition \[ p(x)\,:\,(x\in X)\wedge(x\not\in X), \] where \( x\not\in X \) means \( \neg(x\in X), \) is a contradiction.

Examples:

Specifying the elements:

Specifying a defining property:

The relation \( = \) between two set is defined in → this paragraph.

The empty set \( \emptyset \) contains no element by agreement. It is a subset of every set, see → this paragraph. The Zermelo-Fraenkel axiomatic set theory ensures the existence of one and only one empty set. In particular, \[ \{x\in X\,:\,p(x)\} \] is a possible representation of the empty set if \( p(x) \) is contradictory. Every set other than the empty set contains at least one element.

A set is called finite if the number of its elements is a finite number. Otherwise it is called infinite.

Exercise:

Determine the elements of the following sets.

Video tutorial

1.2.2 Set relations and set operations

We begin with the following set relations.

Definition: Let \( A \) and \( B \) be two arbitrary sets. Then we write

where \( A\not= B \) means \( \neg(A=B). \)

Set equality \( A=B \) can be expressed using the subset relation \[ A=B\quad\mbox{if and only if}\quad A\subseteq B\ \mbox{and}\ B\subseteq A. \] Finally, \( A\supseteq B \) means \( B\subseteq A \) and \( A\supset B \) means \( B\subset A. \)

Now we come to basic set operations.

Definition: Let \( A \) and \( B \) be two arbitrary sets. Then we define their union, their intersection, and their difference as

Example: Let the set \( \Omega=\{0,1,2,3,4,5,6\} \) be given together with the subsets \[ A=\{1,2,3\}\,,\quad B=\{2,3,4\}\,. \] Then we determine

Definition: Let \( A \) and \( B \) be two arbitrary sets. Then we define their cartesian product as \[ A\times B:=\{(x,y)\,:\,x\in A,\ y\in B\}\,. \]

The symbol \( a:=b \) means that the new term \( a \) is defined as the known term \( b. \)

Example: The cartesian product of the set \( A=\{1,2,3\} \) and \( B=\{a,b\} \) ist \[ A\times B=\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}\,. \]

Definition: Let \( A\subseteq X \) be a subset of a superset \( X. \) Then we define the complement of \( A \) w.r.t. \( X \) as \[ A^c:=\{x\,:\,x\in X\setminus A\} \]

Union, intersection, difference, cartesian product and complement of sets are again sets.

Video tutorial

1.2.3 Idempotence, commutativity, associativity

We begin with the following idempotence laws of set theory.

Proposition: Let \( A \) be an arbitrary set. Then there hold

Proof: We use the idempotence laws of propositional logic from → this paragraph to calculate \[ A\cup A =\{x\,:\,x\in A\vee x\in A\} =\{x\,:\,x\in A\} =A, \] and this shows (i), and, analogously, \[ A\cap A =\{x\,:\,x\in A\wedge x\in A\} =\{x\,:\,x\in A\} =A, \] and this is (ii). The proposition is proved.\( \qquad\Box \)

Next we prove that the operators \( \cup \) and \( \cap \) are commutative.

Proposition: Let \( A \) and \( B \) be two arbitrary set. Then there hold

Proof: The commutative laws of propositional logic from → this paragraph yield \[ A\cup B =\{x\,:\,x\in A\vee x\in B\} =\{x\,:\,x\in B\vee x\in A\} =B\cup A, \] and this shows (i), and, analogously, \[ A\cap B =\{x\,:\,x\in A\wedge x\in B\} =\{x\,:\,x\in B\wedge x\in A\} =B\cap A, \] and this is (ii). The proposition is proved.\( \qquad\Box \)

There also hold the associative laws of set theory.

Proposition: Let \( A, \) \( B \) and \( C \) be two arbitrary set. Then there hold

Proof: It is enough to prove (i). Using the associative rules from → this paragraph we get \begin{align} (A\cup B)\cup C &= \{x\,:\,x\in A\vee x\in(A\cup B)\vee x\in C\} \\[0.6ex] &= \{x\,:\,x\in(A\cup B)\cup C\} \\[0.6ex] &= \{x\,:\,x\in A\cup(B\cup C)\} \\[0.6ex] &= \{x\,:\,x\in A\vee x\in(B\cup C)\} \\[0.6ex] &= A\cup(B\cup C) \end{align} Part (ii) can be proved analogously.\( \qquad\Box \)

Exercise: Let \( A, \) \( B, \) \( C \) be arbitrary sets. Prove \[ (A\cap B)\cap C=A\cap(B\cap C). \]

Video tutorial

1.2.4 Operations with the empty set

We represent the empty set \( \emptyset \) by a set \[ \{x\,:\,q(x)\} \] with a contradiction \( x, \) i.e. \( q(x) \) is false for all possible \( x. \) Now, if \( p(x) \) denotes any proposition, we have \[ p(x)\vee q(x)\equiv p(x),\quad p(x)\wedge q(x)\equiv q(x) \] which can be proved by means of truth tables.

Proposition: Let \( A \) be an arbitrary set. Then there hold

Proof: Let \( \emptyset \) be represented by \( \{x\,:\,q(x)\} \) with a contradiction \( q(x). \)

\[ A\cup\emptyset=\{x\,:\,x\in A\vee q(x)\}=\{x\,:\,x\in A\}=A, \]

\[ A\cap\emptyset=\{x\,:\,x\in A\wedge q(x)\}=\{x\,:\,q(x)\}=\emptyset\,, \]

This proves the proposition.\( \qquad\Box \)

Propostion: Let \( A \) be an arbitrary set. Then there hold

Proof:

\[ \{x\,:\,(x\in A)\wedge(x\not\in A)\} \]

\[ A\setminus A=\{x\,:\,(x\in A)\wedge(x\not\in A)\}=\emptyset\,. \]

\[ p(x)\wedge\neg q(x)\equiv p(x) \]

\[ A\setminus\emptyset =\{x\,:\,(x\in A)\wedge\neg q(x)\} =\{x\,:\,x\in A\} =A. \] This proves the proposition.\( \qquad\Box \)

Exercise: Let \( A\subseteq X \) be a subset of a superset \( X, \) and let \( A^c \) denote the complement of \( A \) w.r.t. \( X. \) Prove:

Video tutorial

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