KA

Aus ProgrammingWiki
< BuK < IIm11 < Studenten < sitosalz
Archivierte Version vom 2012-04-03T21:04:09+00:00. Aktuelle Version

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.