Reduzierbarkeit < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen Sie die folgenden Behauptungen für A,B [mm] \subseteq \IN
[/mm]
Es sei B [mm] \not= \emptyset [/mm] , dann gilt A [mm] \le \pi(A [/mm] x B). |
Hallo!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Mir ist leider nicht klar was [mm] \pi(AxB) [/mm] bedeutet.
Handelt es sich hier um die Cantorsche Tupelfunktion von (AxB), wenn ja wie sieht das denn dann aus?
Und wie kann ich dann von A auf [mm] \pi [/mm] (AxB) reduzieren???
Wäre für hilfe sehr dankbar!
LG,
Gaenseblume
|
|
| |
|
Hallo,
vermutlich ist damit eine solche Tupelfunktion gemeint, d.h. eine berechenbare
injektive Abb [mm] \pi\colon \IN\times \IN\to\IN [/mm] , so dass das Problem
[mm] \{ n\in\IN | \exists x,y\in \IN mit \pi(x,y)=n\} [/mm] entscheidbar ist und die Projektionen berechenbar.
Dann waehle [mm] b_0\in B\neq\emptyset [/mm] und reduziere
[mm] A\leq \pi (A\times [/mm] B) vermoege [mm] x\to \pi(x,b_0).
[/mm]
Zur Korrektheit:
Es ist zu zeigen, dass fuer alle [mm] x\in \IN [/mm] gilt:
[mm] x\in [/mm] A genau dann, wenn [mm] \pi(x,b_0)\in A\times [/mm] B.
Dass schaffst Du, oder ?
Viele Gruesse,
Mathias
|
|
|
| |
|
Hallo Mathias!
Ich habe eine ähnliche Aufgabe!
Könnte in diesem Fall nicht auch [mm] \pi(AxB) [/mm] = {<a,b> [mm] \in \IN [/mm] | (a,b) [mm] \in [/mm] AxB}
sein?
Das hatte ich eigentlich wenn auch unsicher angenommen. Allerdings wüsste ich auch nicht wirklich wie man dann das A auf [mm] \pi(AxB) [/mm] reduzieren könnte.
LG,
Nicole
|
|
|
| |
|
Guten Morgen Nicole,
ja genau, so hab ich das auch interpretiert:
[mm] \pi (A\times [/mm] B) = [mm] \{ < x,y> | x\in A \wedge y\in B\}
[/mm]
Also nochmal die Reduktion von A auf [mm] \pi (A\times [/mm] B):
Waehle [mm] b_0\in [/mm] B (wir brauchen also als Vorauss. [mm] B\neq\emptyset), [/mm] dann definiere
[mm] f\colon \IN \to \IN [/mm] durch f(x) := [mm] [/mm]
Dann gilt fuer alle [mm] x\in\IN [/mm] folgendes:
[mm] x\in [/mm] A [mm] \Leftrightarrow [/mm] f(x) [mm] \in \pi(A\times [/mm] B).
Also ist f eine solche Reduktion - dass f rekursiv ist, folgt aus der Rekursivitaet der
Paarfunktion < >.
Viele Gruesse und
guten Start in die Woche,
Mathias
|
|
|
|
