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

$\Box$

## Satz

Die Menge der rationalen Zahlen
ist abzählbar.

### Beweis

$\Box$