Übung04

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:

für aufzählbare Mengen gilt:

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 (Felix Nitsche, Stefan Lüttke)

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

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.

Aufgabe 2 (Stefan Lüttke, Felix Nitsche)

(Aufgabe siehe: VL Slide 15/16)

Beweisen Sie diesen Satz, indem Sie mittels Aussagenlogik die Äquivalenz dieser Aussage zum vorhergehenden Satz zeigen. Es handelt sich um die Kontraposition:

Verwenden Sie im Beweis die folgenden Aussagen:

A: P' ist entscheidbar. B: P ist reduzierbar auf P'. C: P ist entscheidbar.

Der Beweis kann in Form einer Wahrheitstabelle erbracht werden. Dabei werden die folgenden Variabeln genutzt:

A: P' ist entscheidbar

B: P ist reduzierbar auf P'

C: P ist entscheidbar