Begriffssammlung
Inhaltsverzeichnis |
TODO
- Unterschiede Mengen und Funktionen
- Sätze mit aufnehmen, Beweise?
Menge
Eine Sammlung verschiedener Elemente (engl. "A set is a collection of distinct elements").
Zwei Mengen sind genau dann gleich, wenn sie genau die selben Elemente enthalten.
Die leere Menge (\emptyset oder \{\}) ist die Menge, die keine Elemente hat.
Darstellung
Das Euler-Diagramm versucht, Mengen zu veranschaulichen, indem sie als Schlaufen gezeichnet werden, die ihre Elemente umschließen. Ist eine Menge Teilmenge einer anderen, dann liegt ihre Schlaufe vollständig innerhalb der der enthaltenden Menge.
Das Venn-Diagramm versucht, alle Zugehörigkeits-Möglichkeiten für die Elemente von n beliebigen Mengen aufzuzeigen. Dabei spielt es keine Rolle, ob einige Bereiche für eine Belegung konkreter Mengen gar keine Elemente enthalten. Es entstehen n^2 Zonen, die alle Möglichkeiten repräsentieren.
(siehe en.wikipedia.org/wiki/Set_(mathematics)#Euler_and_Venn_diagrams)
Funktion
surjektiv
injektiv
Abzählbarkeit
Eine unendliche Menge M heißt abzählbar unendlich, wenn es eine bijektive Funktion \mathbb{N} \rightarrow M gibt. Gibt eine solche Funktion nicht, so ist M überabzählbar unendlich.
Berechenbarkeit
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.
Entscheidbarkeit
Eine Menge M \subseteq A^\ast ist (absolut) entscheidbar, wenn M zu A^\ast relativ entscheidbar ist, d.h. wenn \chi_{M, A^\ast}, kurz: \chi_M, mit
\chi_M(w) = \begin{cases} wahr, & \mbox{wenn } \mbox{$w \in M$} \\ falsch, & \mbox{wenn } \mbox{$w \in A^\ast \setminus M$} \end{cases}eine total berechenbare Funktion ist.
Semi-entscheidbarkeit
Eine Menge M \subseteq A^\ast ist (absolut) semi-entscheidbar, wenn die partielle (semi-charakteristische) Funktion \chi'_M : A^\ast \rightarrow \{wahr\} mit:
\chi'_M(w) = \begin{cases} wahr, & \mbox{wenn } \mbox{$w \in M$;} \\ \perp, & \mbox{sonst.}\end{cases}berechenbar ist.
Aufzählbarkeit
Eine Menge M \subseteq A^\ast heißt (rekursiv) aufzählbar, engl. recursively enumerable, wenn es entweder eine total berechenbare surjektive Funktion f: \mathbb{N} \rightarrow M gibt, oder es gilt M = \emptyset. Man nennt f eine Aufzählprozedur oder eine Aufzählverfahren von M.
Mengenverhältnisse
