IIm18-Kreativaufgabe2

Aus ProgrammingWiki

Satz: Die Durchschnittsmenge $M_1$ $M_2$ zweier aufzählbar unendlicher Mengen $M_1, M_2$ 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(n)=\begin{cases} f(x), \text{ wenn } f(x) = g(y) \text{ mit } \pi_{n}(x,y)\\ a, \text{ sonst}\\ \end{cases} \text{ und }\;a \in M_{1} \cap M_{2}\text{ . }$$

Auszug aus Tabelle der Cantorschen Paarungsfunktion $ \pi_{n}(x,y)$

x\ y	0	1	2	3	4	...
0	0	2	3	9	10	...
1	1	4	8	11	…	...
2	5	7	12	...	…	...
3	6	13	...	...	…	...
4	14	…	…	…	…	...
...	...	…	…	…	…	...

Da wir je eine Aufzählprozedur für die Menge M1 und die Menge M2 besitzen können wir dies ausnutzen. Dabei ist x der Index für die Menge 1 und y der Index für die Menge 2. Diesen Index übergeben wir der Aufzählprozedur und erhalten das Element an der Stelle x bzw. y.

Die natürliche Zahl die der Aufzählprozedur für h als Parameter übergeben wird, wird nun in die Umkehrfunktion der Cantorischen Paarungsfunktion eingesetzt. Anschaulich heißt das: Wir schauen in der Tabelle nach der Zelle wo wir die natürliche Zahl n finden und lesen x und y ab. Das abgelesene x setzen wir in f(x) ein und das y in g(x). Anschließend wird verglichen ob die beiden Elemente aus M1 und M2 identisch sind. Sind sie es, wird das Element zurückgegeben ansonsten wird a zurückgeggeben.(a ist ein Element welches sicher ein Element ist welches in beiden Mengen enthalten ist.)

Damit ist sichergestellt, dass alle Elemente aus beiden Mengen berücksichtigt werden. Die Cantorsche Paarungsfunktion und deren Umkehrfunktion ist berechenbar und h(n) ist auch berechenbar.