Kurs:Mathematik (Osnabrück 2009-2011)/Teil III/Vorlesung 61

Abzählbare Mengen

Wir erinnern daran, dass zwei Mengen ${}M$ und ${}N$ gleichmächtig heißen, wenn es eine bijektive Abbildung zwischen ihnen gibt. Hier interessieren wir uns für sogenannte „abzählbar unendlichen“ Mengen, die in Bijektion zu den natürlichen Zahlen gebracht werden können. Dies ist nicht für alle unendlichen Mengen möglich, für die reellen Zahlen beispielsweise nicht. Durch den Mächtigkeitsbegriff wird eine Hierarchie in die Welt der unendlichen Mengen gebracht. Die zu den natürlichen Zahlen gleichmächtigen Mengen sind die „kleinsten“ unendlichen Mengen.

Im Rahmen der Maßtheorie für den euklidischen Raum, die wir ab der nächsten Vorlesung entwickeln werden, sind solche Mengen vernachlässigbar. Andererseits kann in der Maßtheorie über abzählbare Indexmengen sinnvoll aufsummiert werden, aber nicht über größere Indexmengen.

Lemma

Es seien ${}M$ und ${}N$ zwei Mengen. Dann sind die folgenden Aussagen äquivalent.

1. ${}N$ ist leer oder es gibt eine surjektive Abbildung

   $\varphi \colon M\longrightarrow N.$

2. Es gibt eine injektive Abbildung

   $\psi \colon N\longrightarrow M.$

Beweis

${}(1)\Rightarrow (2)$. Wenn ${}N$ leer ist, so kann man die leere Abbildung ${}\emptyset \rightarrow M$ nehmen. Es sei also ${}N\neq \emptyset$ und sei

$\varphi \colon M\longrightarrow N$

surjektiv. Zu jedem ${}y\in N$ gibt es ein ${}x\in M$ mit ${}\varphi (x)=y$. Wir wählen für jedes ${}y$ ein solches ${}x_{y}$ aus und definieren ${}\psi$ durch

$\psi \colon N\longrightarrow M,\,y\longmapsto \psi (y)=x_{y}.$

Wegen ${}\varphi (\psi (y))=y$ ist ${}\psi$ injektiv.

${}(2)\Rightarrow (1)$. Es sei nun eine injektive Abbildung

$\psi \colon N\longrightarrow M$

gegeben. Diese induziert eine Bijektion zwischen ${}N$ und dem Bild von ${}\psi$, sei ${}\theta \colon N\rightarrow \operatorname {bild} \psi$ diese Abbildung. Wenn ${}N$ leer ist, so sind wir fertig. Es sei also ${}N\neq \emptyset$ und sei ${}c\in N$ ein fixiertes Element. Wir definieren

$\varphi \colon M\longrightarrow N$

durch

${}\varphi (x)={\begin{cases}\theta ^{-1}(x),\,{\text{ falls }}x\in \operatorname {bild} \psi \,,\\c{\text{ sonst}}\,.\end{cases}}\,$

Diese Abbildung ist wegen ${}\varphi (\theta (y))=y$ surjektiv.

$\Box$

Definition

Eine Menge ${}M$ heißt abzählbar, wenn sie leer ist oder wenn es eine surjektive Abbildung

$\varphi \colon \mathbb {N} \longrightarrow M$

gibt.

Nicht abzählbare Mengen nennt man im Allgemeinen überabzählbar. Aufgrund von Lemma 61.1 ist die Abzählbarkeit von ${}M$ gleichbedeutend damit, dass es eine injektive Abbildung ${}M\rightarrow \mathbb {N}$ gibt. Beim Nachweis der Abzählbarkeit arbeitet man aber meistens mit der oben angegebenen Definition.

Endliche Mengen sind natürlich abzählbar. Die natürlichen Zahlen sind abzählbar unendlich.

Definition

Eine Menge ${}M$ heißt abzählbar unendlich, wenn sie abzählbar, aber nicht endlich ist.

Lemma

Eine Menge ${}M$ ist genau dann abzählbar unendlich, wenn es eine Bijektion zwischen ${}\mathbb {N}$ und ${}M$ gibt.

Beweis

Es sei

$\varphi \colon \mathbb {N} \longrightarrow M$

eine surjektive Abbildung. Wir definieren induktiv eine streng wachsende Abbildung

$\psi \colon \mathbb {N} \longrightarrow \mathbb {N}$

derart, dass ${}\varphi \circ \psi$ bijektiv ist. Wir setzen ${}\psi (0)=0$ und konstruieren ${}\psi$ induktiv über die Eigenschaft, dass ${}\psi (n+1)$ die kleinste natürliche Zahl ${}k$ ist, für die ${}\varphi (k)$ nicht zu

$\{\varphi (\psi (0)),\varphi (\psi (1)),\ldots ,\varphi (\psi (n))\}$

gehört. Eine solche Zahl gibt es immer, da andernfalls ${}M$ endlich wäre; also gibt es auch eine kleinste solche Zahl. Nach Konstruktion ist ${}\psi (n+1)>\psi (n)$, d.h. ${}\psi$ ist streng wachsend. Da jedes ${}n\in \mathbb {N}$ die Eigenschaft

${}\varphi (\psi (n+1))\notin \{\varphi (\psi (0)),\varphi (\psi (1)),\ldots ,\varphi (\psi (n))\}\,$

erfüllt, ist die Gesamtabbildung ${}\varphi \circ \psi$ injektiv.
Zum Nachweis der Surjektivität sei ${}m\in M$. Wegen der Surjektivität von ${}\varphi$ ist die Faser ${}\varphi ^{-1}(m)$ nicht leer und daher gibt es auch ein kleinstes Element ${}a\in \mathbb {N}$ mit ${}\varphi (a)=m$. Da ${}\psi$ streng wachsend ist, gibt es nur endlich viele Zahlen ${}i\in \{0,1,\ldots ,n\}$ mit ${}\psi (i)<a$. Daher ist ${}\psi (n+1)=a$ und ${}\varphi (\psi (n+1))=\varphi (a)=m$.

$\Box$

D.h. insbesondere, dass alle abzählbar unendlichen Mengen gleichmächtig sind.

Lemma

Seien ${}M_{1}$ und ${}M_{2}$ abzählbare Mengen.

Dann ist auch die Produktmenge ${}M_{1}\times M_{2}$ abzählbar.

Insbesondere ist das Produkt ${}\mathbb {N} \times \mathbb {N}$ abzählbar.

Beweis

Wir beweisen zuerst den Zusatz. Die Abbildung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(k,\ell )\longmapsto 2^{k}(2\ell +1),$

ist injektiv, da für jede positive natürliche Zahl ${}n$ die Zweierpotenz ${}2^{k}$, die sie teilt, und der ungerade komplementäre Teiler eindeutig bestimmt sind (das Bild der Abbildung ist ${}\mathbb {N} _{+}$). Daher ist die Produktmenge nach Lemma 61.1 abzählbar.
Für den allgemeinen Fall seien abzählbare Mengen ${}M_{1}$ und ${}M_{2}$ gegeben. Wenn eine davon leer ist, so ist auch die Produktmenge leer und somit abzählbar. Es seien also ${}M_{1}$ und ${}M_{2}$ nicht leer und seien ${}\varphi _{1}:\mathbb {N} \rightarrow M_{1}$ und ${}\varphi _{2}:\mathbb {N} \rightarrow M_{2}$ surjektive Abbildungen. Dann ist auch die Produktabbildung

$\varphi =\varphi _{1}\times \varphi _{2}\colon \mathbb {N} \times \mathbb {N} \longrightarrow M_{1}\times M_{2}$

surjektiv. Nach der Vorüberlegung gibt es eine surjektive Abbildung

$\mathbb {N} \longrightarrow \mathbb {N} \times \mathbb {N} ,$

sodass es insgesamt eine surjektive Abbildung ${}\mathbb {N} \rightarrow M_{1}\times M_{2}$ gibt.

$\Box$

Lemma

Es sei ${}I$ eine abzählbare Indexmenge und zu jedem ${}i\in I$ sei ${}M_{i}$ eine abzählbare Menge.

Dann ist auch die (disjunkte) Vereinigung ${}\bigcup _{i\in I}M_{i}$ abzählbar.

Beweis

Wir können annehmen, dass sämtliche ${}M_{i}$ nicht leer sind. Es gibt dann surjektive Abbildungen

$\varphi _{i}\colon \mathbb {N} \longrightarrow M_{i}.$

Daraus konstruieren wir die Abbildung

$\varphi \colon I\times \mathbb {N} \longrightarrow \bigcup _{i\in I}M_{i},\,(i,n)\longmapsto \varphi _{i}(n),$

die offensichtlich surjektiv ist. Nach Lemma 61.5 ist die Produktmenge ${}I\times \mathbb {N}$ abzählbar, also gilt das auch für das Bild unter ${}\varphi$, und dieses ist die Vereinigung.

$\Box$

Wir ziehen einige wichtige Konsequenzen über die Abzählbarkeit von Zahlenbereichen. Man beachte, dass die natürlichen Inklusionen ${}\mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q}$ nicht bijektiv sind. Die Bijektionen, die es zwischen ${}\mathbb {N}$ einerseits und ${}\mathbb {Z}$ bzw. ${}\mathbb {Q}$ andererseits aufgrund der folgenden Aussagen gibt, respektieren nicht die Rechenoperationen.

Lemma

Die Menge der ganzen Zahlen

ist abzählbar.

Beweis

Siehe Aufgabe 61.1.

$\Box$

Die Abzählbarkeit der positiven rationalen Zahlen.

Satz

Die Menge der rationalen Zahlen

ist abzählbar.

Beweis

Siehe Aufgabe 61.2.

$\Box$

Die Überabzählbarkeit der reellen Zahlen

Satz

Die Menge der reellen Zahlen ${}\mathbb {R}$

ist nicht abzählbar.

Beweis

 Nehmen wir an, die Menge der reellen Zahlen sei abzählbar, dann ist insbesondere auch das Einheitsintervall ${}[0,1[$ abzählbar. Es sei also

$\psi \colon \mathbb {N} _{+}\longrightarrow [0,1[$

eine surjektive Abbildung. Wir betrachten die reellen Zahlen als Ziffernfolgen im Dreiersystem: Jede reelle Zahl ${}r\in [0,1[$ besitzt eine eindeutig bestimmte Darstellung als Reihe

${}r=\sum _{k=1}^{\infty }z_{k}(r)3^{-k}\,,$

wobei die ${}k$-te Nachkommaziffer ${}z_{k}(r)\in \{0,1,2\}$ ist und wobei nicht fast alle Ziffern gleich ${}2$ sind (sonst hätte man keine Eindeutigkeit). Wir definieren nun eine reelle Zahl durch ${}s=\sum _{k=1}^{\infty }b_{k}3^{-k}$ mit

${}b_{k}={\begin{cases}0,{\text{ falls }}(\psi (k))_{k}=1{\text{ oder }}2,\\1,\,{\text{ falls }}(\psi (k))_{k}=0\,.\end{cases}}\,$

Wir behaupten, dass diese Zahl ${}s$ nicht in der Aufzählung ${}\psi$ vorkommt. Für jedes ${}k\in \mathbb {N}$ ist nämlich

${}\psi (k)\neq s\,,$

da ${}\psi (k)$ sich nach Konstruktion von ${}s$ an der ${}k$-ten Nachkommastelle unterscheidet. Also ist ${}\psi$ doch nicht surjektiv.

$\Box$

Kurt Gödel bewies 1938, dass die Hinzunahme der Kontinuumshypothese zur Zermelo-Fraenkelschen Mengenlehre einschließlich Auswahlaxiom (ZFC) diese nicht widersprüchlich macht. Man kann aber nicht beweisen, dass ZFC widerspruchsfrei ist. Auch das hat Gödel bewiesen.

Bemerkung  

Ist jede überabzählbare Menge ${}T\subseteq \mathbb {R}$ gleichmächtig zu ${}\mathbb {R}$? Die Kontinuumshypothese behauptet, dass dies gilt. Diese Frage berührt die mengentheoretischen Grundlagen der Mathematik; es hängt nämlich von der gewählten Mengenlehre ab, ob dies gilt oder nicht, man kann es sich also aussuchen. Anders als beim Auswahlaxiom, ohne dessen Akzeptanz eine Vielzahl von mathematischen Schlüssen nicht möglich wäre und die Mathematik ziemlich anders aussehen wüde, ist es für praktische Zwecke unerheblich, wofür man sich entscheidet.

Mit einem ähnlichen (Diagonal)-Argument wie im Beweis zu Satz 61.9 kann man zeigen, dass die Potenzmenge einer Menge stets eine größere Mächtigkeit als die Menge besitzt.

Satz

Es sei ${}M$ eine Menge und ${}{\mathfrak {P}}\,(M)$ ihre Potenzmenge.

Dann besitzt ${}{\mathfrak {P}}\,(M)$ eine größere Mächtigkeit als ${}M$.

Beweis

Wir nehmen an, dass es eine surjektive Abbildung

$F\colon M\longrightarrow {\mathfrak {P}}\,(M),\,x\longmapsto F(x),$

gibt, und müssen dies zu einem Widerspruch führen. Dazu betrachten wir

${}T={\left\{x\in M\mid x\notin F(x)\right\}}\,.$

Da dies eine Teilmenge von ${}M$ ist, muss es wegen der Surjektivität ein ${}y\in M$ geben mit

${}F(y)=T\,.$

Es gibt nun zwei Fälle, nämlich ${}y\in F(y)$ oder ${}y\not \in F(y)$. Im ersten Fall ist also ${}y\in T$, und damit, nach der Definition von ${}T$, auch ${}y\notin F(y)$, Widerspruch. Im zweiten Fall ist, wieder aufgrund der Definition von ${}T$, ${}y\in T$, und das ist ebenfalls ein Widerspruch.

$\Box$

Fußnoten

<< | Kurs:Mathematik (Osnabrück 2009-2011)/Teil III | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)