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