ℤ ist abzählbar

Wir betrachten die Menge ℤ = { … , −1, 0, 1, … } der ganzen Zahlen und definieren f : ℤ → ℕ durch

$f (x) = { \begin{matrix} 2x, & falls x \geq 0, \\ - 2 x - 1, & sonst. \end{matrix}$

Dann ist f : ℤ → ℕ bijektiv. Also ist ℤ abzählbar.

Allgemeiner gilt der folgende Satz:

Seien A und B abzählbar. Dann ist auch A ∪ B abzählbar.

Seien f : A → ℕ, g : B → ℕ injektiv. Wir definieren h : A ∪ B → ℤ durch

$h (x) = { \begin{matrix} f (x), & falls x \in A, \\ - (g (x) + 1), & falls x \in B - A. \end{matrix}$

Dann ist h injektiv, sodass |A ∪ B| ≤ |ℤ| = |ℕ|. Also ist die Menge A ∪ B abzählbar.