BuK/IIm14/Studenten/s3jeleus

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Ü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}$

{| border="1" cellpadding="5" cellspacing="0"
|-
|| 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}$$

==== 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}$

{| border="1" cellpadding="5" cellspacing="0"
!$\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 || ...
|-
|| ... || ... || ... || ... || ... || ... || ...
|-
|}

$$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} $$

<code id="552e94541ee0b">(define f 
    (lambda (n) 
        (if (= n 1)
            1
            (if (= (modulo n 2) 0)
                (+ 1 (f (/ n 2)))
                (/ 1 (f (- n 1)))
            )
        )
    )
)</code>

<run id="552e94541ee7c"></run>

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}$$

{| border="1" cellpadding="5" cellspacing="0"
!$\R$ \ $\N$
!$0$
!$1$
!$2$
!$...$
!$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}$  || ...
|-
|}