Der erste Teil der Vorlesung soll mit einigen allgemeine Bemerkungen zu Abbildungen abgeschlossen werden. Der Begriff der Abbildung war bereits ganz zu Anfang definiert worden:
Definition. Seien $M$ und $N$ Mengen. Eine Abbildung von $M$ nach $N$ ist eine Vorschrift, die jedem Element von $M$ eindeutig ein Element von $N$ zuordnet.
Man bezeichnet $M$ als den Argument- oder Definitionsbereich und $N$ als den Bild- oder Wertebereich, aber es werden auch andere Begriffe wie Quelle und Ziel verwandt. Ist $f$ eine solche Abbildung, so schreibt man $$
f:M\to N.
$$ Ist $m$ ein Element von $M$, so bezeichnet man das eindeutig zugeordnete Element von $N$ mit $f(m)$. Will man die Vorschrift spezifizieren, so schreibt man auch $$f:m \mapsto f(m).$$
- Eine Abbildung $f:M\to \mathbb K$ mit Werten in einem Körper heißt $\mathbb K$-wertige Funktion.
- Eine Abbildung $g:\mathbb N\to M$ mit den natürlichen Zahlen als Definitionsbereich heißt Folge.
Funktionen $f,g:M\to \mathbb K$ lassen sich addieren und multiplizieren. Die Funktion \begin{aligned}f\ast g:M&\to \mathbb K\\m&\mapsto f(m)\ast g(m)\end{aligned} benutzt die Verknüpfung $\ast\in \{+,\cdot \}$ im Wertebereich. Die Funktion $$\frac1f:m\mapsto \frac1{f(m)}$$ besitzt die Teilmenge $\{m\in M\mid f(m)\not=0\}$ als natürlichen Definitionsbereich.
Obwohl nicht explizit geächtet, wird die Schreibweise $f^{-1}$ an dieser Stelle nicht empfohlen, da hier leicht Verwechslungen auftreten. Ist $f:M\to N$ nämlich eine bijektive Abbildung, so bezeichnet man mit $f^{-1}$ meist die inverse Abbildung \begin{aligned}N&\to M\\n=f(m)&\mapsto m\end{aligned} die einem Element $n\in N$ das eindeutig bestimmte Element $m\in M$ zuordnet, das durch $f$ auf $n$ abgebildet wird. Um Verwechslungen zu vermeiden, benutzt man im Falle von bijektiven Funktionen den Term Umkehrfunktion.
Die Angabe des Definitions- und Wertebereichs ist für Abbildungen wesentlich. Die Zuordnung $z\mapsto \frac{1}{z}$ liefert zum Beispiel eine Funktion, aber nur wenn wir $z=0$ als Argument ausschließen. Wir bekommen dann eine Funktion $$
\mathbb C\setminus \{0\}\to \mathbb C,
$$ und wenn wir ganz pingelig sein wollen, liefert dieselbe Vorschrift $z \mapsto \frac{1}{z}$ auch eine Funktion$$
\mathbb C\setminus \{0\}\to \mathbb C\setminus \{0\}.
$$ Es erweist sich als vorteilhaft, diese Funktionen als verschieden anzusehen, auch wenn sie durch die gleiche Vorschrift beschrieben werden.
Beispiele.
- Die Quadratfunktion \begin{aligned}\mathbb R&\to\mathbb R\\r&\mapsto r^2\end{aligned} ist weder injektiv noch surjektiv. Als Funktion $$\mathbb R\to \mathbb R_{\ge0}=\{r\in\mathbb R\mid r\ge0\}$$ ist die Quadratfunktion surjektiv.
- Die Quadratfunktion \begin{aligned}\mathbb C&\to\mathbb C\\z&\mapsto z^2\end{aligned} ist nicht injektiv, nach Satz (1.7.4) jedoch surjektiv. Jedes Element $w\in \mathbb C\setminus \{0\}$ besitzt genau zwei Urbilder.
- Die $n$-ten Potenzfunktionen \begin{aligned}\mathbb R_{\ge0}&\to\mathbb R_{\ge0}\\r&\mapsto r^n\end{aligned} sind für $n\in\mathbb N$ nach Satz (1.6.15) bijektiv. Die Umkehrfunktionen sind die Wurzelfunktionen \begin{aligned}\sqrt[n]{\phantom{xy}}:\mathbb R_{\ge0}&\to\mathbb R_{\ge0}\\r&\mapsto \sqrt[n]{r}.\end{aligned}
- Die Quadratfunktion \begin{aligned}\{w\in\mathbb C\mid \Im(w)\gt 0\}&\to\mathbb C\setminus \mathbb R_{\ge0}\\z&\mapsto z^2\end{aligned} ist bijektiv. Die Umkehrfunktion wird Zweig der komplexen Wurzelfunktion genannt.
Eine andere Möglichkeit, das Problem der Nichtdefiniertheit der Funktion $z\mapsto\frac{1}{z}$ aufzulösen, besteht darin, die komplexen Zahlen um ein Element $\infty$ zu erweitern, also $\mathbb C^+=\mathbb C\cup\{\infty\}$ zu setzen. Dann beschreibt die Vorschrift $z\mapsto\frac{1}{z}$ eine Abbildung \begin{aligned}\mathbb C^+&\to \mathbb C^+\\
z&\mapsto
\begin{cases}
\frac{1}{z},&\text{falls}\; z\notin \{0,\infty\}\\
0 &\text{falls}\; z=\infty\\
\infty &\text{falls}\; z=0.
\end{cases}\end{aligned} Entgegen dem ersten Anschein hat diese Konstruktion nichts Esoterisches an sich. Tatsächlich kann man $\mathbb C^+$ geometrisch als eine Kugeloberfläche interpretieren. Wenn man das so macht, ist die obige Abbildung nichts anderes als eine halbe Drehung dieser Riemannschen Zahlenkugel um eine Achse, die durch $1$ und $-1$ geht.
Zum Abschluss dieses etwas trockenen Kapitels ein kurzer Abstecher über die Mächtigkeit von Mengen.
Definition. Es seien $M$ und $N$ zwei Mengen.
Lemma 1.8.1. Es seien $M\not=\emptyset$ und $N$ zwei Mengen. Die folgenden Aussagen sind äquivalent:
Beweis. Es sind zwei Richtungen zu zeigen.
- $\implies$ 2. Sei $f:M\to N$ injektiv und $A:= f(X)\subset N$ das Bild von $f$. Dann ist $f:M\to A$ bijektiv und besitzt eine Umkehrfunktion $h:A\to M$. Wir wählen $m_0\in M$ beliebig und setzen \[g(n):=\begin{cases}h(n)&\text{ falls } n\in A\\m_0&\text{ sonst.}\end{cases}\] Die derart definierte Abbildung $g:N\to M$ ist surjektiv, da zu gegebenem $m\in M$ das Bild $f(m)$ in $A$ und folglich gilt $g((f(m))=h(f(m))=m$.
- $\implies$ 1. Es sei $g\colon N\to M$ surjektiv. Für jedes $m\in M$ ist das Urbild $B_m:=\{n\in N\mid g(n)=m\}$ nicht leer. Wir wählen aus jeder Teilmenge $B_m$ ein Element $b_m$ aus und definieren $f\colon M\to N$ durch $f(m):=b_m$. Diese Abbildung ist injektiv. Sei nämlich $m\in M$ gegeben, so ist $f(m)=b_m\in B_m$ und es gilt $g(f(m))=m$. Hätten wir also $f(m)=f(m')$, so folgte $m=g(f(m))=g(f(m'))=m'$.
qed
Bemerkung. Wie schon in den Übungen angemerkt, benötigt man in einer logisch fundierten Mengenlehre ein besonderes Axiom, das Auswahlaxiom, um den obigen Wahlvorgang zu rechtfertigen.
Satz von Schröder-Bernstein 1.8.2. Gilt $|M|\le |N|$ und $|N|\le |M|$, so gilt auch $|M|= |N|$.
Beweis. Seien $f\colon M\to N$ und $g\colon N\to M$ injektive Abbildungen, die es ja nach der Voraussetzung des Satzes geben muss. Zum Beweis des Satzes müssen wir aus $f$ und $g$ eine Bijektion $h\colon M\to N$ basteln. Dazu sehen wir uns die Lebensgeschichte eines Elementes an, auf das immer wieder eine der Abbildungen $f$ oder $g$ angewandt wird: Jedes Element $m\in M$ und $n\in N$ tritt in genau einer Sequenz der Form$$
\ldots n_{-2}\stackrel{g}{\longmapsto}
m_{-1}\stackrel{f}{\longmapsto}n_{-1}\stackrel{g}
{\longmapsto}m_0\stackrel{f}{\longmapsto}n_0\stackrel{g}
{\longmapsto}m_1\stackrel{f}{\longmapsto}n_1\stackrel{g}
{\longmapsto}m_2\stackrel{f}{\longmapsto}\ldots
$$ als ein $n_k$ oder $m_k$ auf. So eine Sequenz kann in beiden Richtungen unendlich lang sein, kann sich nach endlich vielen Schritten im Kreis schließen oder aber einen Anfang besitzen. Wir definieren $h$ durch $h(m)=f(m)$, falls $m$ in einer Sequenz auftaucht, die mit einem Element aus $M$ startet. Ansonsten setzen wir $h(m)=g^{-1}(m)$.
Die so definierte Abbildung ist bijektiv. Die Umkehrabbildung bildet $n\in N$ ab auf $f^{-1}(n)$, falls die Sequenz, in der $n$ lebt, ihren Startpunkt in $M$ besitzt und bildet ansonsten auf $g(n)$ ab.
qed
Satz 1.8.3. Für eine unendliche Menge $M$ gilt $|\mathbb N|\le |M|$.
Beweis. Wir müssen eine injektive Abbildung $f\colon \mathbb N\to M$ konstruieren. Ist $A\subset M$ eine beliebige endliche Menge. Da $M$ unendlich ist, können wir aus $M\setminus A$ ein Element $m_A$ auswählen. Wir definieren $f\colon\mathbb N\to M$ rekursiv und setzen $f(1):=m_\emptyset$. Seien $f(k)$ für $k\le n$ definiert, so setzen wir $f(n+1):= m_{\{f(1),\ldots,f(n)\}}$.
Nach Konstruktion gilt also \[f(n+1)\notin \{f(1),\ldots,f(n)\}\] für alle $N\in \mathbb N$. Folglich ist $f$ injektiv.
qed
Korollar 1.8.4. Für eine nicht-leere Menge $M$ sind äquivalent:
Beweis. Die Äquivalenz von 2. und 3. wurde bereits in 1.8.1. gezeigt.
\mathbb N\to M$.
- $\implies$ 2. gilt nach Definition der Abzählbarkeit.
- $\implies$ 1. Sei $f\colon M\to \mathbb N$ injektiv. Falls die Menge $M$ endlich ist, ist sie bijektiv zu einer Teilmenge $\{1,\ldots,n\} $ von $\mathbb N$. Falls $M$ unendlich ist, gilt $|\mathbb N|\le |M|$ nach Satz 1.8.3. Nach dem Satz von Schröder-Bernstein folgt, dass $\mathbb N$ und $M$ gleich mächtig sind.
qed
Satz 1.8.5. Das Produkt $\mathbb N\times \mathbb N$ ist abzählbar.
Beweis. Wir definieren $g\colon \mathbb N\times \mathbb N\to \mathbb N, (n,m)\mapsto 2^n\cdot 3^m$. Die Abbildung $g$ ist injektiv, denn sei $2^n\cdot 3^m=2^{n'}\cdot 3^{m'}$, so können wir annehmen $n\le n'$. Dann gilt $3^m=2^{n'-n}\cdot 3^{m'}$. Die linke Seite ist ungerade, also auch die rechte. Somit folgt $n=n'$ und damit $3^m=3^{m'}$ und $m=m'$.
qed
Korollar 1.8.6. Sowohl $\mathbb Z$, wie auch $\mathbb Q$ sind abzählbar.
Beweis. Wir wählen eine Bijektion $\phi\colon\mathbb N\to \mathbb N\times\mathbb N$. Die Abbildung $\psi\colon\mathbb N\times\mathbb N\to \mathbb Z, (s,h)\mapsto h-s$ ist surjektiv, wie auch die Abbildung $\rho\colon\mathbb N\times \mathbb N\times \mathbb N\to \mathbb Q, (s,h,n)\mapsto \frac{h-s}n$. Somit sind auch die folgenden zusammengesetzten Abbildungen surjektiv: \[\psi\circ\phi \colon \mathbb N\to \mathbb N\times\mathbb N\to \mathbb Z\] und \[\rho\circ\left(\phi\times \mathrm{id}_{\mathbb N}\right)\circ\phi \colon \mathbb N\to \mathbb N\times\mathbb N\to \mathbb N\times\mathbb N\times \mathbb N\to \mathbb Q.\]qed
Satz 1.8.7. Die reellen Zahlen sind überabzählbar.
Beweis. Wir benutzen wir eine Eigenschaft der Dezimalbruchentwicklungen: Jede reelle Zahl $x$ mit $0
\lt x \le 1$ hat eine eindeutig bestimmte Dezimalbruchentwicklung $$
x=0,a_1a_2a_3\ldots, $$ für die gilt: Es gibt kein $n\in\mathbb N$ mit $a_i=0$ für alle $i>n$. Wäre $\mathbb R$ abzählbar, so wäre auch das Intervall $]0,1]=\{r\in\mathbb R\mid 0 \lt r \le 1\}$ als Teilmenge von $\mathbb R$ abzählbar und es gäbe eine bijektive Abbildung $f\colon\mathbb N \to ]0,1]$.
\begin{align*}
f(1)&=0,a_{11} a_{12} a_{13} \ldots\\
f(2)&=0, a_{21} a_{22} a_{23}\ldots\\
f(3)&=0, a_{31} a_{32} a_{33}\ldots\\
&\vdots
\end{align*} Das Element $0,{b}_{1}{b}_{2} {b}_{3}\ldots$ taucht nicht in der Liste auf, falls ${b}_{i} \neq a_{ii}$ für alle $i$ gewählt wird.
qed
Die folgende Aussage wurde nicht in der Vorlesung behandelt und wird im weiteren Verlauf der Vorlesung auch keine Rolle spielen.
Satz von Cantor 1.8.8. Die Potenzmenge $\mathfrak{P}(M)$, also die Menge der Teilmengen von $M$, besitzt eine echt größere Kardinalität als $M$. Es gilt also $|M|\lt|\mathfrak{P}(M)|$.
Beweis. Die Zuordnung $m\mapsto\{m\}$ liefert eine injektive Abbildung von der Menge $M$ in ihre Potenzmenge. Nehmen wir nun an, es gäbe eine Bijektion $f\colon M\to
\mathfrak{P}(M)$. Dann bezeichne $ A\subset M$ die Teilmenge $A=\{m\in M\mid m\notin f(m)\}$ der Elemente von $M$, die nicht in ihrem Bild unter $f$ enthalten sind. Wegen der Surjektivität von $f$ gäbe es ein Element $m_0$ in $M$ mit $f(m_0)=A$. Dieses Element $m_0$ wäre nun nach Definition genau dann Element von $A$, wenn gälte $m_0\notin f(m_0)=
A$. Diesen Widerspruch kann kein Element ertragen.
qed