In diesem Abschnitt werden einige Grundbegriffe der Mengenlehre und grundlegende Prinzipien der mathematischen Logik bereitgestellt. Für die nachfolgenden Betrachtungen benutzen wir stets den „naiven“ Mengenbegriff, wie ihn Georg Cantor geprägt hat.

Nach Cantor ist eine Menge $M$ eine Zusammenfassung bestimmter, wohlunterschiedener Objekte unserer Anschauung oder unseres Denkens (welche die Elemente von $M$ genannt werden) zu einem Ganzen.

Wie üblich benutzen wir das Symbol $\in$ um auszudrücken, daß das Element $a$ zu der Menge $M$ gehört: $a \in M$ .

Der Cantor’sche Mengenbegriff erwies sich jedoch als widersprüchlich. Um die Jahrhundertwende 1900 wurden mehrere Antinomien konstruiert. Eine – wohl die bekannteste – die 1901 von B. Russel gefunden wurde, sei hier wiedergegeben.

Wäre Cantors Mengenbegriff korrekt, dann ließe sich die Menge $M$ aller Mengen $X$ bilden, die sich selbst nicht als Element enthalten.

Für alle Mengen $X$ gilt dann: $X \in M$ genau dann, wenn $X \notin X$ .

Da $M$ selbst eine Menge ist, müßte speziell für $X = M$ gelten:

$M \in M$ genau dann, wenn $M \notin M .$

Dies liefert offensichtlich einen Widerspruch.

Wir wollen Mengen aber trotzdem in diesem „naiven“ anschaulichen Sinne verstehen. Eine logisch befriedigende Einführung in die Mengenlehre sprengt den Rahmen dieses Buches.

Elementare mengentheoretische Operationen und Relationen

Wir führen zunächst folgende Bezeichnungen ein:

Ist $E (x)$ eine Eigenschaft für Elemente $x$ (Mengen sind natürlich ebenfalls Elemente) – dies könnte z.B. $x \neq x, x \in M$ oder auch $x \notin M$ sein, wobei $M$ eine gegebene Menge ist – dann bezeichne ${x : E (x)}$ die Zusammenfassung aller Elemente $x$ mit der Eigenschaft $E$ (dies muß, entsprechend der konstruierten Antinomie, nicht wieder eine Menge sein).

Ist $a$ ein Element, dann ist ${a}$ die Menge, die aus genau dem einen Element $a$ besteht. Analog soll ${a_{1}, \dots, a_{n}}$ die Menge sein, die aus genau den Elementen $a_{1}, \dots, a_{n}$ besteht. Dabei werden die Elemente in der Menge natürlich nur einmal „gezählt“, falls sie in der Auflistung $a_{1}, \dots, a_{n}$ mehrfach auftreten.

Im folgenden seien $M, N$ Mengen.

Gleichheit von Mengen

Zwei Mengen sind genau dann gleich, wenn sie die gleichen Elemente enthalten, d.h.,

$M = N :=$ Für jedes $x$ gilt: $x \in M$ genau dann, wenn $x \in N .$

Teilmengenbeziehung oder Inklusion

$M \subseteq N :=$ Für jedes $x$ gilt: wenn $x \in M,$ so $x \in N .$ (Inklusion)

$M \subset N := M \subseteq N$ und $M \neq N,$ (echte Inklusion) d.h., $M \subseteq N$ und es gibt ein $x$ , so daß $x \in N$ , und $x \notin M .$

Will man aus einer gegebenen Menge $M$ die Teilmenge der Elemente $x$ mit einer bestimmten Eigenschaft – etwa $E (x)$ – aussondern, dann kennzeichnen wir dies durch

${x \in M : E (x)} .$

Durchschnitt und Vereinigung von Mengen

$M \cap N := {x : x \in M$ und $x \in N} .$ (Durchschnitt; vgl. Abb. 1.1)

$M \cup N := {x : x \in M$ oder $x \in N} .$ (Vereinigung; vgl. Abb. 1.2 )

PICT

PICT

Differenz und Komplement von Mengen

$M \ N := {x : x \in M$ und $x \notin N} .$ (Mengendifferenz; vgl. Abb. 1.3)

Ist eine Bezugsmenge $M$ gegeben, z.B. $M = I R$ , dann läßt sich auch das Komplement einer Teilmenge $N$ von $M$ bilden:

$C (N) := {x : x \in M$ und $x \notin N} .$ (Komplement bez. $M$ ; vgl. Abb. 1.4)

PICT

Komplement

Geordnetes Paar

$(a, b) := {{a, b}, {b}} .$

Der Sinn dieser Definition ist nicht unmittelbar einsichtig. Er besteht vorwiegend darin, daß nur mengentheoretische Grundbegriffe verwendet werden und daß sich die folgende grundlegende Eigenschaft für geordnete Paare recht leicht nachweisen läßt:

$(a, b) = (c, d)$ genau dann, wenn $a = c$ und $b = d .$

Sinngemäß definiert man den Begriff des Tripels und schließlich induktiv den des $n$ -Tupels:

$(a, b, c) := ((a, b), c)$ , (Tripel )

$(a_{1}, \dots, a_{n}, a_{n + 1}) := ((a_{1}, \dots, a_{n}), a_{n + 1}) .$ ( $(n + 1)$ -Tupel )

Kartesisches Produkt

$M \times N := {(x, y) : x \in M$ und $y \in N} .$ (Produkt zweier Mengen)

$M_{1} \times \dots \times M_{n} := {(x_{1}, \dots, x_{n}) : x_{1} \in M_{1}, \dots, x_{n} \in M_{n}} .$

(Produkt endlich vieler Mengen)

Potenzmenge

$P o t (M) := {X : X \subseteq M} .$ (Menge aller Teilmengen von $M$ )

Aus Bequemlichkeitsgründen soll auch die „Zusammenfassung“ von Objekten, die gar kein Element enthält, als Menge bezeichnet werden, und zwar als

Leere Menge

$\emptyset := {x : x \neq x} .$

Manchmal ist es erforderlich, bei Durchschnitten oder Vereinigungen mit mehr als zwei Mengen zu operieren. Dazu betrachten wir jetzt eine Menge $M$ , deren Elemente selbst wieder Mengen sind. $M$ heißt dann auch System von Mengen.

Definition. (Durchschnitt und Vereinigung von Mengensystemen)

(1) $⋂ M$ heißt Durchschnitt von $M$

=Df

⋂ M = {x :

für jedes

X \in M

ist

x \in X}

Bez.: $⋂ M = ⋂_{X \in M} X$

(2) $⋃ M$ heißt Vereinigung von $M$

=Df

⋃ M = {x :

es existiert ein

X \in M,

so daß

x \in X}

Bez.: $⋃ M = ⋃_{X \in M} X$

Bemerkung. Häufig wird ein System von Mengen dadurch gegeben, daß man von einer sog. Indexmenge $I$ ausgeht, jedem „Index“ $i \in I$ eine Menge $X_{i}$ zuordnet und die Mengen $X_{i}$ zu einer neuen Menge $M : = {X_{i} : i \in I}$ zusammenfaßt.

Für das so gewonnene Mengensystem $M$ kann man dann den Durchschnitt bzw. die Vereinigung wie folgt schreiben:

$⋂ M = ⋂_{i \in I} X_{i}$ bzw. $⋃ M = ⋃_{i \in I} X_{i} .$

Es ließen sich hier natürlich weitere solcher Grundbegriffe auflisten. Für unsere Zwecke reichen die bisher gegebenen aber zunächst aus.

In mathematischen Definitionen und Sätzen benutzt man sehr häufig die folgenden Bindewörter bzw. Wortverbindungen:

nicht, und, oder, wenn – so, genau dann – wenn (oder einfach gdw), für jedes $\dots$ , es gibt ein $\dots$ ,

die der Reihe nach auch als

Negation, Konjunktion, Alternative, Implikation, Äquivalenz, All-Quantor, Existenz-Quantor

bezeichnet werden, und für die man gelegentlich der Reihe nach folgende Abkürzungen benutzt:

$\neg, \land, \lor, \to, \leftrightarrow, \forall, \exists .$

Es hat sich gezeigt, daß man in der Mathematik alle Aussagen schon allein mittels gewisser „Grundaussagen“ (gebildet mit Hilfe des Mengenbegriffs, der Elementbeziehung und der Gleichheitsrelation) und den oben gegebenen Bindewörtern und Wortverbindungen formulieren kann. Es wäre natürlich nicht vernünftig, alle mathematischen Aussagen auf solche „Grundaussagen“ zurückzuführen, da man kompliziertere Aussagen (etwa aus der Analysis) in dieser „Sprache“ kaum noch verstehen könnte. Daher ist es sehr hilfreich, sich weitere Grundbausteine zu definieren. Hierzu gehören insbesondere Relationen und Funktionen (oder Abbildungen).

Definition. (Relation)

(1) $R$ ist eine 2-stellige Relation

=Df

Es gibt Mengen

M

und

N

, so daß

R \subseteq M \times N

(2) $R$ ist eine $n$ -stellige Relation ( $n \geq 1$ )

=Df

Es gibt Mengen

M_{1}, \dots, M_{n}

, so daß

R \subseteq M_{1} \times \dots \times M_{n}

(3) $R$ ist eine $n$ -stellige Relation in M ( $n \geq 1$ )

=Df

R \subseteq \underset{n - m a l}{\underset{︸}{M \times \dots \times M}}

Zum Beispiel ist $\leq = {(0, 0), (0, 1), (1, 1), (0, 2), (1, 2), (2, 2), \dots}$ eine 2-stellige Relation in $I N$ .

Definition. (Funktion oder Abbildung)

(1) $f$ ist eine Funktion (oder Abbildung)

=Df

Es existieren Mengen

M

und

N

, so daß

f \subseteq M \times N

, und für jedes

a \in M

gibt es höchstens ein

b \in N

, so daß

(a, b) \in f

. (Eine Funktion ist also eine spezielle Relation.)

(2) $f$ ist eine Funktion aus $M$ in $N$

=Df

f \subseteq M \times N

und für jedes

a \in M

gibt es höchstens ein

b \in N

, so daß

(a, b) \in f

Bez.: $f : M \to N .$

(3) $f$ ist eine Funktion von $M$ in $N$

=Df

f \subseteq M \times N

und für jedes

a \in M

existiert genau ein

b \in N

, so daß

(a, b) \in f

. (Jedes

a \in M

bestimmt eindeutig ein gewisses

b \in N

Bez.: $f (a) = b .$

In diesem Falle heißt $M$ Definitionsbereich (oder domain) von $f$ und

$f (M) : = {b \in N :$ es existiert ein $a \in M$ , so daß $b = f (a)}$

Wertebereich oder Bild (oder image) von $f .$

Bez.: $M = D (f) = d o m (f)$ und $f (M) = W (f) = i m (f) .$

Für Abbildungen $f : M \to N$ gilt also im allgemeinen nur $D (f) \subseteq M$ und $W (f) \subseteq N .$ $N$ heißt auch Zielbereich (oder range) von $f$ .

Definition. Es sei $f : M \to N$ eine Abbildung von $M$ in $N$ .

(1) $f$ ist surjektiv oder eine Abbildung auf $N$

=Df

Für jedes

b \in N

existiert ein

a \in M

, so daß

(a, b) \in f

, (d.h.,

W (f) = N

(2) $f$ ist injektiv oder eineindeutig von $M$ in $N$

=Df

Für jedes

a_{1}, a_{2} \in M

gilt: Wenn

a_{1} \neq a_{2}

, so

f (a_{1}) \neq f (a_{2})

(3) $f$ ist bijektiv oder eineindeutig von $M$ auf $N$

=Df

f

ist injektiv und surjektiv.

Eine wesentliche Aufgabe der Mathematik besteht darin, die Gültigkeit oder Ungültigkeit von mathematischen Aussagen (Behauptungen, Theoremen, …) zu überprüfen. In diesem Zusammenhang erhebt sich sofort die Frage nach dem Wahrheitswert (wahr := W bzw. falsch := F) einer zusammengesetzten Aussage in Abhängigkeit von den Wahrheitswerten ihrer einzelnen Bestandteile. Wir setzen hierbei das logische Prinzip der Zweiwertigkeit voraus, nämlich, daß jede mathematische Aussage entweder wahr oder falsch ist. In Form von Schemata (Wahrheitswerttabellen) kann der Wahrheitwert aussagenlogisch zusammengesetzter Aussagen dargestellt werden. Hierzu seien $A$ und $B$ beliebige Aussagen. Wir bilden aus $A, B$ kompliziertere Aussagen, die mit Hilfe von nicht, und, oder, wenn – so, gdw zusammengesetzt sind. Dann gilt:

$A$	$\neg A$

W	F
F	W

$A$	$B$	$A \land B$	$A \lor B$	$A \to B$	$A \leftrightarrow B$

W	W	W	W	W	W
W	F	F	W	F	F
F	W	F	W	W	F
F	F	F	F	W	W

Die Implikation „Wenn $A$ , so $B$ “ ist immer schon dann wahr, wenn die Voraussetzung $A$ falsch ist. (In solchen Implikationen nennt man $A$ Voraussetzung und $B$ Behauptung.) Dies führt gelegentlich zu Irritationen. Aber, in der Mathematik wird die Implikation genau so benutzt. An dem folgenden kleinen Beispiel soll dies erläutert werden.

Wählt man für $A : = n | 2$ ( $n$ teilt 2) und für $B : = n | 6$ , dann erhält man die für alle natürlichen Zahlen $n$ gültige Beziehung

Wenn $n | 2$ , so $n | 6$ .

Dies ist insbesondere richtig für $n = 2, 3, 4$ . Also

für $n = 2$ entsteht $2 | 2 \to 2 | 6$ ( W – W),

für $n = 3$ entsteht $3 | 2 \to 3 | 6$ ( F – W),

für $n = 4$ entsteht $4 | 2 \to 4 | 6$ ( F – F).

Die Gültigkeitsuntersuchungen von Aussagen, die mit Hilfe von Quantoren gebildet sind, erweisen sich als wesentlich komplizierter.

Ist $A (x)$ ein Ausdruck (Eigenschaft), der etwas über die Elemente einer Menge $M$ aussagt, dann wird festgelegt:

Die Aussage „Für jedes $x : A (x)$ “ ist wahr in $M$ =Df Für ein beliebiges $a \in M$ trifft $A$ auf $a$ zu.

Die Aussage „Es gibt ein $x : A (x)$ “ ist wahr in $M$ =Df In $M$ existiert ein Element $a$ , so daß $A$ auf $a$ zutrifft.

Bei der Untersuchung des Wahrheitsgehalts einer mathematischen Aussage spielen Verneinungen eine wichtige Rolle. Wir werden jetzt zur besseren Veranschaulichung der logischen Struktur von Aussagen die früher eingeführten Abkürzungen $\neg, \land, \lor, \to, \leftrightarrow, \forall, \exists$ benutzen. Z.B. anstatt

„wenn $($ (wenn $A$ , so $B$ ) und (wenn $B$ , so $C$ ) $)$ , so (wenn $A$ , so $C$ )“

schreiben wir kürzer

$„ (A \to B) \land (B \to C) \to (A \to C) “ .$

Im folgenden seien $A, B$ Aussagen.

Definition. (Äquivalenz von Aussagen) $A$ und $B$ sind äquivalent =Df $A \leftrightarrow B$ ist wahr. Bez.: $A \equiv B, A \Leftrightarrow B, A$ gdw $B$

Wir geben jetzt Regeln für die Verneinung zusammengesetzter Aussagen an. Durch schrittweise Anwendung dieser Regeln lassen sich beliebige mathematische Aussagen verneinen.

$\begin{matrix} \neg (\neg A) & \equiv & A, (\neg (\neg A) \leftrightarrow A ist also immer wahr .) \\ \neg (A \land B) & \equiv & \neg A \lor \neg B, \\ \neg (A \lor B) & \equiv & \neg A \land \neg B, \\ \neg (A \to B) & \equiv & A \land \neg B, \\ \neg (A \leftrightarrow B) & \equiv & (A \land \neg B) \lor (\neg A \land B), \\ \neg \forall x A (x) & \equiv & \exists x \neg A (x), \\ \neg \exists x A (x) & \equiv & \forall x \neg A (x) . \end{matrix}$

Daraus ergeben sich sofort die folgenden Äquivalenzen:

$A \to B \equiv \neg A \lor B$ ,

$A \leftrightarrow B \equiv (A \to B) \land (B \to A)$ .

Es werden jetzt einige wahre Aussagen betrachtet, die aufgrund ihrer logischen Struktur häufig als Beweisprinzipien auftreten. (In der Regel benutzt man diese Prinzipien schon rein intuitiv richtig.)

$A \land (A \to B) \to B$ (Modus ponens oder Abtrennungsregel )

Aus der Gültigkeit der Aussagen $A$ und $A \to B$ , schließt man auf die Gültigkeit der Aussage $B$ .

Analog interpretiert man auch die folgenden Prinzipien:

$(A \to B) \land (B \to C) \to (A \to C)$ (Kettenschluß )

$A \to B \leftrightarrow \neg B \to \neg A$ (Kontraposition)

Die Kontraposition besagt, daß die Aussagen $A \to B$ und $\neg B \to \neg A$ stets den gleichen Wahrheitswert besitzen. Dies darf allerdings nicht verwechselt werden mit der Umkehrung $B \to A$ der Implikation $A \to B$ . Die Aussagen $A \to B$ und $B \to A$ sind im allgemeinen nicht äquivalent.

$(\neg A \to F) \to A$ (indirekter Beweis; $F$ steht für eine beliebige falsche Aussage)

Praktisch geht man beim indirekten Beweis folgendermaßen vor: Man nimmt an, daß die Aussage $A$ falsch ist, also die Negation $\neg A$ gilt. Dann leitet man aus dieser Annahme etwas Falsches her, d.h., man erzeugt einen Widerspruch. (Dies wird häufig einfach durch das Symbol PICT ! ausgedrückt). Daraus schließt man, daß die Aussage $\neg A$ nicht richtig sein kann; also gilt die Aussage $A .$ (Hierbei wird ganz wesentlich das Prinzip der Zweiwertigkeit benutzt.)

Die wichtigste Beweismethode für Aussagen über natürliche Zahlen ist die vollständige Induktion. Sie beruht auf dem

Induktionsaxiom:

Es sei $E$ eine Eigenschaft für natürliche Zahlen $n$ . Dann gilt

$E (0) \land \forall n (E (n) \to E (n + 1)) \to \forall m E (m) .$

Um die Aussage $\forall m E (m)$ zu beweisen, genügt es:

1. $E (0)$ zu zeigen (Anfangsschritt) und

2. $\forall n (E (n) \to E (n + 1))$ nachzuweisen (Induktionsschritt).

Bei der Eigenschaft 2. betrachtet man ein beliebiges $n \in N$ und zeigt:

Wenn $E (n)$ , so $E (n + 1)$ .

$E (n)$ heißt Induktionsvoraussetzung, $E (n + 1)$ Induktionsbehauptung.

Eigentlich müßte beim Induktionsschritt eine Fallunterscheidung durchgeführt werden:

Fall (a): $E (n)$ ist falsch.

Dann ist die Implikation $E (n) \to E (n + 1)$ aber trivialerweise richtig. Daher läßt man diesen Fall im Induktionsbeweis in der Regel weg und betrachtet nur noch

Fall (b): $E (n)$ ist richtig.

Unter dieser Voraussetzung ist dann die Gültigkeit von $E (n + 1)$ zu zeigen.

Achtung: Häufig findet man bei „Anfängern“ die folgende falsche Formulierung im Induktionsschritt:

„Für beliebiges $n$ wird vorausgesetzt, daß $E (n)$ schon gilt.“

Wer dies so formuliert, hat die Behauptung bereits vorausgesetzt.

Modifikationen des Induktionsaxioms

(1)

Es sei

k

eine natürliche Zahl.

E (k) \land \forall n (k \leq n \land E (n) \to E (n + 1)) \to \forall m (k \leq m \to E (m))

(2)

Es seien

k, l

natürliche Zahlen mit

k < l

E (k) \land \forall n (k \leq n < l \land E (n) \to E (n + 1)) \to \forall m (k \leq m \leq l \to E (m))

(1) liefert das Beweisprinzip von $E (n)$ für alle $n \geq k$ und (2) das von $E (n)$ für alle $n$ mit $k \leq n \leq l$ .

Schwerpunkte für die Wiederholung von Kapitel 1

Mengentheoretische Grundbegriffe (Gleichheit von Mengen, Inklusion, Durchschnitt, Vereinigung, Differenz, Komplement, kartesisches Produkt, Relationen, Funktionen);
Gebrauch von: nicht, und, oder, wenn–so, gdw, für jedes, es gibt ein;
Wahrheitswerttabellen; Verneinungen logischer Ausdrücke;
Beweisprinzipien (Modus ponens, Kettenschluß, Kontraposition, indirekter Beweis, vollständige Induktion);