Vorlesung 2

Vorlesung 2 - Berechenbarkeitsbegriff

Inhaltsverzeichnis

Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: $\Z$, $\Q$, die Menge der Primzahlen, die geraden 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)$

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

(f 2)

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.

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

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

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$

(define f (lambda n (* n 2)))

(f 2)

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.