saetze

• Eine Abbildung oder Funktion f ist eine rechtseindeutige Relationen der Form f \subseteq X \times Y, das heisst für jedes x \in X gibt es höchstens ein y \in Y mit (x,y) \in f. Man schreibt f(x) = y oder f : x \mapsto y, d.h. x wird durch die Funktion f auf y abgebildet. Statt f \subseteq X \times Y verwendet man die Schreibweise f : X \to Y.

• D_f = \{x \in X | \exists y \in Y f(x)=y\} \subseteq X heisst Definitionsbereich von f, Y Wertebereich von f.

• Eine Funktion f:X \to Y mit D_f = X heisst total. Gilt D_f \subseteq X, ist f eine partielle Funktion. Hieraus folgt, dass alle totalen Funktionen in der Menge der partiellen Funktionen enthalten sind. Man kann also sagen, dass jede totale Funktion partiell ist, aber nicht umgekehrt.

• Eine unendliche Menge M heisst abzählbar unendlich, wenn es eine bijektive Funktion \N \to M gibt. Gibt es eine solche Funktion nicht, so ist M überabzählbar unendlich.

• Eine Menge M ist entweder endlich oder abzählbar unendlich, wenn es eine surjektive Funktion \N \to M gibt.

• Die Potenzmenge einer (endlichen oder unendlichen) Menge M ist die Menge aller Teilmengen von M: p(M)=\{R|R \subseteq M \}

• Eine Funktion f ist berechenbar, wenn es einen Algorithmus gibt,der für jedes x \in D_f den zugehörigen Funktionswert f(x) effektiv ermittelt.

• Die Potenzmenge p(A^*) ist eine überabzählbar unendliche Menge

• Es gibt höchstens so viele Algorithmen wie Programme

• Es gibt höchstens abzählbar unendlich viele Programm

• Also stehen höchstens abzählbar unendlich viele Algorithmen überabzählbar unendlich vielen Wortfunktionen (Problemen) gegenüber.

• Fazit(Kardinalzahlargument): Es gibt überabzählbar unendlich viele nicht berechenbare Funktionen bzw. unentscheidbare Prädikate

• Eine Menge M_1 ist relativ entscheidbar zu M_2 (M_1,M_2 \subseteq A^*), wenn die charakteristische Funktion \chi_{M_1,M_2} mit

eine total berechenbare Funktion ist.