Aufzählbarkeit und Entscheidbarkeit

Aufgabe

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

Lösung

Wenn \wp(A^*) abzählbar unendlich wäre, so müsste eine bijektive Abbildung auf die natürlichen Zahlen erfolgen können. Bijektiv bedeutet in diesem Fall, dass jedem Element aus N genau ein Element aus \wp(A^*) zugeordnet wird.

Die Menge \wp(A^*) wird über A^* gebildet. Unter der Annahme, dass \wp(A^*) abzählbar unendlich ist, müsste man also zuerst die natürlichen Zahlen auf A^* abbilden können und anschließend A^* auf \wp(A^*).

Für eine bijektive Abbildung von N auf \wp(A^*) müssten also alle drei Mengen gleichmächtig, im konkreten Fall also abzählbar unendlich sein. Dass N abzählbar unendlich ist steht außer Frage. Dass A^* ebenfalls abzählbar unendlich ist, wurde in Übung 2 nachgewiesen.

Wie kann nun die Mächtigkeit von \wp(A^*) bestimmt werden? Die Potenzmenge ist folgendermaßen definiert: \wp(X) := \{U | U \subseteq X\}. Die Menge A^* besteht aus den Wörtern w_1, w_2, \dots, w_k. Daraus folgt, dass \wp(A^*) für jedes w_i aus A^* ein Element der Form \{w_i\} enthält. Zusätzlich enthält \wp(A^*) aber unter Anderem auch \{\}. Das allein reicht aus, um sagen zu können |\wp(A)| > |A|.

Somit ist bewiesen, dass es keine bijektive Abbildung von A auf \wp(A^*) geben kann und somit auch keine von N auf \wp(A^*). Demzufolge ist \wp(A^*) eine überabzählbar unendliche Menge.

Aufgabe

Implementieren Sie eine Scheme-Prozedur chi-endlich, die eine natürliche Zahl n und eine Liste L nimmt und entweder #t oder #f zurückgibt, 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

Aufgabe

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

Lösung

Man sagt f zählt M auf, wenn gilt:

M \subseteq A^*
f ist eine totale Funktion der Form f: N \mapsto M
f ist surjektiv und berechnbar und deren Wertebereich ist M = {f(0), f(1), \dots}

Dabei ist M die Menge der Quadratzahlen. Die Funktion f muss also eine surjektive Abbildung der natürlichen Zahlen N auf die Menge M vornehmen und berechenbar sein. Dazu benötigen wir die sogenannte Aufzählfunktion g für die Menge der Quadratzahlen.

Die Menge M erzeugen wir mit Hilfe von Streams.

Damit können wir f wie folgt implementieren:

Aufgabe

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

Vorsich: Der folgende Aufruf stoppt nicht!

Um \text{quadRelZuNat} stoppen zu lassen verwenden wir weiter oben definierte Prozeduren.