BuK-Übung02

Aus ProgrammingWiki

Archivierte Version vom 2015-04-15T14:33:29+00:00. Aktuelle Version

Inhaltsverzeichnis

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

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

\| 0	1	2	3	4	5	...
\| 0	1	-1	2	-2	3	...

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

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

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

\Z \ \N	1	2	3	4	5	...
\| 1	1/1	1/2	1/3	1/4	1/5	...
\| 2	2/1	2/2	2/3	2/4	2/5	...
\| 3	3/1	3/2	3/3	3/4	3/5	...
\| 4	4/1	4/2	4/3	4/4	4/5	...
\| 5	5/1	5/2	5/3	5/4	5/5	...
\| ...	...	...	...	...	...	...