Foundations

Mathematical Logic

Set Theory

Mathematical Logic

Propositions and Formulas

Mathematics begins with the

This agreement contains undefined terms: colloquial statement, true and false, which we do not explain more precisely. This means that our agreement is not a mathematical definition.

Our agreement contains the following principle of bivalence of propositional logic:

Examples:

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

The first statement is true, the second is false. Therefore, both statements are propositions. We do not know wether the third statement is true or false but we are convinced that it is either true or false. Thus, it also represents a statement.

We can not attribute true or false to any statement or sentence. This explicitely includes congratulations, questions, and requests, for example:

• Happy birthday!
• How are you?
• Let us go to the lecture!

But it also includes terms like

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

that we call formulas. A formula becomes a proposition if we replace the placeholder \( x \) with a number what makes \( x+7=28 \) true or false, or if we interpret \( {\mathcal R}(x,y,z) \) as the mathematical relation \( x\lt y\lt z, \) and, for example, this makes \( {\mathcal R}(0,3,1) \) false.

Connecting Propositions

We denote propositions with small letters \( a, \) \( b, \) \( c \) etc. Each proposition has one and only one thruth value

We can connect propositions to new propositions by applying the connectives \[ \neg\,,\quad \vee\,,\quad \wedge\,,\quad \to\,,\quad \leftrightarrow\,. \] In this order, the connectives are called

We define their actions by means of a truth table:

The equivalence \( \leftrightarrow \) can be written using \( \to \) as follows \[ a\leftrightarrow b\quad\text{if and only if}\quad a\to b\ \text{and}\ b\to a. \]

For example, it holds \[ (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:

Round brackets reflect the order in which the connectives are to be performed. Otherwise, we agree upon their actions from the highest to the lowest priority as follows \[ \neg,\quad\wedge,\quad\vee,\quad\to,\quad\leftrightarrow. \]

Propositional calculation rules

We present some important calculation rules of propositional logic. Here is our first

These rules can be proved using truth tables. We omit a proof and leave it as an exercise. Similarly, the following merging rules for disjunction and conjunction can be justified \[ a\equiv a\wedge(a\vee b),\quad a\equiv a\vee(a\wedge b). \] Without refering to truth tables, we want to derive an important converse of the implication, the so-called law of contraposition (see next subsection): \[ a\to b\equiv\neg a\vee b\equiv b\vee\neg a\equiv\neg(\neg b)\vee\neg a\equiv\neg b\to\neg a. \] Finally, we state the de Morgan rules of propositional logic.

Propositional principles of proof

For example, the proposition \[ a\vee\neg a \] is a tautology, or we say it is tautological, since it is always true regardless of the truth values \( 0 \) or \( 1 \) of the variable \( a. \)

By means of truth tables we can prove our next

Diese Beweisprinzipien sind in der Analysis von besonderer Bedeutung, und wir werden sie wieder und immer wieder anwenden. Wir wollen vier dieser Schlussweisen in Worten formulieren:

Eine weitere, für die Analysis wichtige Tautologie ist \[ (a\to b)\wedge(a\to\neg b)\to\neg a. \] Folgen \( b \) und \( \neg b \) gleichzeitig aus \( a, \) so muss \( a \) falsch sein. Diesen Schluss nennt man auch reductio ad absurdum.

Kontrapositionen

Keine Tautologie stellt die folgende Aussage dar \[ (a\to b)\vee(b\to c)\to(a\to c), \] welche sich vom Satz zum modus barbara durch die links stehende Disjunktion statt einer Konjunktion unterscheidet. Ihr Wahrheitswert ist \( 0 \) oder \( 1, \) abhängig von der Belegung der Variablen \( a, \) \( b \) und \( c. \)

Kontrapositionen gehen durch Negieren in Tautologien über, wie beispielsweise \[ \neg(a\wedge\neg a)\equiv a\vee\neg a, \] worin die Kontraposition \( a\wedge\neg a \) übergeht in die Tautologie \( a\vee\neg a. \)

Set Theory

Charakterisierung von Mengen

Den Begriff einer Menge werden wir nicht definieren, sondern wir geben nur zwei mögliche Charakterisierungen von Mengen:

Die Relation \( \in \) ist eine Dichotomie in folgendem Sinn \[ \text{entweder}\quad x\in X\quad\text{oder}\quad\neg(x\in X), \] eine dritte Möglichkeit gibt es nicht. Beispielsweise stellt so die Aussage \[ p(x)\,:\,(x\in X)\wedge(x\not\in X), \] worin \( x\not\in X \) für \( \neg(x\in X) \) steht, eine Kontradiktion dar.

Beispiele:

Durch Angabe der Elemente:

Durch Angabe einer charakterisierenden Eigenschaft:

Eine Menge heißt endlich, falls die Anzahl ihrer Elemente endlich ist. Andernfalls heißt die Menge unendlich.

Mengenrelationen und Mengenoperationen

Wir beginnen mit den folgenden Mengenrelationen.

Die Mengengleichheit \( A=B \) kann durch die Teilmengenrelation wie folgt ausgedrückt werden \[ A=B\quad\text{genau dann, wenn}\quad A\subseteq B\ \text{und}\ B\subseteq A. \] Schließlich verstehen wir \( A\supseteq B \) als \( B\subseteq A \) und \( A\supset B \) als \( B\subset A. \)

Nun kommen nun zu wichtigen Mengenoperationen.

Beispiel: Gegeben sei die Menge \( \Omega=\{0,1,2,3,4,5,6\} \) mit den zwei Teilmengen \[ A=\{1,2,3\}\,,\quad B=\{2,3,4\}\,. \] Dann bestimmen wir

Wir benötigen ebenfalls noch die

Das Symbol \( a:=b \) bedeutet, dass \( a \) definiert ist in Termen von \( b. \)

Beispiel: Das kartesische Produkt der Mengen \( A=\{1,2,3\} \) und \( B=\{a,b\} \) lautet \[ A\times B=\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}\,. \]

Bewegen sich unsere sämtlichen Untersuchungen innerhalb einer Obermenge \( X, \) so verwenden wir auch häufig die Schreibweise \[ A^c:=\{x\,:\,x\in X\setminus A\} \] für das Komplement von \( A \) bez. \( X. \)

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

Idempotenz, Kommutativität, Assoziativität;

Unter Benutzung der Resultate → aus diesem Paragraphen kommen wir zum

Operationen mit der leeren Menge

Wir stellen die leere Menge \( \emptyset \) dar in der Form \[ \{x\,:\,q(x)\} \] mit einer Kontradiktion \( q(x), \) d.h. für alle möglichen \( x \) ist \( q(x) \) falsch. Bezeichnet nun \( p(x) \) eine von \( x \) abhängige Aussage, so verifiziert man sofort vermittels einer Wahrheitstabelle \[ p(x)\vee q(x)\equiv p(x),\quad p(x)\wedge q(x)\equiv q(x) \]

Rechenregeln für Mengen

Wir verwenden die aus der Aussagenlogik bekannten Distributionsgesetze \[ 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) \] um folgende Rechenregeln für Mengen zu gewinnen.

Auch die de Morganschen Regeln lassen sich auf Mengen übertragen, wie man als Übung zeigt.

Abbildungen zwischen Mengen

Wir betrachten nun Abbildungen \( f\colon A\to B. \)

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

\[ f(A):=\{b\in B\,:\,\text{es existiert ein}\ a\in A\ \text{mit}\ f(a)=b\}\,; \]

Eine bijektiv Abbildung \( f\colon A\to B \) ordnet jedem Element \( a\in A \) genau ein Element \( b\in B \) zu, und umgekehrt kann jedes \( b\in B \) auf genau ein \( a\in A \) abgebildet werden vermittels der inversen Abbildung \[ f^{-1}\colon B\longrightarrow A. \] Die inverse Abbildung besitzt die charakteristischen Eigenschaften \[ \begin{array}{ll} f^{-1}\circ f(a):=f^{-1}(f(a))=a & \quad\text{für alle}\ a\in A, \\[0.6ex] f\circ f^{-1}(b):=f(f^{-1}(b))=b & \quad\text{für alle}\ b\in B. \end{array} \]

Gleichmächtige Mengen

Als die Mächtigkeit einer endlichen Menge \( A \) mit Elementen \( a_1,\ldots,a_n \) verstehen wir die Anzahl \( n \) ihrer Elemente, in Zeichen \[ |A|=n. \] Um die Mächtigkeit einer unendlichen Menge zu definieren, benötigen wir weitere Vorarbeiten, mit denen wir an dieser Stelle beginnen wollen.

Beispielsweise existiert eine Bijektion der natürlichen Zahlen \( \mathbb N \) und der Menge aller geraden Zahlen \( 2\mathbb N \) \[ \begin{array}{l} f\colon\mathbb N\longrightarrow 2\mathbb N \quad\text{vermöge}\quad f(n):=2n,\ n=1,2,3,\ldots \\[1ex] \displaystyle \text{mit der Inversen}\quad f^{-1}(m):=\frac{m}{2}\,,\ m=2,4,6,\ldots \end{array} \] Hierauf werden wir in den Übungen und auch bei der Bestimmung der Mächtigkeit der rationalen Zahlen genauer eingehen. Für den Moment genügt uns die folgende

In unserem Beispiel sind also die Mengen \( \mathbb N \) und \( 2\mathbb N \) gleichmächtig. Es macht keinen Sinn, von mehr oder von weniger Elementen zu sprechen, da beide Mengen nicht von endlicher Mächtigkeit sind.

Die Potenzmenge

Beispielsweise haben wir \[ {\mathcal P}(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\}\,, \] denn \( \emptyset, \) \( \{1\}, \) \( \{2\} \) und \( \{1,2\} \) sind alle vier möglichen Teilmengen von \( \{1,2\}. \) Beachte, dass die leere Menge \( \emptyset \) nach unserer Vereinbarung Teilmenge jeder Menge ist.

Ferner gilt für endliche Mengen stets \[ |A|\lt|{\mathcal P}(A)|=2^{|A|}\,, \] wovon wir uns als Übung überzeugen wollen.

Der Satz von Cantor-Bernstein-Schröder

Hierbei geht es um den folgenden

Wir betrachten als Beispiel die beiden reellen Zahlenintervalle \[ \begin{array}{l} A=(-1,1):=\{x\in\mathbb R\,:\,-1\lt x\lt 1\}\,, \\[0.8ex] B=[-1,1]:=\{x\in\mathbb R\,:\,-1\le x\le 1\}\,. \end{array} \] Die Abbildungen \[ \begin{array}{l} \displaystyle f\colon(-1,1)\longrightarrow[-1,1]\quad\text{vermöge}\ f(a):=a, \\[1.0ex] \displaystyle g\colon[-1,1]\longrightarrow(-1,1)\quad\text{vermöge}\ g(b):=\frac{b}{2}\,. \end{array} \] sind injektiv, d.h. nach dem Satz von Cantor-Bernstein-Schröder sind \( (-1,1) \) und \( [-1,1] \) gleichmächtig.

Der Satz von Cantor

Eine Menge \( A \) ist nie gleichmächtig zu ihrer Potenzmenge \( {\mathcal P}(A). \) Im Fall endlicher Mengen gilt, wie wir oben bemerkt haben, \[ |A|\lt|{\mathcal P}^{|A|}=2^{|A|}\,. \] Die Potenzmenge \( {\mathcal P}(A) \) einer endlichen Menge \( A \) ist also stets mächtiger als \( A \) selbst. Eine analoge Aussage gilt nun für alle Mengen im folgenden Sinne:

Es existiert also auch keine bijektive Abbildung \( f\colon A\to{\mathcal P}(A). \) Wir sagen auch hier, dass die Potenzmenge \( {\mathcal P}(A) \) mächtiger ist also die Menge \( A \) selbst.

Quantoren

In der Mathematik arbeiten wir mit Variablen \( x,y,\ldots \) als Elemente von Mengen \( X,Y,\ldots \)

„Es existiert“ bedeutet, dass es wenigstens ein Element \( x\in X \) mit der geforderten Eigenschaft gibt, aber natürlich kann es auch mehrere solche Elemente geben.

Beispiel: Die Funktion \( f\colon\Omega\to\mathbb R \) heißt im Punkt \( x_0\in\Omega \) stetig, falls \[ \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) \] oder in Worten:

Für alle \( \varepsilon\gt 0 \) existiert ein \( \delta\gt 0, \) so dass \[ |f(x)-f(x_0)|\lt\varepsilon\quad\text{für alle}\ x\in\Omega\ \text{mit}\ |x-x_0|\lt\delta. \]

Hierin benötigen wir vier Variablen \( x, \) \( x_0, \) \( \delta \) und \( \varepsilon. \) Wir sagen, dass \( x, \) \( \varepsilon \) und \( \delta \) durch einen Quantor gebunden sind, während \( x_0 \) frei ist.

Die Relationen \( \in \) und \( \lt \) sind Beispiele sogenannter Prädikate.

Der Operator \( \neg \) auf der jeweils linken Seite wirkt dabei auf die gesamten Formel \( \forall x\,p(x) \) bzw. \( \exists x\,p(x). \) Beispielsweise ermittelt man \[ \neg\forall x\,\exists y\,p(y)\equiv\exists x\,\neg\exists y\,p(y)\equiv\exists x\forall y\,\neg p(y). \]