Mengentheorie/Abzählbarkeit/Textabschnitt

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 Fakt 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 Fakt 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} ,$

so dass 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 Fakt 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.

$\Box$

Die Abzählbarkeit der positiven rationalen Zahlen.

Satz

Die Menge der rationalen Zahlen

ist abzählbar.

Beweis

Siehe Aufgabe.

$\Box$