s3jeleus

Aus ProgrammingWiki
< BuK < IIm14 < Studenten
Archivierte Version vom 2015-04-15T17:44:51+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


Umkehrfunktion:

f^{-1}(n) = \begin{cases}1, & n = 1 \\ f^{-1}(n-1) * 2, & n > 1 \\ f^{-1}(\frac{1}{n}) + 1, & sonst\end{cases} 


Reele Zahlen
Indirekter Beweis: R ist abzählbar unendliche Menge, d.h es existiert eine Funktion f: \N \xrightarrow{\text{bij.}} \R
n_{ij} \in [0,9]

Es lässt sich stets eine neue Zeile, die eine neue reele Zahl repräsentiert, hinzufügen.
n_i = \begin{cases}
   n_{ii} + 1, & \text{wenn  $n_{ii} \neq 9$};\\
  0, & \text{sonst }.\\
\end{cases}

\R \ \N012...j...
| n_{1}n_{10}n_{11}n_{12}...n_{1j}...
| n_{2}n_{20}n_{21}n_{22}...n_{2j}...
| n_{3}n_{30}n_{31}n_{32}...n_{3j}...
| .....................
| n_{i}n_{i0}n_{i1}n_{i2}n_{i3}n_{ij}...