IIm18-Kreativaufgabe2

Wiki-Quelltext dieser Seite.

<language>FLACI_</language>
Satz: Die Durchschnittsmenge $M_1$ <math>\cap</math> $M_2$ zweier aufzählbar unendlicher Mengen $M_1, M_2$ <math>\subseteq</math> A* ist eine aufzählbare Menge.

== ==
gegeben: die surjektiven, berechenbaren Funktionen $ f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow  M_{2} $. 



== ==
z.z: Gesucht ist eine surjektive, berechenbare Aufzählfunktion $ h: \N \rightarrow M_{1} \cap M_{2} $.

== == 
Lösung:

Es werden folgende zwei Fälle unterschieden:

# $ M_{1} \cap M_{2} = \emptyset $
# $ M_{1} \cap M_{2} \neq \emptyset $

Da $ M_{1} \cap M_{2} $ nur eine leere oder eine nichtleere Menge sein kann, ist diese Fallunterscheidung vollständig.


;Fall 1
: $ M_{1} \cap M_{2} $ ist aufzählbar.
;Fall 2
: Wir definieren die Aufzählfunktion $ h: \N \rightarrow M_{1} \cap M_{2} $ mit 

$$h(i)=\begin{cases}
f(x), \text{ wenn } f(x) = g(y) \text{ mit } \pi_{i}(x,y)\\
a, \text{ sonst}\\
\end{cases} \text{ und }\;a \in M_{1} \cap M_{2}\text{ . }$$ 

: $ h $ ist berechenbar, da $ f $ und $ g $ für alle natürlichzahligen Argumente berechenbar sind. Auch ist die Umkehrung der cantorschen Paarungsfunktion $ \pi_{i}(x,y) $ für alle $ i \in \N $ berechenbar. $ \square $