BuK/IIm14/Studenten/s3jeleus

Wiki-Quelltext dieser Seite.

== Ü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 ===


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