BuK-KA-Durchschnittsmenge
Aus ProgrammingWiki
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 1
Gegeben sind die surjektiven, berechenbaren Funktionen $ f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow M_{2} $. Gesucht ist eine surjektive, berechenbare Aufzählfunktion $ h: \N \rightarrow M_{1} \cap M_{2} $.
Es werden folgende zwei Fälle unterschieden:
- $ M_{1} \cap M_{2} = \emptyset $
- $ 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 $
Beweis 2
Gegeben sind die surjektiven, berechenbaren Funktionen $ f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow M_{2} $. Gesucht ist eine surjektive, berechenbare Aufzählfunktion $ h: \N \rightarrow M_{1} \cap M_{2} $.
Analog zum ersten Beweis werden die folgenden zwei Fälle unterschieden:
- $ M_{1} \cap M_{2} = \emptyset $
- $ 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 zwei nichtleere, endliche Mengen $ F = \big\{f(j),\:j = 0,1,\dotsc,i \big\} \text{ und } G = \big\{g(j),\:j = 0,1,\dotsc,i \big\} $.
- Die Aufzählfunktion $ h $ definert sich nun aus
$$h(i)=\begin{cases} f(i), \text{ wenn } f(i) \in G\\ k(i), \text{ sonst}\\ \end{cases}$$
$$\text{ mit } k(i)=\begin{cases}
g(i), \text{ wenn } g(i) \in F\\
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. Außerdem sind $ F $ und $ G $ endliche Mengen und daher entscheidbar. $ \square $
Implementierung
Die Herausforderung bei der Implemtierung der Aufzählungsfunktion $ h $ ergibt sich aus den Vergleichen, da die Reihenfolgen der Mengen $ M_{1} \text{ und } M_{2} $ verschieden seien können. Dem kann durch zwei Pools entgegengewirkt werden, welche je Menge die Elemente aufbehalten, welche noch zu keinem erfolgreichen Vergleich führten.
