BuK-KA-Durchschnittsmenge

Aus ProgrammingWiki
< BuK < IIm11
Archivierte Version vom 2014-05-01T22:52:55+00:00. Aktuelle Version

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
Wenn M_{1} \cap M_{2} eine nichtleere Menge ist, dann existiert a mit a \in M_{1} \cap M_{2} . Die Aufzählfunktion h: \N \rightarrow M_{1} \cap M_{2} ist dann definiert mit
h(i)=\begin{cases} f(x), \text{ wenn } f(x) = g(y) \text{ mit } \pi_{i}(x,y)\\ a, \text{ sonst}\\ \end{cases}
h ist berechenbar, da f und g für alle natürlichzahligen Argumente berechenbar sind. Auch ist die Umkehrung der Cantorsche 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 werde 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(i),\:j = 0,1,\dotsc,i \big\} .


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

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.