Beweis

Aufgabenstellung

Zeigen Sie, dass \wp(A^*) für ein beliebiges Alphabet A eine überabzählbar unendliche Menge ist.

Lösung

Um nachzuweisen, dass eine Menge abzählbar unendlich ist, muss eine bijektive Abbildung auf die natürlichen Zahlen möglich sein.

Für die Wortmenge A^* wurde in der letzten Übung nachgewiesen, dass eine Abbildung möglich ist, die Wortmenge A^* über einem Alphabet A also abzählbar unendlich ist.

Um nachzuweisen, dass \wp(A^*) abzählbar unendlich ist, müsste man also auch \wp(A^*) auf die natürlichen Zahlen abbilden können. Da diese Abbildung bei der Wortmenge A^* schon funktioniert hat, kann man auch eine Abbildung von \wp(A^*) auf A^* erzeugen um eine Abzählbarkeit nachzuweisen.

Bei \wp(A^*) handelt es sich jedoch um die Potenzmenge von A^*. Laut dem Satz von Cantor gilt für unendliche Mengen: |X|<|\wp(X)|.

(vgl.Die Größe der Potenzmenge (Kardinalität))

Da also in der Wortmenge A^* weniger Elemente vorhanden sind als in der Potenzmenge \wp(A^*) ist keine bijektive Abbildung möglich.

Entscheidbarkeit endlicher Mengen

Aufgabenstellung

Implementieren Sie eine Scheme-Prozedur chi-endlich, die eine natürliche Zahl n und eine Liste L nimmt und entweder \#t oder \#f zurück gibt, je nachdem ob n \in L oder n \notin L gilt. Stellen Sie für den Entwurf von chi-endlich die erforderlichen Hilfsprozeduren bereit.

Lösung

Aufzählbarkeit

Aufgabenstellung

Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen aufzählt.

Lösung

Semientscheidberkeit

Aufgabenstellung

Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen relativ zur Menge der natürlichen Zahlen semi-entscheidet.

Hinweis: Implementieren Sie eine Prozedur für die (allgemeingültige) \chi'_{M} und wenden Sie sie auf die Menge (stream) der natürlichen Zahlen an. Überlegen Sie sich vor dem Aufruf genau, welche Ausgabe Sie erwarten.

Lösung