siinkoer

Aufgabe 3 (Ingo Körner, Christof Ochmann)

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

Für \Z:

Für \Q:

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.

Aufgabe 4 (Ingo Körner, Christof Ochmann)

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

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

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