saetze

Aus ProgrammingWiki

• 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

$$ \chi_{M_1,M_2}(w) = \begin{cases} wahr, & \text{wenn } w \in M_1;\\ falsch, & \text{wenn } w \in M_2 \text{ ohne } M_1; \end{cases} $$ eine total berechenbare Funktion ist.