BuK/IIm13/Studenten/simaknoc/Vorlesung 2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Vorlesung 2 - Berechenbarkeitsbegriff

== Abzählbar unendliche Menge ==

''' Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: $\Z$, $\Q$, die Menge der Primzahlen, die geraden Zahlen'''


=== Ganze Zahlen ===

z.z. Die Menge $\Z$ ist abzählbar unendlich.

D.h. es existiert eine bijektive Funktion f, die $\N$ auf $\Z$ abbildet.

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

Einige Funktionswerte:
$f(0) = 0$, $f(1) = -1$, $f(2) = 1$, $f(3) = -2$, $f(4) = 2)$

<code id="551c0f1aadbfb">

(define f
 (lambda(n)
  (if (=(modulo n 2)0)
    (/ n 2)
    (*(/ (+ n 1) 2) -1))))

</code>

<run id="551c0f1aadc6e">(f 2)</run>

=== Rationale Zahlen ===

z.z. Die Menge $\Q$ ist abzählbar unendlich.

D.h. Es existiert eine bijektive Funktion f, die $\N$ auf $\Q$ abbildet.

Die Zahlen der Menge $\Q$ werden dargestellt in der Form $z=\frac{p}{q}$

Lösung mit Hilfe des Cantorschen Diagonalisierungsverfahrens erster Art.

{| border="1" cellpadding="5" cellspacing="0"
! 
!$0$
!$1$
!$-1$
!$2$
!$-2$
!$3$
!$\ldots$
|-
|| $1$ || $\frac{0}{1}$|| $\frac{1}{1}$ || $-\frac{1}{1}$ || $\frac{2}{1}$ || $ -\frac{2}{1}$ || $\frac{3}{1}$ || $\ldots$
|-
||$2$|| $\frac{0}{2}$|| $\frac{1}{2}$ || $-\frac{1}{2}$ || $\frac{2}{2}$ || $ -\frac{2}{2}$ || $\frac{3}{2}$ || $\ldots$
|-
||$3$|| $\frac{0}{3}$|| $\frac{1}{3}$ || $-\frac{1}{3}$ || $\frac{2}{3}$ || $ -\frac{2}{3}$ || $\frac{3}{3}$ || $\ldots$
|-
||$4$|| $\frac{0}{4}$|| $\frac{1}{4}$ || $-\frac{1}{4}$ || $\frac{2}{4}$ || $ -\frac{2}{4}$ || $\frac{3}{4}$ || $\ldots$
|-
||$5$|| $\frac{0}{5}$|| $\frac{1}{5}$ || $-\frac{1}{5}$ || $\frac{2}{5}$ || $ -\frac{2}{5}$ || $\frac{3}{5}$ || $\ldots$
|-
||$\vdots$ ||$\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\ddots$
|}

=== Menge der Primzahlen ===

z.z. Die Menge der Primzahlen ist abzählbar unendlich.


=== Gerade Zahlen ===

z.z. Die Menge der geraden Zahlen ist abzählbar unendlich.

D.h. es existiert eine bijektive Funktion, die die Natürlichen Zahlen auf die geraden Zahlen abbildet.

$f(n) = 2n$

<code id="551c13f623372">
(define f
 (lambda n
  (* n 2)))
</code>

<run id="551c13f6233f4">(f 2)</run>

=== Vereinigungsmenge ===

'''Beweisen Sie den folgenden Satz:'''

Wenn $M_1$, $M_2$, $M_3$ $\ldots$ abzählbare Mengen sind, dann ist auch die Menge $\bigcup_{n=1}^{\infty} M_n$ abzählbar.

== Aufgabe Umkehrfunktion ==

== Überabzählbar unendliche Menge ==