BuK/IIm20/Begriffssammlung

Wiki-Quelltext dieser Seite.

== TODO ==

- 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 ==

Eine Funktion ist eine Relation zwischen zwei Mengen $A$ und $B$, die Elemente aus $A$ auf Elementen von $B$ abgebildet.

$f: A \rightarrow B$

$f: x \mapsto y$

$f(x) = y$

$(x, y) \in f$

=== total und partiell ===

Eine Funktion $f: X \rightarrow Y$ mit $D_{\!f} = X$ heißt '''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.

=== Injektivität ===

Eine Funktion ist injektiv, wenn jedem Element der Zielmenge höchstens ein Funktionsargument zugeordnet wurde – die Zuordnung also ein-eindeutig ist.

Ist eine Funktion injektiv, muss gelten: $f(x_1) = y = f(x_2) \Longrightarrow x_1 = x_2$

=== Surjektivität ===

Eine Funktion ist surjektiv, wenn jedem Element der Zielmenge mindestens ein Funktionsargument zugeordnet wurde – also jedes über die Zuordnung erreichbar ist und keines ausgelassen wird.

${\large\forall} y \in R \hspace{10px} {\large\exists} x \in D : \hspace{8px} f(x) = y \hspace{1cm}$ (wobei $R$ die Bildmenge und $D$ der Definitionsbereich sind)

=== Bijektivität ===

Eine Funktion ist bijektiv, wenn sie sowohl injektiv als auch surjektiv ist, wenn auf jedes Element der Zielmenge genau ein Funktionsargument abgebildet wird.

== Eigenschaften von Mengen ==

=== 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'''.


=== 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 ein '''Aufzählverfahren''' von $M$.

''Satz:'' Eine Menge $M$ ist genau dann '''aufzählbar''', wenn sie '''semi-entscheidbar''' ist.

''Satz:'' Jede Teilmenge einer '''abzählbaren''' Menge ist '''abzählbar''', aber nicht jede Teilmenge einer '''aufzählbaren''' Menge ist '''aufzählbar'''.

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


=== Turing-aufzählbar ===
Eine Menge $M \subseteq A^\ast$ heißt (rekursiv) '''Turing-aufzählbar''' (engl. recursively enumerable), wenn es entweder eine total Turing-berechenbare surjektive Funktion $f: \mathbb{N} \rightarrow M$ gibt, oder es gilt $M = \emptyset$. Man nennt $f$ eine '''Aufzählprozedur''' oder ein '''Aufzählverfahren''' von $M$.

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

''Satz:'' Wenn die Menge $M$ '''entscheidbar''' ist, dann ist $M$ '''aufzählbar'''.
''(Die Umkehrung dieses Satzes gilt nicht!)''

''Satz:'' Eine Menge $M$, mit $M \subseteq A^\ast$, ist '''entscheidbar''' genau dann, wenn $M$
'''und''' $A^\ast \backslash M$ ''(Komplementmenge)'' '''aufzählbare''' Mengen sind.

=== Turing-entscheidbar ===

Eine Menge $M \subseteq A^\ast$ ist (absolut) '''Turing-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 Turing-berechenbare Funktion ist.

== Eigenschaften von Funktionen ==

=== 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. ("effektiv" = es muss ein entsprechendes Verfahren geben)

=== Turing-Berechenbarkeit ===

Eine Funktion $f: \sum^\ast \rightarrow \sum^\ast$ heißt '''Turing-berechenbar''', wenn es
eine (deterministische) Turing-Maschine $M$ gibt, so dass für alle $w, y \in \sum^\ast$ gilt: $f(w) = y$ genau dann, wenn $q_0\ w \stackrel{\ast}{\vdash} q_e\ y, q_e \in E$.





== Mengenverhältnisse ==

[[Bild:Mengen_Rot.png]]