s3jeleus

Aus ProgrammingWiki
< BuK < IIm14 < Studenten
Archivierte Version vom 2015-04-15T16:26:30+00:00. Aktuelle Version

Inhaltsverzeichnis

Übungsaufgabe 2

Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \mathbb{Z}, \mathbb{Q}, die Menge der Primzahlen, die geraden Zahlen.

\Z ist abzählbar unendlich

z.z. \mathbb{Z} ist abzählbar unendlich, d.h. es existiert eine Funktion \mathbb{f}: \mathbb{N} \xrightarrow{\text{bij.}} \mathbb{Z}

| 012345...
| 01-12-23...
f(n) = \begin{cases} \frac{n}{2}, & \text{wenn n gerade};\\ - \frac{n + 1}{2}, & \text{sonst }.\\ \end{cases}

Beweis durch vollständige Induktion


Induktionsanfang

f(2n) + 1 == f(2n + 2)

Induktionsvoraussetzung

f(2n) + 1 = f(2n +2)

Induktionsbehauptung

f(2(n + 1) + 1 = f(2(n +1) + 2) \frac{2(n + 1)+ 1}{2} = \frac{f(2(n+ 1)+ 2}{2} n + 1 +1 = n + 1 + 1 n + 2 = n + 2 n = n


\Q ist abzählbar unendlich

z.z. \mathbb{Q} ist abzählbar unendlich, d.h. es existiert eine Funktion \mathbb{f}: \mathbb{N} \xrightarrow{\text{bij.}} \mathbb{Q}

\Z \ \N12345...
| 11/11/21/31/41/5...
| 22/12/22/32/42/5...
| 33/13/23/33/43/5...
| 44/14/24/34/44/5...
| 55/15/25/35/45/5...
| .....................
f(n) = \begin{cases} 1, & wenn \text{wenn n = 1};\\ f(\frac{n}{2}) + 1, & \text{wenn n gerade};\\ \frac{1}{f(n-1)}, & \text{sonst }.\\ \end{cases}

\P ist abzählbar unendlich

\P ist abzählbar unendlich