BuK/IIm12/Studenten/sifedeut/uebung4

Wiki-Quelltext dieser Seite.

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

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