2. Elementary number systems | 3. Real and complex numbers | 4. Theory of series |
5. Continuous functions | 6. Differentiable functionen | 7. Integrable functions |
1. Foundations
1.1.1 Propositions and propositional formulas
Mathematics starts 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 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 statement. This concerns in particular congratulations, questions, requests and so on, for example:
Mathematical expressions, such as
are called (propositional) formulas. Such 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.
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
\( \neg \) | Negation | not | |
\( \vee \) | Disjunction | or | |
\( \wedge \) | Conjunction | say: | and |
\( \to \) | Implication | if ... then | |
\( \leftrightarrow \) | Equivalence | if and only if |
We define the meaning of this connectives by means of the following truth table:
\( a \) | \( b \) | \( \neg a \) | \( \neg b \) | \( a\wedge b \) | \( a\vee b \) | \( a\to b \) | \( b\to a \) | \( a\leftrightarrow b \) |
\( 0 \) | \( 0 \) | \( 1 \) | \( 1 \) | \( 0 \) | \( 0 \) | \( 1 \) | \( 1 \) | \( 1 \) |
\( 0 \) | \( 1 \) | \( 1 \) | \( 0 \) | \( 0 \) | \( 1 \) | \( 1 \) | \( 0 \) | \( 0 \) |
\( 1 \) | \( 0 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) | \( 0 \) |
\( 1 \) | \( 1 \) | \( 0 \) | \( 0 \) | \( 1 \) | \( 1 \) | \( 1 \) | \( 1 \) | \( 1 \) |
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:
\( a \) | \( b \) | \( a\to b \) | \( \neg a \) | \( \neg a\vee b \) |
\( 0 \) | \( 0 \) | \( 1 \) | \( 1 \) | \( 1 \) |
\( 0 \) | \( 1 \) | \( 1 \) | \( 1 \) | \( 1 \) |
\( 1 \) | \( 0 \) | \( 0 \) | \( 0 \) | \( 0 \) |
\( 1 \) | \( 1 \) | \( 1 \) | \( 0 \) | \( 1 \) |
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
(i) | \( a\wedge(b\vee c)\equiv(a\wedge b)\vee(a\wedge c) \) |
(ii) | \( a\vee(b\wedge c)\equiv(a\vee b)\wedge(a\vee c) \) |
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
(i) | \( a\to b\equiv \neg a\vee b \) |
(ii) | \( a\to b\equiv \neg b\to\neg a \) |
(iii) | \( a\leftrightarrow b\equiv(a\vee\neg b)\wedge(\neg a\vee b) \) |
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
(i) | \( \neg(a\wedge b)\equiv\neg a\vee\neg b \) |
(ii) | \( \neg(a\vee b)\equiv\neg a\wedge\neg b \) |
Exercise: Proof all the above propositions by means of truth tables.
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:
\( \circ \) | Law of the excluded middle | \( a\vee\neg a \) |
\( \circ \) | Law of contradiction | \( \neg(a\wedge\neg a) \) |
\( \circ \) | Law of double negation | \( \neg(\neg a)\to a \) |
\( \circ \) | Law of contraposition | \( (a\to b)\leftrightarrow(\neg b\to\neg a) \) |
\( \circ \) | Law of modus ponens | \( (a\to b)\wedge a\to b \) |
\( \circ \) | Law modus tollens | \( (a\to b)\wedge\neg b\to\neg a \) |
\( \circ \) | Law of modus barbara | \( (a\to b)\wedge(b\to c)\to(a\to c) \) |
We want to clarify the following four principle in our own words:
\( \circ \) | Law of the excluded middle |
either \( a \) holds true, or \( a \) does not hold true; there is no third possibility | |
\( \circ \) | Law of contradiction |
a proposition \( a \) and its negation \( \neg a \) can not be true simultaneously | |
\( \circ \) | Law of modus ponens |
if \( a \) is true and \( b \) follows from \( a, \) then \( b \) is true; this is what we call a direct proof, \( b \) follows directly from \( a \) | |
\( \circ \) | Law of modus tollens |
if \( \neg b \) is true, but \( b \) follows from \( a, \) then \( a \) is false; this is what we call a proof of the contrapositive, a special form of an indirect proof |
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.
(i) | \( a\vee(b\wedge\neg b)\to a \) |
(ii) | \( a\wedge(b\vee\neg b)\to a \) |
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:
\( \circ \) | \( \forall x\in X\,p(x) \) |
\( p(x) \) is true for all elements \( x \) from \( X \) | |
\( \circ \) | \( \exists x\in X\,p(x) \) |
there exists an element \( x \) from \( X \) such that \( p(x) \) is true |
„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). \]
Problems for Propositions and propositional formulas
Problem 1.1.1: (Examples of propositions)
Which of the following statements are propositions, and which are not propositions?
(i) | Berlin is the capital of Germany. |
(ii) | All students work hard. |
(iii) | It rained all day yesterday. |
(iv) | Travel broadens the mind. |
(v) | The class has already started. |
(vi) | Mathematics is really difficult? |
Problem 1.1.2: (Own examples of propositions)
Formulate at least
(i) | five own examples of propositions, |
(ii) | five own examples of linguistic statements which are not propositions. |
Problem 1.1.3: (Propositional formulas)
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
(i) | \( {\mathcal R}(6) \) is true, |
(ii) | \( {\mathcal S}(1,7) \) is true, |
(iii) | \( {\mathcal T}(1,3,12) \) is true. |
Aufgaben zu Logische Paradoxien
Aufgabe 1.1.4: (Die Lügnerparadoxie)
In dem Brief des Paulus an Titus (Der notwendige Kampf gegen Irrlehren) lesen wir (Zitat nach Wikipedia, Die freie Enzyklopädie, Seite „Paradoxon des Epimenides“):
Es hat einer von ihnen gesagt, ihr eigener Prophet: Die Kreter sind immer Lügner, böse Tiere und faule Bäche.
Im Jahre 1908 greift B. Russell dieses Zitat wieder auf:
The oldest contradiction of the kind in question is the Epimenides. Epimenides the Cretan said that all Cretans were liars, and all other statements made by Cretans were certainly lies. Was this a lie?
Das ist die Quelle einer der bekanntesten logischen Paradoxien: Alle Kreter lügen (siehe T. Zoglauer, Seite 16). Diskutieren Sie diese Paradoxie.
Aufgabe 1.1.5: (Russells Barbier-Paradoxie)
In B. Russel, Seite 101, finden wir folgende Paradoxie:
I once had a form suggested to me which was not valid, namely the question whether the barber shaves himself or not. You can define the barber as "one who shaves all those, and those only, who do not shave themselves." The question is, does the barber shave himself? In this form the contradiction is not very difficult to solve ...
Wie nämlich ist dieser Widerspruch auflösbar?
Aufgabe 1.1.6: (Zoglauers Kannibalen-Paradoxie)
Aus T. Zoglauer, Abschnitt 1.2, entnehmen wir das folgende Beispiel einer Paradoxie:
Ein Reisender gerät unter Kannibalen, die ihn gefangen nehmen und anschließend zur Bereicherung ihres Speiseplanes essen wollen. Die Kannibalen sind sich nur noch nicht einig, wie sie ihn zubereiten sollen. Sie bieten ihm an, er könne irgendeine Aussage machen. Wenn die Aussage wahr ist, werde er gekocht, und wenn sie falsch ist, werde er geröstet ... Daher wird der Reisende entweder gekocht oder geröstet, aber dem unstillbaren Hunger der Kannibalen scheint er nicht entkommen zu können. Trotzdem fand der Reisende einen logischen Ausweg ... Seine Aussage lautet: „Das, was ich jetzt sage, ist falsch.“ Dieser Satz stürzte die Kannibalen in große Verwirrung ...
Was könnte die Kannibalen denn in Verwirrung gebracht haben?
Aufgabe 1.1.7: (Ein einfaches Beispiel zur Selbstbezüglichkeit)
Ein weiteres Beispiel aus T. Zoglauer, Seite 16, lautet:
Welche drei Fehler sind gemeint?
Aufgaben zu Verknüpfungen von Aussagen
Aufgabe 1.1.8: (Doppelte Verneinung)
Beweisen Sie die aussagenlogische Äquivalenz \[ \neg\neg a\equiv a. \]
Aufgabe 1.1.9: (Idempotenzgesetze der Aussagenlogik)
Beweisen Sie die folgenden aussagenlogischen Äquivalenzen:
(i) | \( a\equiv a\vee a \) |
(ii) | \( a\equiv a\wedge a \) |
Aufgabe 1.1.10: (Äquivalenzen der Implikation)
Beweisen Sie die folgenden aussagenlogischen Äquivalenzen:
(i) | \( a\to b\equiv \neg a\vee b a \) |
(ii) | \( a\to b\equiv \neg b\to\neg a \) |
(iii) | \( a\leftrightarrow b\equiv(a\vee\neg b)\wedge(\neg a\vee b) \) |
Aufgabe 1.1.11: (Kommutativität der Disjunktion und Konjunktion)
Beweisen Sie die folgenden aussagenlogischen Äquivalenzen:
(i) | \( a\vee b\equiv b\vee a \) |
(ii) | \( a\wedge b\equiv b\wedge a \) |
Aufgabe 1.1.12: (Assoziativgesetze der Aussagenlogik)
Beweisen Sie die folgenden aussagenlogischen Äquivalenzen:
(i) | \( a\vee(b\vee c)\equiv(a\vee b)\vee c \) |
(ii) | \( a\wedge(b\wedge c)\equiv(a\wedge b)\wedge c \) |
Aufgabe 1.1.13: (Distributivgesetze der Aussagenlogik)
Beweisen Sie die folgenden aussagenlogischen Äquivalenzen:
(i) | \( a\wedge(b\vee c)\equiv(a\wedge b)\vee(a\wedge c) \) |
(ii) | \( a\vee(b\wedge c)\equiv(a\vee b)\wedge(a\vee c) \) |
Aufgabe 1.1.14: (Verschmelzung von Disjunktion und Konjunktion)
Beweisen Sie die folgenden aussagenlogischen Äquivalenzen:
(i) | \( a\equiv a\wedge(a\vee b) \) |
(ii) | \( a\wedge a\vee(a\wedge b) \) |
Aufgabe 1.1.15: (de Morgansche Regeln der Aussagenlogik)
Beweisen Sie die folgenden aussagenlogischen Äquivalenzen:
(i) | \( \neg(a\wedge b)\equiv\neg a\vee\neg b \) |
(ii) | \( \neg(a\vee b)\equiv\neg a\wedge\neg b \) |
Aufgaben zu Aussagenlogische Beweisprinzipien
Aufgabe 1.1.16: (Kontradiktionen)
Beweisen Sie, dass das Negieren einer Tautologie zu einer Kontradiktion führt und umgekehrt.
Aufgabe 1.1.17: (Beispiele aussagenlogischer Tautologien I)
Beweisen Sie die folgenden aussagenlogischen Tautologien:
(i) | \( a\vee(b\wedge\neg b)\to a \) |
(ii) | \( a\wedge(b\vee\neg b)\to a \) |
Die Aussage (ii) bezeichnet man auch als reductio ad absurdum.
Aufgabe 1.1.18: (Beispiele aussagenlogischer Tautologien II)
Beweisen Sie die folgenden aussagenlogischen Tautologien:
(i) | Satz vom ausgeschlossenen Dritten | \( a\vee\neg a \) |
(ii) | Satz vom Widerspruch | \( \neg(a\wedge\neg a) \) |
(iii) | Satz von der doppelten Verneinung | \( \neg(\neg a)\to a \) |
(iv) | Satz von der Kontraposition | \( (a\to b)\to(\neg b\to\neg a) \) |
Aufgabe 1.1.19: (Tautologien I)
Beweisen Sie die folgenden aussagenlogischen Tautologien:
(i) | Satz zum modus ponens | \( (a\to b)\wedge a\to b \) |
(ii) | Satz zum modus tollens | \( (a\to b)\wedge\neg b\to\neg a \) |
(iii) | Satz zum modus barbara | \( (a\to b)\wedge(b\to c)\to(a\to c) \) |
Aufgabe 1.1.20: (Beispiele aussagenlogischer Taugologien II)
Beweisen Sie die folgenden aussagenlogischen Tautologien:
(i) | Kompressionsregel | \( a\vee a\to a \) |
(ii) | Expansionsregel | \( a\to a\vee b \) |
(iii) | Schnittregel | \( (a\vee b)\wedge(\neg a\vee c)\to(b\vee c) \) |
Aufgabe 1.1.21: (Beispiele aussagenlogischer Tautologien III)
Beweisen Sie die folgenden aussagenlogischen Tautologien:
(i) | \( a\to((a\to b)\to b) \) |
(ii) | \( a\to(b\to(a\to b)) \) |
(iii) | \( \neg(a\to a)\to b \) |
(iv) | \( \neg(a\to b)\to\neg b \) |
(v) | \( \neg(a\to b)\to a \) |
Aufgabe 1.1.22: (Schlussregeln der Aussagenlogik)
Es seien \( \varphi(a_1,\ldots,a_n) \) und \( \psi(a_1,\ldots,a_n) \) aussagenlogische Formeln in Abhängigkeit der \( n \) Variablen \( a_1,\ldots,a_n. \) Über eine Abbildung \[ I\colon\{a_1,\ldots,a_n\}\longrightarrow\{0,1\} \] weisen wir den \( a_i \) die Wahrheitswerte \( 0 \) oder \( 1 \) zu. Nimmt \( \varphi \) für ein spezielles \( I(a_1,\ldots,a_n) \) den Wahrheitswert \( 1 \) an, so heißt \( I \) ein Modell für \( \varphi, \) i.Z. \[ I\models\varphi. \] Wir schreiben \( \varphi\models\psi \) genau dann, wenn jedes Modell von \( \varphi \) auch Modell von \( \psi \) ist.
(i) | Beweisen Sie, dass gilt |
|
Entsprechendes gilt im Fall \( \{\varphi_1,\ldots,\varphi_m\}\models\psi, \) falls also \( I(a_1,\ldots,a_n) \) als gleichzeitiges Modell aller \( \varphi_i \) auch Modell von \( \psi \) ist. Das in (i) formulierte semantische Deduktionstheorem identifiziert die semantische Folgerung \( \models \) mit dem syntaktischen Implikationsoperator \( \to. \) Eine semantische Schlussregel bildet nun eine semantische Ersetzung vorausgesetzter und wahrer Formeln \( \varphi_1,\ldots,\varphi_m \) durch eine zu schließende Formel \( \psi, \) wobei gelten soll \( \{\varphi_1,\ldots,\varphi_m\} \models\psi, \) i.Z. \[ \frac{\{\varphi_1,\ldots,\varphi_m\}}{\psi}\,, \] also beispielsweise \[ \frac{a\to b,\,b}{b}\quad\mbox{für den modus ponens.} \]
(ii) | Formulieren Sie die Tautologien aus vorigem Satz als semantische Schlussregeln. |
Aufgabe 1.1.23: (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?
(i) | Es existieren ein \( x\in\mathbb Z \) und ein \( y\in\mathbb Z \) mit \( x+y=0. \) |
(ii) | Für alle \( x\in\mathbb Z \) existiert ein \( y\in\mathbb Z \) mit \( x+y=0. \) |
(iii) | Es existiert ein \( x\in\mathbb Z, \) so dass für alle \( y\in\mathbb Z \) gilt \( x+y=0. \) |
(iv) | Für alle \( x\in\mathbb Z \) und für alle \( y\in\mathbb Z \) gilt \( x+y=0. \) |
Aufgabe 1.1.24: (Negation der Stetigkeit)
Negieren Sie obige prädikatenlogische Formel der Stetigkeit einer Funktion in einem Punkt \( x_0\in\Omega. \)
Aufgabe 1.1.25: (Offene Mengen)
Es sei \( X \) eine Menge mit einer Abstandsfunktion \( d\colon X\times X\to\mathbb R. \) Eine Teilmenge \( \Omega\subset X \) heißt offen, wenn für jedes \( x\in\Omega \) ein \( \varepsilon>0 \) existiert, so dass gilt \( y\in\Omega \) für alle \( y\in X \) mit \( d(x,y)\lt\varepsilon. \)
(i) | Schreiben Sie diese Bedingung als prädikatenlogische Formel. |
(ii) | Negieren Sie diese Formel. |
Aufgabe 1.1.26: (Lebesguemessbare Funktionen)
Eine Funktion \( f\colon\Omega\subseteq\mathbb R^n\to\mathbb R \) heißt Lebesguemessbar, i.Z. \( f\in\mathcal L(\Omega^n,\mathbb R), \) falls die Mengen \[ \Omega_\lambda:=\{x\in\Omega\,:\,f(x)>\lambda\} \] für alle \( \lambda\in\mathbb R \) Lebesguemessbar sind, i.Z. \( \Omega_\lambda\in\mathcal L(\mathbb R^n). \)
(i) | Schreiben Sie diese Bedingung als prädikatenlogische Formel. |
(ii) | Negieren Sie diese Formel. |
Aufgabe 1.1.27: (Analytische Geometrie)
Es bedeute \( \mathcal L \) die Menge aller Geraden in der Ebene. Formulieren Sie als prädikatenlogische Formel:
\( \to \) | Zwei Geraden schneiden sich in genau einem Punkt, oder sie sind parallel und durchschnittsfremd, |
oder sie sind gleich. |
1. | Was versteht man unter einer Aussage? |
2. | Was versteht man unter der Zweiwertigkeit der Aussagenlogik? |
3. | Wie sind die Junktoren \( \neg, \) \( \wedge, \) \( \vee, \) \( \to \) und \( \leftrightarrow \) definert? |
4. | Wann heißen zwei Aussagen äquivalent? |
5. | Was versteht man unter einer Tautologie? |
6. | Wie lautet der Satz vom ausgeschlossenen Dritten? |
7. | Wie lautet der Satz vom Widerspruch? |
8. | Wie lautet der Satz von der doppelten Verneinung? |
9. | Wie lautet der Satz von der Kontraposition? |
10. | Wie lautet der Satz zum modus ponens? |
11. | Wie lautet der Satz zum modus tollens? |
12. | Wie lautet der Satz zum modus barbara? |
13. | Wie wurden der Allquantor \( \forall \) und der Existenzquantor \( \exists \) eingeführt? |
14. | Wie werden die Quantoren \( \forall \) und \( \exists \) negiert? |
1.2.1 Characterisation of sets
We do not define the term set. Rather, we give two possibilities to characterise sets, namely,
\( \circ \) | by specifying their elements \( m_1, \) \( m_2, \) \( m_3 \) etc., and then we write |
\[ M=\{m_1,m_2,m_3,\ldots\}, \]
where the order of the elements does not have to be considered; | |
\( \circ \) | by specifying a defining property, for example |
\[ M=\{x\in X\,:\,p(x)\}, \]
i.e. \( M \) consists of all those elements \( x\in X \) for which \( p(x) \) is true. |
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:
(i) | The set \( M=\{1\} \) consists of the only element \( 1. \) |
(ii) | The set \( M=\{1,\{1\}\} \) consists of the both elements \( 1 \) and \( \{1\}. \) |
(iii) | The set \( \mathbb N=\{1,2,3,\ldots\} \) is the set of the natural numbers without \( 0. \) |
Specifying a defining property:
(iv) | It holds \( \{x\in\mathbb R\,:\,x^2=\sqrt{2}\}=\{\sqrt{2},-\sqrt{2}\}\,. \) |
(v) | It holds \( \{n\in\mathbb N\,:\,2^n\lt n^2\}=\{3\}\,. \) |
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.
(i) | \( M=\{(x,y)\,:\,x,y\in\mathbb N,\ 1\le x\le 17\ \mbox{and}\ x\ \mbox{is a prime number}\} \) |
(ii) | \( M=\{(x,y)\,:\,x,y\in\mathbb N,\ x-y\ \mbox{is divisible by}\ 2\ \mbox{without remainder}\} \) |
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
\( A=B \) | \( A \) is equal to \( B \) | \( x\in A\,\leftrightarrow x\in B \) | |
\( A\subseteq B \) | \( A \) is a subset of \( B \) | \( x\in A\,\to x\in B \) | |
\( A\subset B \) | \( A \) is a proper subset of \( B \) | \( A\subseteq B\,\wedge\,A\not=B \) |
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
\( A\cup B \) | \( A \) union \( B \) | \( \{x\,:\,x\in A\vee x\in B\} \) | |
\( A\cap B \) | \( A \) intersect \( B \) | \( \{x\,:\,x\in A\wedge x\in B\} \) | |
\( A\setminus B \) | \( A \) minus \( B \) | \( \{x\,:\,x\in A\wedge x\not\in B\} \) |
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
\( \circ \) | \( \Omega\setminus A=\{0,4,5,6\} \) |
\( \circ \) | \( A\cup B=\{1,2,3,4\} \) |
\( \circ \) | \( A\cap B=\{2,3\} \) |
\( \circ \) | \( A\setminus B=\{1\} \) |
\( \circ \) | \( B\setminus A=\{4\} \) |
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.
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
(i) | \( A\cup A=A \) |
(ii) | \( A\cap A=A \) |
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
(i) | \( A\cup B=B\cup A \) |
(ii) | \( A\cap B=B\cap A \) |
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
(i) | \( (A\cup B)\cup C=A\cup(B\cup C) \) |
(ii) | \( (A\cap B)\cap C=A\cap(B\cap C) \) |
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). \]
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
(i) | \( A\cup\emptyset=A \) |
(ii) | \( A\cap\emptyset=A \) |
Proof: Let \( \emptyset \) be represented by \( \{x\,:\,q(x)\} \) with a contradiction \( q(x). \)
(i) | We compute |
\[ A\cup\emptyset=\{x\,:\,x\in A\vee q(x)\}=\{x\,:\,x\in A\}=A, \]
and this shows (i). | |
(ii) | We compute |
\[ A\cap\emptyset=\{x\,:\,x\in A\wedge q(x)\}=\{x\,:\,q(x)\}=\emptyset\,, \]
and this shows (ii). |
This proves the proposition.\( \qquad\Box \)
Propostion: Let \( A \) be an arbitrary set. Then there hold
(i) | \( A\setminus A=\emptyset \) |
(ii) | \( A\setminus\emptyset=A \) |
Proof:
(i) | The proposition \( (x\in A)\wedge(x\not\in A) \) is a contradiction and, therefore, |
\[ \{x\,:\,(x\in A)\wedge(x\not\in A)\} \]
represents the empty set. Thus, we obtain |
\[ A\setminus A=\{x\,:\,(x\in A)\wedge(x\not\in A)\}=\emptyset\,. \]
(ii) | Let \( \{x\,:\,q(x)\} \) with a contradiction \( q(x) \) represent \( \emptyset. \) Then \( \neg q(x) \) is a tautologie, and it holds |
\[ p(x)\wedge\neg q(x)\equiv p(x) \]
for any proposition \( p(x). \) Thus, we obtain |
\[ 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:
(i) | \( A\cap A^c=\emptyset \) |
(ii) | \( A\cup A^c=X \) |
(iii) | \( (A^c)^c=A \) |
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). \]
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
\( \circ \) | surjektiv, wenn für jedes \( b\in B \) ein \( a\in A \) mit \( f(a)=b \) existiert; |
\( \circ \) | injektiv, wenn \( f(a)=b \) für gegebenes \( b\in B \) höchstens eine Lösung \( a\in A \) besitzt, d.h. |
|
|
bzw. | |
|
|
\( \circ \) | bijektiv, wenn \( f \) injektiv und surjektiv ist. |
Insbesondere ist eine Abbildung \( f\colon A\to B \)
\( \circ \) | nicht surjektiv, falls es ein \( b\in B \) gibt, welches nicht im Bildraum der Funktion liegt, |
\( \circ \) | nicht injektiv, falls es \( a_1\not=a_2 \) aus \( A \) gibt mit \( f(a_1)=f(a_2). \) |
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. \)
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 - Charakterisierung von Mengen
Aufgabe 1.2.1: (Darstellung von Mengen)
Welche Elemente besitzen die folgenden Mengen?
(i) | \( M=\{(x,y)\in\mathbb N\,:\,1\le x\le 17\ \mbox{und}\ x\ \mbox{ist Primzahl}\} \) |
(ii) | \( M=\{(x,y)\in\mathbb N\times\mathbb N\,:\,x-y\ \mbox{ist ohne Rest durch}\ 2\ \mbox{teilbar}\} \) |
(iii) | \( M=\{(x,y)\in\mathbb Z\times\mathbb Z\,:\,x-y\ \mbox{ist ohne Rest durch}\ 3\ \mbox{teilbar}\} \) |
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:
(i) | \( M=\{1,2,3,4\} \) und \( N=\{a,b\} \) |
(i) | \( M=\{a,b,c\} \) und \( N=\{x,y\} \) |
(iii) | \( M=\{1,2,3,4,\ldots\} \) und \( N=\{1,2,3,4,\ldots\} \) |
(iv) | \( M=\{x\in\mathbb N\,:\,2\le x\le 3\} \) und \( N=\{x\in\mathbb N\,:\,6\le x\lt 9\} \) |
Aufgaben - Rechenregeln für Mengen
Aufgabe 1.2.4: (Distributivgesetze der Mengenlehre)
Es seien \( A, \) \( B \) und \( C \) drei beliebige Mengen. Beweisen Sie:
(i) | \( A\cap(B\cup C)=(A\cap B)\cup(A\cap C) \) |
(ii) | \( A\cup(B\cap C)=(A\cup B)\cap(A\cup C) \) |
Aufgabe 1.2.5: (de Morgansche Regeln der Mengenlehre)
Es seien \( A \) und \( B \) zwei beliebige Teilmengen einer nichtleeren Obermenge \( X. \) Beweisen Sie:
(i) | \( X\setminus(A\cup B)=(X\setminus A)\cap(X\setminus B) \) |
(ii) | \( X\setminus(A\cap B)=(X\setminus A)\cup(X\setminus B) \) |
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.
(i) | \( (A\cap C)\cup(B\cap D)\subseteq(A\cup B)\cap(C\cup D) \) |
(ii) | \( (A\cap C)\cup(B\cap D)=(A\cup B)\cap(C\cup D) \) |
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:
(i) | \( f \) ist weder injektiv noch surjektiv |
(ii) | \( f \) ist injektiv, aber nicht surjektiv |
(iii) | \( f \) ist surjektiv, aber nicht injektiv |
(iv) | \( f \) ist sowohl injektiv als auch surjektiv |
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: \)
(i) | \( M=\emptyset \) |
(ii) | \( M=\{a\} \) |
(iii) | \( M=\{a,b\} \) |
(iv) | \( M=\{a,b,c\} \) |
(v) | \( M={\mathcal P}(\emptyset) \) |
(vi) | \( M={\mathcal P}(\{a\}) \) |
Aufgabe 1.2.11: (Potenzmenge auf Vereinigung und Durchschnitt)
Es seien \( A \) und \( B \) zwei beliebige Mengen.
(i) | Zeigen Sie durch Angabe eines Gegenbeispiels, dass nicht gilt |
|
|
(ii) | Beweisen Sie die Richtigkeit der Aussage |
|
1. | Wie lassen sich Mengen charakterisieren? |
2. | Wie sind die Mengenrelationen \( =, \) \( \subseteq, \) \( \subset, \) \( \supseteq \) und \( \supset \) erklärt? |
3. | Wie sind die Mengenoperationen \( \cup, \) \( \cap, \) \( \setminus \) und \( \times \) definiert? |
4. | Was versteht man unter dem Komplement einer Menge? |
5. | Wie lauten die Distributivgesetze der Mengenlehre? |
6. | Wie lauten die de Morganschen Regeln der Mengenlehre? |
7. | Wann heißt eine Abbildung \( f\colon A\to B \) surjektiv? |
8. | Wann heißt eine Abbildung \( f\colon A\to B \) injektiv? |
9. | Wann heißt eine Abbildung \( f\colon A\to B \) bijektiv? |
10. | Wann heißt eine Menge endlich? |
11. | Was versteht man unter der Mächtigkeit einer endlichen Menge? |
12. | Wann heißen zwei Mengen gleichmächtig? |
13. | Was versteht man unter der Potenzmenge einer Menge? |
14. | Wie viele Elemente besitzt die Potenzmenge einer endlichen Menge mit \( n \) Elementen? |