2.1. Mengenlehre und Logik¶
Ein wichtiges Konzept um Mathematik aufzuschreiben sind sogenannte Mengen. Eine Menge ist eine Sammlung unterscheidbarer Objekte, die wir innerhalb der Mengenklammern \(\{ \ldots \}\) notieren. Wir unterscheiden endliche Mengen, wie
oder
und unendliche Mengen wie natürlichen Zahlen
Dabei ist die Reihenfolge der Elemente unerheblich, also können wir genauso \( M_1 = \{1,3,2\}\) oder \(M_1=\{3,2,1\}\) schreiben. Auch \(M_1=\{1,2,2,3\}\) ist immer noch die gleiche Menge, da wir nur unterscheidbare Objekte betrachten. Eine Menge \(M\) besteht aus ihren Elementen \(x\), wir schreiben \(x \in M\). Ist \(x\) nicht in \(M\) enthalten, so schreiben wir \(x \notin M\).
Definition 2.1
Seien \(M\) und \(\tilde M\) Mengen, dann heißt \(\tilde M\) Teilmenge von \(M\), wenn für alle \(x \in \tilde M\) folgt, dass \(x \in M\) gilt. Gibt es ein \(x \in M\) mit \(x \notin \tilde M\), dann heißt \(\tilde M\) echte Teilmenge.
Jede Menge hat zumindest eine Teilmenge, die sogenannte leere Menge \(\emptyset\). Ein einfaches Beispiel für eine Teilmenge ist \(\N \subset \Z\), es ist auch eine echte Teilmenge, da z.b. \(-1 \in \Z\) und \(-1 \notin \N\). Wir beachten auch den Unterschied zwischen \(x\) und der Menge \(\{x\}\). So gilt im obigen Beispiel etwa \(1 \in M_1\), aber \(\{1\} \subset M_1\).
Wir können (Teil)Mengen auch durch Aussagen definieren. Gegeben eine Menge \(M\) und eine Aussage \(A(x)\) über Elemente in \(x\), die entweder wahr oder falsch ist, erhalten wir
als Teilmenge jener Elemente von \(M\), für die \(A(x)\) wahr ist. Als Beispiel betrachten wir \(M_1\) wie oben und
oder als Teilmenge der reellen Zahlen
2.1.1. Mengensysteme und Mengenoperationen¶
In dem wir Mengen selbst in Mengen stecken, erhalten wir Mengensysteme. Als Beispiel betrachten wir
\(S\) ist eine Teilmenge der sogenannten Potenzmenge von \(\{1,2,3\}\) Allgemein nennen wir die Menge aller Teilmengen von \(M\) die Potenzmenge \({\cal P}(M)\) (oder auch \(2^M\)). So gilt etwa
Ist \(M\) endlich und bezeichnet \(\vert M \vert\) die Anzahl der Elemente in \(M\), so hat \({\cal P}(M)\) genau \(2^{\vert M \vert}\) Elemente. Auf Mengensystemen können wir auch Operationen definieren wie etwa den Durchschnitt oder die Vereinigung:
Definition 2.2
Sei \(S\) ein Mengensystem. Dann ist der Durchschnitt definiert als
und die Vereinigung als
Für endliche Systeme \(S=\{M_1,M_2,\ldots,M_n\}\) schreiben wir auch
bzw.
Gilt \(M_1 \cap M_2 = \emptyset\), so heißen \(M_1\) und \(M_2\) disjunkt. Gilt \(M_1 \cap M_2 = \emptyset\) für alle \(M_1\) und \(M_2\) in \(S\), so heißen die Elemente von \(S\) paarweise disjunkt. Wir können auch die Teilmengeneigenschaft über den Schnitt definieren:
Lemma 2.1
\(\tilde M \subset M\) gilt genau dann wenn \(\tilde M \cap M = \tilde M\)
Proof. \(\tilde M \subset M\) ist äquivalent zu
dies ist gilt natürlich auch genau dann wenn
Die letzte Aussage ist gleichbedeutend mit \(\tilde M \cap M = \tilde M\). \(\square\)
Wir definieren noch einige weitere Operationen auf Paaren von Mengen:
Die Differenzmenge \(M \setminus \tilde M\) ist gegeben durch
Die symmetrische Differenz \(M \Delta \tilde M\) ist gegeben durch
Das kartesische Produkt zweier Mengen ist die Menge aller geordneten Paare aus Elementen, d.h.
Dies kennen wir auch aus der Definition des \(\R^2 = \R \times \R\) über zwei kartesische Koordinaten.
Neben Operationen können wir auch sogenannte Relationen auf Paaren von Mengen oder einzelnen Mengen definieren. Dazu konstruieren wir eine neue Menge \(R\), in die wir alle geordneten Paare aus \(M \times \tilde M\) schreiben, für die eine Relation gelten soll:
Definition 2.3
Eine Teilmenge \(R \subset M \times \tilde M\) heißt Relation zwischen \(M\) und \(\tilde M\). Eine Teilmenge \(R \subset M \times M\) heißt Relation auf \(M\).
Als Beispiel können wir die Menge \(M\) der Bundesliga-Teams betrachten und definieren eine Relation wenn zwei Teams bereits gegeneinander gespielt haben. \(R\) besteht also aus allen Spielpaaren \((x,y)\). Wollen wir nicht nach Heim- oder Auswärtsspielen unterscheiden, so schreiben wir neben \((x,y)\) auch \((y,x)\) in \(R\).
Definition 2.4
Eine Relation \(R \subset M \times M\) heißt\begin{*ize}
reflexiv, wenn für alle \(x \in M\) gilt: \((x,x) \in R\)
symmetrisch, wenn \((x,y) \in R\) impliziert: \((y,x) \in R\)
antisymmetrisch, wenn \((x,y) \in R\) und \((y,x) \in R\) impliziert, dass \(y=x\) gilt
transitiv, wenn aus \((x,y) \in R\) und \((y,z) \in R\) folgt, dass \((x,z) \in R\) gilt. \end{*ize
Das obige Beispiel der Bundesligamannschaften ist nie reflexiv und nur dann symmetrisch, wenn wir nicht zwischen Heim- und Auswärtsspielen unterscheiden. Als weiteres Beispiel betrachten wir wieder \(M_1 = \{1,2,3\}\) und
Diese Relation ist reflexiv, anti-symmetrisch und transitiv. Relationen mit diesen drei Eigenschaften (Reflexivität, Anti-Symmetrie, Transitivität) nennen wir Ordnungsrelation (oder Halbordnung). Statt \((x,y) \in R\) schreiben wir auch \(x \preceq y\). Eine Halbordnung heißt Ordnung, wenn sich alle Paare vergleichen lassen, d.h. es gilt \(x \preceq y\) oder \(y \preceq x\).
Example 2.1
Sei \(M= \N \setminus \{0\}\) und \(R=\{(x,y) \in M \times M~|~x \text{ teilt } y\}\). Dies ist eine Halbordnung auf \(\N \setminus 0\), die keine Ordnung ist, da z.B. \(2\) und \(3\) nicht vergleichbar sind.
Eine weitere wichtige Klasse sind Äquivalenzrelationen:
Definition 2.5
Eine Relation \(R \subset M \times M\) heißt Äquivalenzrelation, wenn sie reflexiv, symmetrisch und transitiv ist. Für \((x,y) \in R\) schreiben wir dann auch \(x \sim y\).
Example 2.2
Sei \(M= \Z\) und \(x \sim y\) wenn
gilt. D.h. \(x \sim y\) wenn beide gerade oder beide ungerade sind. In diesem Beispiel kennen wir schon die Einteilung in sogenannte Äquivalenzklassen, nämlich die geraden und die ungeraden Zahlen. Solche kann man auch für allgemeine Äquivalenzrelationen definieren
Definition 2.6
Die von \(m \in M\) erzeugte Äquivalenzklasse unter einer Äquivalenzrelation ist gegeben durch
Jedes Element einer Äquivalenzrelation heißt Repräsentant
Im Beispiel der Aufteilung in gerade und ungerade Zahlen sind typische Repräsentanten die Zahlen \(0\) (für gerade) und \(1\) (für ungerade). Wir wissen auch, dass eine Zahl entweder gerade oder ungerade ist und eine solche Eigenschaft gilt ebenfalls für allgemeine Äquivalenzrelationen:
Lemma 2.2
Gegeben sei eine Äquivalenzrelation \(\sim\) auf \(M\). Dann ist jedes Element \(m \in M\) in genau einer Äquivalenzklasse enthalten. Für alle \(m,n \in M\) gilt entweder
Proof. \([m]\) ist wegen der Reflexivität nicht leer (\(m \in [m]\)) und jedes Element ist damit auch in mindestens einer Äquivalenzklasse enthalten. Sei nun \(m \in [n]\) für \(n \neq m\), dann folgt wegen der Symmetrie auch \(n \in [m]\). Wegen der Transitivität gilt
und
Also folgt \([m]=[n]\). Sei nun \(m \not\sim n\). Dann gilt für \(p \sim m\) auch \(p \not\sim n\), da sonst wegen der Transitivität \(m \sim n\) folgt. Also gilt für jedes \(p \in [m]\) auch \(p \notin [n]\). Mit exakt demselben Argument folgern wir aus \(p \in [n]\) dann \(p \notin [m]\). Damit ist \([n] \cap [m] = \emptyset\)
Bei der Relation
gibt es zwei Äquivalenzklassen, die geraden und die ungeraden Zahlen. Allgemeiner gibt es für \(n \in \N \setminus \{0,1\}\) und
genau \(n\) Äquivalenzklassen, die charakterisiert sind durch den Rest bei der Division durch \(n\), d.h. die Repräsentanten \(0,1,\ldots,n-1\). Man spricht deshalb auch von Restklassen.
Für eine Relation \(R\) auf \(M\) (oder kurz \(\sim\)) bezeichnen wir mit der Faktormenge \(M/R\) (oder \(M/\sim\)) die Menge der Äquivalenzklassen. Wir beachten, dass wir jede Äquivalenzklasse mit einem beliebigen Repräsentanten identifizieren können. So gilt bei der Einteilung in gerade und ungerade Zahlen \(M/\sim = \{[0],[1]\}\), was wir auch mit \(\{0,1\}\) identifizieren können.
2.1.2. Abbildungen¶
Eine Abbildung oder Funktion \(f:M_1 \rightarrow M_2\) ordnet jedem Element \(m_1 \in M_1\) ein Element \(m_2 =f(m_1) \in M_2\) zu. Die Bedeutung von Zuordnung ist zwar relativ klar, mathematisch sauberer ist eine Betrachtung als Mengen bzw. wieder als spezielle Relation:
Definition 2.7
Eine Relation \(f \subset M_1 \times M_2\) heißt Funktion (oder Abbildung) von \(M_1\) nach \(M_2\), wenn
\(i)\) \(D(f) = \{m_1 \in M_1~|~\exists m_2 \in M_2: (m_1,m_2) \in f \} = M_1 \)
\(ii)\) \((m,n) \in f\) und \((m,p) \in f\) impliziert \(n=p\).
Wir nennen \(M_1\) den Definitionsbereich und \(M_2\) den Bildbereich von \(f\).
heißt Wertebereich (oder Bild) von \(f\). Da zu jedem \(m_1 \in M_1\) nun genau ein \(m_2 \in M_2\) mit \((m_1,m_2) \in f\) existiert, können wir hier auch die Zuordnung \(m_2=f(m_1)\) definieren. Damit haben wir die gewohnte Form
die wir im Folgenden für Funktionen auch meist verwenden werden. Wir beachten, dass die Sichtweise über die Relation dem Funktionsgraphen bestehend aus den Punkten \((m,f(m))\) entspricht.
Definition 2.8
Eine Funktion \(f:M_1 \rightarrow M_2\) heißt
surjektiv, wenn Bildbereich und Wertebereich übereinstimmen, d.h. \(f(M_1)=M_2\)
injektiv, wenn aus \((m_1,n) \in f\) und \((m_2,n) \in f\) (bzw. \(f(m_1) =f(m_2)\)) folgt \(m_1=m_2\).
bijektiv, wenn sie injektiv und surjektiv ist.
Ist \(f\) bijektiv, dann erfüllt die Relation
auch die Eigenschaften einer Funktion und wir nennen \(f^{-1}\) die Umkehrfunktion von \(f\). Es gilt dann
und
Wir beachten, dass \(f^{-1}\) als Relation auch definiert ist, wenn \(f\) nicht bijektiv ist, \(f^{-1}\) ordnet dann jedem \(m_2\) eine Teilmenge von \(M_1\) zu (die auch leer sein kann). Die Einschränkung einer Funktion auf \(U \subset M_1\) bezeichnen wir mit
2.1.3. Mächtigkeit von Mengen¶
Mit Hilfe von Abbildungen können wir die Mächtigkeit, d.h. die Größe, von Mengen vergleichen. Für endliche Mengen ist die Mächtigkeit genau die Anzahl der Elemente, die wir einfach durchzählen können. Dies bedeutet wir konstruieren eine bijektive Abbildung von \(\{1,\ldots,n\}\) auf \(M\) und schreiben als Mächtigkeit dann \(\vert M \vert\). Für die leere Menge setzen wir \(\vert \emptyset \vert =0\). Dies können wir allgemeiner zum Vergleich der Mächtigkeit verwenden. Wir sagen, dass zwei Mengen \(M_1\) und \(M_2\) die gleiche Mächtigkeit haben, wenn es eine Bijektion \(f: M_1 \rightarrow M_2\) gibt. Die kleinste undendliche Menge ist \(\N\), wir definieren die Mächtigkeit von \(\N\) als \(\aleph_0\) (gesprochen Aleph Null) als kleinstes Maß für Unendlichkeit, diese nennen wir erste Kardinalzahl. Mengen \(M\), die durch eine Bijektion auf \(\N\) abgebildet werden können, nennen wir abzählbar (oder abzählbar unendlich) und schreiben dementsprechend \(|M|=\aleph_0\).
Example 2.3
Es gilt \(|\Z|=\aleph_0\). Wir betrachten dazu die bijektive Abbildung \(f: \N \rightarrow \Z\),
Example 2.4
Sei \(M= \N \times \N = \N^2\), dann gilt auch \(|M|=\aleph_0\). Wir betrachten dazu die bijektive Abbildung
Es gilt mit Hintereinanderausführung ähnlicher Abbildung übrigens auch \(|\N^n|=\aleph_0\).
Die Mengenlehre stößt an ihre Grenzen, wenn man Selbstbezüge in der Definition von Mengen einbaut. Dies zeigt ein bekanntes Beispiel von Bertrand Russell.
Sei
und
Damit können wir die unbeantwortbare Frage Gilt \(N \in N\) ? stellen. Nehmen wir an es gilt \(N \in N\), dann ist per Definition von \(N\) auch \(N \notin N\) und umgekehrt. Diese sogenannte Russell’sche Antinomie legt nahe, dass man Selbstbezüge in der Definition von Mengen vermeiden sollte um logisch konsistent zu bleiben.
2.1.4. Logik und Aussagen¶
Im Folgenden werden wir nun etwas näher die Aussagenlogik betrachten. Eine Aussage \(A\) ist für uns ein Element der Menge \(\{\text{wahr},\text{falsch}\}\). Eine Aussageform ist eine Abbildung von einer Menge an Möglichkeiten in die Menge \(\{\text{wahr},\text{falsch}\}\). So ist etwa \(4\) ist gerade eine (wahre) Aussage, und \(x \in N, x\) gerade eine Aussageform. Wir identifizieren im Folgenden meist die Aussage \(A\) mit der Abbildung \(M_A:M \rightarrow \{\text{wahr},\text{falsch}\}\), solange der Zusammenhang klar ist. Sind \(A,B\) zwei Aussagen, dann können wir mit sogenannten Junktoren neue Aussagen herleiten:
Negation: nicht \(A\), geschrieben \(\lnot A\), entspricht der Abbildung, die falsch liefert wenn \(A\) wahr liefert und umgekehrt.
Konjunktion: \(A\) und \(B\), geschrieben \(A \land B\), ist eine Abbildung, die wahr liefert wenn \(A\) und \(B\) wahr sind, sonst erhalten wir falsch.
Disjunktion: \(A\) oder \(B\), geschrieben \(A \lor B\), ist eine Abbildung, die falsch liefert wenn \(A\) und \(B\) falsch sind, sonst erhalten wir wahr.
Implikation: wenn \(A\), dann \(B\), geschrieben \(A \Rightarrow B\).
Äquivalenz: \(A\) äquivalent zu \(B\), \(A \Leftrightarrow B\).
Bei zwei Aussagen können wir die Verknüpfung durch Junktoren mit Fallunterscheidungen charakterisieren, die sogenannten Wahrheitstafeln, eine Tabelle der Form
A |
B |
J(A,B) |
|---|---|---|
W |
W |
* |
W |
F |
* |
F |
W |
* |
F |
F |
* |
wobei \(J(A,B)\) die Junktion bezeichnet. Als Beispiel betrachten wir das logische Und:
A |
B |
A \(\land\) B |
|---|---|---|
W |
W |
W |
W |
F |
F |
F |
W |
F |
F |
F |
F |
Mit Hilfe von Wahrheitstafeln können wir auch Verknüpfungen von Junktoren betrachten und deren Äquivalenz zu anderen Formen nachweisen. Als Beispiel betrachten wir \(\lnot (A \land B)\). Die Wahrheitstafel liefert
A |
B |
\(\lnot (A \land B)\) |
\((\lnot A) \lor (\lnot B)\) |
|---|---|---|---|
W |
W |
F |
F |
W |
F |
W |
W |
F |
W |
W |
W |
F |
F |
W |
W |
Damit sehen wir
Wie bereits vorher verwendet können wir Quantoren wie \(\forall\) und \(\exists\) verwenden und diese auch verknüpfen.
\(\forall x \in M: A(x) \) bedeutet, dass die Aussageform \(A\) für alle \(x\) in \(M\) wahr ist.
\(\exists x \in M: A(x) \) bedeutet, dass die Aussageform \(A\) für zumindest ein \(x\) in \(M\) wahr ist (oder äquivalent nicht für alle \(x \in M\) falsch ist).
Mit offensichtlichen Ergebnissen erhalten wir auch die Negation, Konjunktion etc. von Quantoren. So gilt etwa
und