BuK/IIm11/Studenten/sitosalz/KA

Wiki-Quelltext dieser Seite.

=Kreativaufgaben=

==Schnittmengen-Aufgabe==
'''Satz:''' 

Die Durchschnittsmenge $M_1 \cap M_2$ zweier aufzählbar unendlicher Mengen $M_1, M_2 \subseteq A^*$ ist eine aufzählbare Menge.

'''Beweis:'''

Gegeben sind die Aufzählprozeduren $f$ und $g$ für die surjektiven Funktionen $f: N \mapsto M_1$ und $g: N \mapsto M_2$.

Hierfür kann eine Aufzählfunktion definiert werden: $h: \N \mapsto M_1 \subseteq M_2$ mit

$$
h(i) = \begin{cases}

f(\frac{i}{2}), & \text{wenn } i \text{ gerade };\\
g(\frac{i - 1}{2}), & \text{sonst}.
\end{cases}
$$

$h$ ist berechenbar, da $f$ und $g$ fur alle natürlichzahligen Argumente berechenbar sind.

'''Idee:'''
Falls die Schnittmenge nicht leer ist, gibt es zwei Pools, welche nachschauen ob das jeweilige Element $f(n)$, bzw. $g(n)$ in dem anderen Pool enthalten ist.