Aufgabe 1

Satz 1: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

Teilaufgabe 1 (Jens Heider, Daniel Tasche, Felix Nitsche, Stefan Lüttke)

zu zeigen: Wenn M aufzählbar, dann M semi-entscheidbar.

Gegeben ist eine aufzählbare Menge. Daraus folgt, dass es eine Aufzählprozedur f für M gibt, welche die natürlichen Zahlen auf die Elemente von M abbildet. f : \N \mapsto M

zu zeigen: M ist semi-entscheidbar

Wenn M semi-entscheidbar ist, dann gibt es eine Prozedur \chi'_M, die für ein Wort aus der Menge M über dem Alphabet A^* wahr zurückgibt, wenn das Wort in der Menge enthalten ist und ansonsten ewig weiter läuft. \chi'_M(w) : A^* \mapsto \{\text{wahr}\}

Durch Verwendung der Prozedur f kann entschieden werden, ob ein gegebenes Element in der Menge M enthalten ist. Dabei wird f für jedes i; mit i \in \N aufgerufen, f(0), f(1), f(2), ... Ergibt f(i) das Wort, dann gibt \chi'_M wahr zurück, ansonsten läuft die Prozedur ewig weiter.

Teilaufgabe 2 (Tobias Salzmann, Ronald Krause, Robert Rosenberger, Stefan Scheumann)

ÜA: 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.

Herleitung der Funktionen für x und y aus z = (x; y)

z =\frac{(x+y)(x+y+1)}{2} +y = t + y;
w = x + y;

Die Lösung von w^{2} + w + 2t = 0

für positives w ist w_1 = \frac{\sqrt{8t+1}-1}{2}

Außerdem gilt:
t \leq z , weil z=t+y
z= t + w - x, weil z=t+y und y=w-x

Unter Verwendung von z \leq \frac{(w+1)^{2} + (w+1)}{2} können wir w nach oben abschätzen.

Für z wird \frac{(w+1)^{2} + (w+1)}{2} eingesetzt:

\frac{\sqrt{4w^2+12w+9}-1}{2} = \frac{\sqrt{(2w+3)^2}-1}{2} = \frac{2w+2}{2} = \frac{2(w+1)}{2} = w+1

Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist als erstes w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor zu berechnen. Dann ergeben sich

t = \frac{w(w+1)}{2} und y = z -t sowie

Beispiel: Ermittelung von x und y aus z=\pi(1,3) = 13

Kritik an der Aufteilung Aufgabenstellung wird bis Dienstag 15:00 Uhr entgegen genommen und Bearbeitet ;-)

Aufgabe 2

Satz 2: Jede Teilmenge einer abzählbaren Menge ist abzählbar, aber nicht jede Teilmenge einer aufzählbaren Menge ist aufzählbar.

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.

Teilaufgabe 2 - Indirekter Beweis (Max Wielsch, Raik Bieniek)

zu zeigen: Nicht jede Teilmenge M_2 einer aufzählbaren Menge M_1 ist aufzählbar.

oder: Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen M_2 ⊆ M_1, dass sie aufzählbar sind.

Indirekter Beweis: Behauptung: Wenn M_1 aufzählbar, dann jede Teilmenge M_2 ⊆ M_1 ist aufzählbar.

Gegeben:

• f: ℕ ↦ M_1; aufzählbar (surjektiv; berechenbar)
• M_2 ⊆ M_1
• Satz 1: Wenn M_2 entscheidbar ⇔ M_2 und M_1 \setminus M_2 aufzählbar.
• Satz 2: Wenn M_2 aufzählbar → dann ist M_2 semientscheidbar.

Gesucht:

• g: ℕ ↦ M_2; aufzählbar (surjektiv; berechenbar), d. h. es gilt Satz 1.

$g(x) = \left\{\begin{array}{cc} f(x); wenn\ f(x) ∈ M_2\\ a; wenn f(x) ∈ M1\setminus M_2\\ \end{array}\right. $

laut Satz 2:

$Χ'_{M_2,M_1}(w) = \left\{\begin{array}{cc} wahr; (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\ ⊥; sonst\\ \end{array}\right. $

$Χ_{M_2,M_1}(w) = \left\{\begin{array}{cc} wahr; (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\ falsch; (f(i) = w) ∈ M_1\setminus M_2 \\ \end{array}\right. $

Χ'_{M_2,M_1} vs. Χ_{M_2,M_1}; entscheidbar ☇ semi-entscheidbar. → Behauptung falsch → Satz wahr.

Aufgabe 3

Satz 3: Wenn die Menge M entscheidbar ist, dann ist M aufzählbar.

Beweis:

Es ist gegeben, dass M entscheidbar ist. Damit ist M auch semi-entscheidbar. Wie in Satz 1 bereits bewiesen wurde gilt, dass jede semi-entscheidbare Menge auch aufzählbar ist.

Aufgabe 4

Eine Menge M, mit M \subseteq A^* ist entscheidbar genau dann, wenn M und A^*\M aufzählbare Mengen sind.

Teilaufgabe 1 - Beweis Teil 1 (Ingo Körner, Christof Ochmann)

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

Teilaufgabe 2 - Beweis Teil 2 (Tobias Salzmann, Ronald Krause)

Abbildung

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

Da M und A^*\M aufzählbare Mengen sind, gibt es total berechenbare surjektive Funktionen für diese.

Für M lautet die Auzählfunktion f: \N \mapsto M:

Hinweis: a \in M .

Für A^*\M lautet die Auzählfunktion g: \N \mapsto A^*\M:

Hinweis: b \in A^*\M .

Beweis

Da zu zeigen ist, dass M entscheidbar sein soll, muss es eine total berechenbare Funktion \chi_M geben.

Es muss also eine Prozedur chi geben, welche für jedes Wort w in endlicher Zeit für ein i mit w = f(i) oder w = g(i) findet.

Da die Schnittmenge von M und A^*\M eine leere Menge ist, kann es kein w geben, welches in beiden Mengen vorkommt, sodass man genau sagen kann, ob w in der Menge M oder der Menge A^*\ M liegt.

Da das Wort w aus der Wortmenge A^* stammt und die Vereinigung der beiden Mengen die Wortmenge ist, muss das Wort in diesen beiden Mengen liegen. Um die Abzählbarkeit zu gewährleisten, wird abwechseln das i-te-Element aus f und g gesucht, sodass kein Wort vergessen wird.

Teilaufgabe 3 - Illustration (Robert Rosenberger, Stefan Scheumann)

Übung 4, Aufgabe 4 (Teilaufgabe 3)

Illustrieren Sie den Beweis (Aufgabe 4.2) durch ein Scheme-Programm.