Anzahlvergleich von Mengen

• Mengen A und B sind gleichmächtig, Notation A∼B,

  falls eine Bijektion von A auf B existiert.

• Menge A heißt unendlich: ∃B⊆A : (B≠A)∧(B∼A).

  Beispiel: $\mathbb {N}$ ist unendlich.

• Menge A heißt abzählbar, falls A endlich oder A∼$\mathbb {N}$

  Bsp: Die Menge aller Programmtexte ist abzählbar.

• $\mathbb {N}$∼$\mathbb {N}$² (konstruiere Bijektion durch dovetailing)
• $\mathbb {N}$ $\not\sim$2^{$\mathbb {}$}N (Beweis: Cantors Diagonal-Argument)

  Folgerung: es gibt (sehr viele) Funktionen f : $\mathbb {N}$→{0, 1}, die nicht berechenbar sind.