Vorlesung 2
Inhaltsverzeichnis |
Vorlesung 2 - Berechenbarkeitsbegriff
Abzählbar unendliche Menge
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \Z, \Q, die Menge der Primzahlen, die geraden Zahlen
Ganze Zahlen
z.z. Die Menge \Z ist abzählbar unendlich.
D.h. es existiert eine bijektive Funktion f, die \N auf \Z abbildet.
$f(n) = \begin{cases} \frac{n}{2}, \text{wenn n gerade,}\\ -(\frac{n+1}{2}), \text{sonst.} \end{cases}$
Einige Funktionswerte: f(0) = 0, f(1) = -1, f(2) = 1, f(3) = -2, f(4) = 2)
Rationale Zahlen
z.z. Die Menge \Q ist abzählbar unendlich.
D.h. Es existiert eine bijektive Funktion f, die \N auf \Q abbildet.
Die Zahlen der Menge \Q werden dargestellt in der Form z=\frac{p}{q}
Lösung mit Hilfe des Cantorschen Diagonalisierungsverfahrens erster Art.
| 0 | 1 | -1 | 2 | -2 | 3 | \ldots | |
|---|---|---|---|---|---|---|---|
| | 1 | \frac{0}{1} | \frac{1}{1} | -\frac{1}{1} | \frac{2}{1} | -\frac{2}{1} | \frac{3}{1} | \ldots |
| |2 | \frac{0}{2} | \frac{1}{2} | -\frac{1}{2} | \frac{2}{2} | -\frac{2}{2} | \frac{3}{2} | \ldots |
| |3 | \frac{0}{3} | \frac{1}{3} | -\frac{1}{3} | \frac{2}{3} | -\frac{2}{3} | \frac{3}{3} | \ldots |
| |4 | \frac{0}{4} | \frac{1}{4} | -\frac{1}{4} | \frac{2}{4} | -\frac{2}{4} | \frac{3}{4} | \ldots |
| |5 | \frac{0}{5} | \frac{1}{5} | -\frac{1}{5} | \frac{2}{5} | -\frac{2}{5} | \frac{3}{5} | \ldots |
| |\vdots | \vdots | \vdots | \vdots | \vdots | \vdots | \vdots | \ddots |
Menge der Primzahlen
z.z. Die Menge der Primzahlen ist abzählbar unendlich.
Gerade Zahlen
z.z. Die Menge der geraden Zahlen ist abzählbar unendlich.
D.h. es existiert eine bijektive Funktion, die die Natürlichen Zahlen auf die geraden Zahlen abbildet.
f(n) = 2nVereinigungsmenge
Beweisen Sie den folgenden Satz:
Wenn M_1, M_2, M_3 \ldots abzählbare Mengen sind, dann ist auch die Menge \bigcup_{n=1}^{\infty} M_n abzählbar.