BuK/IIm20/Vorlesung 4 Freudenberg

Wiki-Quelltext dieser Seite.

'''ÜA S.26 Satz 3: „Wenn die Menge M entscheidbar ist, dann ist M aufzählbar“''' <br\>
<br\>
-	der Satz ist bereits in der Wenn-Dann-Form <br\>
-	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 <br\>
-	aufzählbar: es existiert eine Aufzählprozedur, die surjektiv ist und sie ist auf die natürlichen Zahlen abbildbar, sie ist berechenbar <br\>
<br\> 
-	die Funktion ist XM,A*  total berechenbar und somit aufzählbar <br\>
-	'''Frage: Ist Berechenbarkeit hinreichend für Aufzählbarkeit?''' <br\>
<br\>
'''ÜA S.28 Satz 4 / Teil 1: „Wenn M eine entscheidbare Menge ist, dann sind M und A*\M aufzählbare Mengen“'''<br\>
<br\>
-	der Satz ist bereits in der Wenn-Dann-Form <br\>
-	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 <br\>
-	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 <br\>
-	-> 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 <br\>