BuK-KA-Durchschnittsmenge

Aus ProgrammingWiki
< BuK < IIm11

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:

  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(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:

  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 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.