BuK/IIm12/Studenten/sidahorb/saetze

Wiki-Quelltext dieser Seite.

* 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.