BuK/IIm20/Begriffssammlung

Wiki-Quelltext dieser Seite.

== 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 [https://en.wikipedia.org/wiki/Set_(mathematics)#Euler_and_Venn_diagrams 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 ==

[[Bild:Mengen_Rot.png]]