ue3

Aufgabe 3: ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

Gegeben:

aufzählbar: abzählbar + berechenbar

abzählbar: \exists g: \N \mapsto G, G sei die Menge der geraden Zahlen

g: surjektiv

berechenbar: Es gibt einen Algorithmus für g

Funktion: $g(n) = \left\{\begin{array}{cc} n; wenn\ 2|n\\ -1 \cdot (n + 1); sonst\\ \end{array}\right.$

Algorithmus:

ÜA: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

Gegeben:

aufzählbar: abzählbar + berechenbar

abzählbar: \exists p: \N \mapsto P, P sei die Menge der Primzahlen

p: surjektiv

berechenbar: Es gibt einen Algorithmus für p

Funktion: