Thema4

Aufgabe 1

Vervollständigen Sie die Herleitung der Funktionen für x und y aus z = π(x, y) und geben Sie als Beispiel die Ermittlung von x und y aus z = π(1, 3) = 13 an.

Aufgabe 2

zu zeigen: Jede Teilmenge M_2 einer abzählbaren Menge M_1 ist abzählbar. Wenn M_1 eine abzählbare Menge ist, dann ist jede Teilmenge M_2 \subseteq M_1 abzählbar.

Aufgabe 3

zu zeigen: Nicht jede Teilmenge M_2 einer aufzählbaren Menge M_1 ist aufzählbar. Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen M_2 ⊆ M_1, dass sie aufzählbar sind.

Aufgabe 4

zu zeigen: Wenn die Menge M entscheidbar ist, dann ist M aufzählbar.

Aufgabe 5

zu zeigen: Wenn M und A^*\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge.

Aufgabe 6

Stellen Sie die folgenden Mengen in genau einem Diagramm grafisch dar.

1. die Klasse der abzählbaren Mengen, von denen es überabzählbar unendliche viele gibt
2. die Klasse der aufzählbaren Menegn, von denen es abzählbar unendlich viele gibt
3. die Klasse der entscheidbaren Mengen, von denen es ebenfalls abzählbar unendlich viele gibt
4. die Klasse der semi-entscheidbaren Mengen, von denen es abzählbar unendlich viele gibt
5. die Klassen der endlichen Mengen von denen es abzählbar unendlich viele gibt
6. die Mengen A*, \mathscr{P}(a), und \mathscr{P}(A*) für ein beliebiges Alphabet A