BuK/IIm11/Studenten/sifenits/Übung04

Wiki-Quelltext dieser Seite.

Behauptung: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.
[Bearbeiten] Teilaufgabe 1 (Felix Nitsche, Stefan Lüttke, Jens Heider, Daniel Tasche)
zu zeigen: Wenn M aufzählbar, dann M semi-entscheidbar.


Annahme:

$M \subseteq X$

$x, n \in N$

für aufzählbare Mengen gilt:

$f(x) :  N \rightarrow M$

für semi-entscheidbare Mengen gilt:

$
g(n \in X) = \begin{cases}
wahr; & \text{wenn } n \in M;\\
\bot; & sonst
\end{cases}
$


Es kann nun bewiesen werden dass eine aufzählbare Menge immer auch semi-entscheidbar ist, wenn man einen Algorithmus angibt, der mithilfe der Funktion $f(x)$ die Funktion $g(n)$ nachbildet. Dies kann erreicht werden, indem die Funktion $f(x)$ in einer Schleife nacheinander mit jedem Element aus $X$ aufgerufen wird. Ist das Ergebnis dabei gleich $n$ wird $wahr$ zurückgegeben. Ist nun $n \in M$ gibt der Algorithmus $wahr$ zurück, andernfalls terminiert er nicht.




=== Teilaufgabe 1 - Beweis <tt>(Felix Nitsche, Stefan Lüttke)</tt> ===
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.

Da für $M_2 = \emptyset$ die Aussage offensichtlich zutrifft kann angenommen werden dass wenigstens ein Element $a \in  M_2$ existiert.

Für $M_1$ als abzählbare Menge existiert eine Funktion

$f(x) = n \in M_1$

welche die Menge der natürlichen Zahlen auf M_1 abbildet.

Dadurch kann man nun für $M_2$ die folgende Funktion angeben:

$
g(x) = \begin{cases}
f(x); & f(x) \in M_1;\\
a; & sonst
\end{cases}
$

Durch diese Funktion wird nun jedem Element der natürlichen Zahlen eindeutig ein Element der Menge $M_2$ zugeordnet, wodurch deren Abzählbarkeit bewiesen ist.