BuK/IIm11/Studenten/siinkoer

Wiki-Quelltext dieser Seite.

==== Aufgabe 3 <tt>(Ingo Körner, Christof Ochmann)</tt> ====

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

Für $\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};\\
\lceil \frac{n}{2} \rceil, & \text{sonst }.\\
\end{cases}$$


Für $\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 || ...
|-
|| ... || ... || ... || ... || ... || ... || ...
|-
|}

Es werden mit Hilfe des ersten Cantorschen Diagonalisierungsverfahren alle Zahlen erreicht.

Für die Menge der Primzahlen:

1. Die Menge der Primzahlen P ist unendlich (nach Satz von Euklid).

2. Die Menge der Primzahlen P ist abzählbar unendlich, da gilt: P $\subset \N$.


Für die Menge der geraden Zahlen:

1. Die geraden Zahlen G sind unendlich (per Definition) und abzählbar unendlich, da gilt: G $\subset \Z$.


<language>Scheme</language>
==== Aufgabe 4 <tt>(Ingo Körner, Christof Ochmann)</tt> ====
ÜA: Zeigen Sie, dass jede endliche Menge M aufzählbar ist.

''aufzählbar = abzählbar + berechenbar''

1) Jede endliche Menge ist aufzählbar (per Definition).

2) Jede endliche Menge ist berechenbar. 

Es gibt eine Funktion f, die als Eingabe die natürlichen Zahlen N nimmt und auf jedes Element der endlichen Menge M abbildet. f ist berechenbar, da es eine total berechenbare surjektive Funktion f : N -> M gibt.
Es wird der Reihe nach jedes Element aus N einem Element aus M zugeordnet. Ist f sujektiv, können die restlichen Elemente aus N auf ein beliebiges Element von M abgebildet werden. Somit ist f surjektiv, total und berechenbar.


ÜA: Die Menge G der Gitterpunkte (0, 0),(0, 1), ... einer x-y-Ebene ist aufzählbar.

1 Geben Sie eine Funktion f an, die $\N_0$ bijektiv auf G abbildet.

2 Definieren Sie eine Ordnungsrelation $p_<$ in G.
$p_<$ = {(0,0) < (0,1) < (1,0) < (2,0) < (1,1) < (0,2) < (0,3) < (1,2) < (2,1)}

3 Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y) des betrachteten Gitterpunktes (x, y) an.


<code id="4f7872cf68601">
(define pair 
    (lambda (m n)
        (+ (/ (* (+ m n) (+ m n 1)) 2) n)
    )
)
</code>

<run id="4f7872cf686a7">
(pair 3 2)
</run>


4 Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.