BuK/IIm12/Studenten/sidahorb/uebung4

Wiki-Quelltext dieser Seite.

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

Lösung:

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

Lösung:

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

Lösung:

== Aufgabe 4 ==
zu zeigen: Wenn die Menge $M$ entscheidbar ist, dann ist $M$ aufzählbar.

Lösung:

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

Lösung: