Vorlesung 4 Freudenberg

Aus ProgrammingWiki

ÜA S.26 Satz 3: „Wenn die Menge M entscheidbar ist, dann ist M aufzählbar“

- der Satz ist bereits in der Wenn-Dann-Form
- entscheidbar: es existiert eine charakteristische vollständig definierte Funktion XM,A* , die entscheidet, ob ein Element x aus der Grundmenge A* in der Teilmenge M enthalten ist
- aufzählbar: es existiert eine Aufzählprozedur, die surjektiv ist und sie ist auf die natürlichen Zahlen abbildbar, sie ist berechenbar

- die Funktion ist XM,A* total berechenbar und somit aufzählbar
- Frage: Ist Berechenbarkeit hinreichend für Aufzählbarkeit?

ÜA S.28 Satz 4 / Teil 1: „Wenn M eine entscheidbare Menge ist, dann sind M und A*\M aufzählbare Mengen“

- der Satz ist bereits in der Wenn-Dann-Form
- Komplementmenge: M ist eine echte Teilmenge von A*, dann enthält die Komplementmenge A*\M alle die Elemente, die in A* aber nicht in M enthalten sind
- entscheidbar: es existiert eine charakteristische vollständig definierte Funktion XM,A* , die entscheidet, ob ein Element x aus der Grundmenge A* in der Teilmenge M enthalten ist
- -> die charakteristische Funktion XM,A* ist berechenbar und aufzählbar und entscheidet für alle Elemente aus A*, d.h. die Elemente aus A* müssen berechenbar sein und sind somit auch aufzählbar