BuK/IIm10/BuK-Übung03 G1

Wiki-Quelltext dieser Seite.

=Beweis=
==Aufgabenstellung==
Zeigen Sie, dass <math>\wp(A^*)</math> für ein beliebiges Alphabet <math>A</math> 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 <math>A^*</math> wurde in der [[BuK/IIm10/BuK-Übung02 G1| letzten Übung nachgewiesen]], dass eine Abbildung möglich ist, die Wortmenge <math>A^*</math> über einem Alphabet <math>A</math> also abzählbar unendlich ist.

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

Bei <math>\wp(A^*)</math> handelt es sich jedoch um die Potenzmenge von <math>A^*</math>. Laut dem [http://de.wikipedia.org/wiki/Satz_von_Cantor Satz von Cantor] gilt für unendliche Mengen: <math>|X|<|\wp(X)|</math>.

(vgl.[http://de.wikipedia.org/wiki/Potenzmenge#Die Größe der Potenzmenge (Kardinalität) Die Größe der Potenzmenge (Kardinalität)])

=Entscheidbarkeit endlicher Mengen=

==Aufgabenstellung==
Implementieren Sie eine Scheme-Prozedur <math>chi-endlich</math>, die eine natürliche Zahl n und eine Liste L nimmt und entweder <math>\#t</math> oder <math>\#f</math> zurück gibt, je nachdem ob <math>n \in L</math> oder <math>n \notin L</math> gilt. Stellen Sie für den Entwurf von <math>chi-endlich</math> 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) <math>\chi'_{M}</math> 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==