Abzählbarkeit

Take-aways

• z.B. $\mathbb{N}$ oder $\mathbb{Q}$ abzählbar, weil du beginnen könntest, alle Elemente aufzuzählen. Bei $\mathbb{R}$ z.B. geht das nicht.
• Unendliche Mengen
  • Equinumerous, wenn es eine Bijektion gibt, Zeichen $\sim$
    • A und B sind gleich Mächtig
  • B dominiert A, wenn es eine injektion von A nach B gibt, Zeichen $\preceq$
  • countable, wenn equinumerous zu $\mathbb{N}$
  • $\sim$ ist eine Äquivalenzrelation
• Endliche Mengen
  • $A \sim B$, wenn $|A|=|B|$
  • Endliche Mengen sind immer countable

Arten von Mengen:

1. Endliche Mengen {1,2}
2. Unendliche abzählbare Mengen ($\mathbb{N}, \space \mathbb{Z}$, $\mathbb{N} \times \mathbb{N}$, endliche Bitstrings: $\{0,1\}^*$ )
3. Unendliche überabzählbare Mengen: $\{0,1\}^{\infty}$, $[0,1]$ und $\mathbb{R}$

$\{0,1\}^*$ ist abzählbar, damit gemeint sind alle endlichen Folgen aus 0 und 1, also 0, 1, 01, 10, 001, 1110
$\{0,1\}^{\infty}$ ist unabzählbar, damit gemeint sind alle unendlichen Folgen aus 0 uns 1, also 0101010101… unendlich halt

Beweise

Beweis, Abzählbarkeit der Menge S:

• Finde abzählbare Menge A, z.B. $\mathbb{N}$
• Muss aber mit Lemma begründet werden z.B. $\mathbb{N} \times \mathbb{N}$ ist abzählbar
• Finde injektive Funktion $f: S \rightarrow A$
• Beweise, dass f injektiv ist
• Beweise, dass $f(s) \in A$ gilt für alle $s \in S.$

Beweis, dass S überabzählbar ist:

• Finde überabzählbare Menge B, z.B. $\{0,1\}^\infty$ (vom TA empfohlen)
• Finde injektive Fkt $f: B \rightarrow S$
• Beweise, dass f injektiv ist
• Beweise, $f(b) \in S$ für alle $b \in B$

Beweise equinumerity (Gleichmächtigkeit): A ~ B

• Finde bijektive Funktion $f: A \rightarrow B$
• Beweise, dass f injektiv und surjektiv ist