Produkt von abzählbaren Mengen/Abzählbar/Fakt/Beweis

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.

Zur bewiesenen Aussage