IIm18-Kreativaufgabe2

Aus ProgrammingWiki
Archivierte Version vom 2019-06-14T08:48:28+00:00. Aktuelle Version

Satz: Die Durchschnittsmenge M_1 \cap M_2 zweier aufzählbar unendlicher Mengen M_1, M_2 \subseteq 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:

  1. M_{1} \cap M_{2} = \emptyset
  2. 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