BuK-KA-Durchschnittsmenge
Inhaltsverzeichnis |
Aufgabenstellung
Weisen Sie nach, dass die Durchschittsmenge (Schnittmenge) zweier aufzählbarer Mengen M_{1},M_{2} \subseteq A^{*} eine aufzählbare Menge ist. Implementieren Sie eine zugehörige Scheme-Repräsentation.
Satz
Die Durchschnittsmenge M_{1} \cap M_{2} zweier aufzählbarer Mengen M_{1},M_{2} \subseteq A^{*} ist eine aufzählbare Menge.
Beweis
Gegeben sind die Aufzählprozeduren für die surjektiven Funktionen f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow M_{2} . Gesucht ist eine Aufzählfunktion h: \N \rightarrow M_{1} \cap M_{2} mit
h(i)=\begin{cases} f(i), \text{ wenn } \chi_{M_{1} \cap M_{2}}(f(i))\\ h(i+1), \text{ sonst}\\ \end{cases}Die Schnittmenge M_{1} \cap M_{2} ist aufzählbar, wenn h berechenbar ist. f(i) ist für alle i \in \N berechenbar, da M_{1} eine aufzählbare Menge ist.
Außerdem ist \chi_{M_{1} \cap M_{2}}(w), w \in A^{*} mit
\chi_{M_{1} \cap M_{2}}(w)=\begin{cases} wahr, \text{ wenn } \chi_{M_{1}}(w) \wedge \chi_{M_{2}}(w)\\ \perp, \text{ sonst}\\ \end{cases}berechenbar, da die partiellen semi-chrakteristischen Funktionen \chi_{M_{1}} \text{ und } \chi_{M_{2}} berechenbar sind. \square