Definition Aufzählbarkeit < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:27 Do 19.07.2007 | | Autor: | Mumrel |
| Aufgabe | | Wie wird die Aufzählbarkeit einer Menge für gewöhnlich definiert? |
Also in meinem Info Skript steht, dass eine Menge aufzählbar ist gdw. die Menge leer ist, oder es eine berechenbare Bijektion von [mm] \IN [/mm] und der Menge gibt.
Ich habe im Hinterkopf, aber dass man nur fordert, dass nur eine Surjektion von [mm] \IN [/mm] --> Menge geben muss.
Die Wikipedia würde mir in dem Punkt recht geben, allerdings ist dort von Rekursiver Aufzählbarkeit die Rede.
Gibt es hier einen Unterschied zwischen der "einfachen" Aufzählbarkeit under der rekursiven Aufzählbarkeit?
Das die beiden Definitionen (berechenbar bijektiv, berechenbarsurjektiv) äquivalent sind neheme ich mal nicht an
, nur dass berechenbar surjektiv ev. eine Folgerung von berechenbar bijektiv ist,
Also, ist es ungewöhnlich aufzählbar als berechenbare Bijektion einzuführen, bzw. welche Definition macht mehr Sinn?
Danke und Grüße
Mumrel
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:12 Do 19.07.2007 | | Autor: | Harris |
Also, ich kenne die Definition etwas anders:
Eine Menge M ist abzählbar gdw sie endlich ist oder es eine eine Bijektion von [mm] \IN [/mm] auf M gibt...
Aber ich denke, in deinem Fall wäre "Surjektion" das passende Wort, denn es gibt ja keine Bijektion von ganz [mm] \IN [/mm] auf endliche Mengen
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:27 Fr 20.07.2007 | | Autor: | Mumrel |
Vorsicht, ich habe nach der Definition von aufzählbar gefragt.
Da gibt es einen Unterschied, eben jenen, dass man nur die Bijektionen/Surjektionen (das ist eben die Frage) zulässt die man berechnen kann, für die also ein Algorithmus existiert.
Anscheinden gibt es nämlich abzählbare Mengen die nicht aufzählbar sind und schlimmer noch. In meinem Skript steht, jede unendlich abzählbare Menge enthält unendlich nicht aufzählbare Teilmengen..:)
Aber zumindest die Definition von abzählbar ist bei uns gleich :)
Grüße Mumrel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:19 Fr 20.07.2007 | | Autor: | Zaed |
Hallo,
eine Menge A heißt aufzählbar, genau dann wenn gilt:
die Menge A ist leer oder es existiert eine allgemein rekursive (also eine totale) Funktion mit [mm] f(\IN) = A [/mm]
also haben wir eine totale Funktion [mm] f : \IN \to A [/mm], welche natürlich surjektiv sein muss. Schließlich soll ja gerade [mm] f(\IN) = A [/mm] (das kann man sich dadurch leicht überlegen)
Das da rekursiv aufzählbar steht bedeutet lediglich, dass wir partiell-rekursive Funktionen betrachten. Die Definition ist wegen der Beziehung [mm] P = TM [/mm], wobei P die Klasse aller partiell-rekursiven Funktionen ist und TM die Klasse all jener Funktionen, die Turingberechenbar sind, äquivalent zur Turingaufzählbarkeit.
Wie du siehst musst die Funktion nicht bijektiv sein, sondern lediglich surjektiv... (wieso sollte sie das auch)
Wenn man es ganz genau nimmt darf man sowas auch nicht fordern, sonst waere die Menge {1,2,3,4,5,6,7,8} ja nicht aufzählbar, was ja intuitiv nicht der Fall sein kann.
Die Frage, weshalb die Funktion f aber TOTAL sein muss kannst du dir jetzt vielleicht mal selbst beantworten :D
ich hoffe das hilft dir ein wenig
mfG Zaed
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:15 Fr 20.07.2007 | | Autor: | Mumrel |
> Hallo,
>
> eine Menge A heißt aufzählbar, genau dann wenn gilt:
>
> die Menge A ist leer oder es existiert eine allgemein
> rekursive (also eine totale) Funktion mit [mm]f(\IN) = A[/mm]
>
> also haben wir eine totale Funktion [mm]f : \IN \to A [/mm], welche
> natürlich surjektiv sein muss. Schließlich soll ja gerade
> [mm]f(\IN) = A[/mm] (das kann man sich dadurch leicht überlegen)
Also steht das im direkten Widerspruch zu:
![[]](/images/popup.gif) Mein Skript Seite 569
> Das da rekursiv aufzählbar steht bedeutet lediglich, dass
> wir partiell-rekursive Funktionen betrachten. Die
> Definition ist wegen der Beziehung [mm]P = TM [/mm], wobei P die
> Klasse aller partiell-rekursiven Funktionen ist und TM die
> Klasse all jener Funktionen, die Turingberechenbar sind,
> äquivalent zur Turingaufzählbarkeit.
Ok den Abschnitt versteh ich nicht, aber das liegt daran, dass ich die Begriffe die du verwedndest bei uns noch nicht eingeführt wurden.
> Die Frage, weshalb die Funktion f aber TOTAL sein muss
> kannst du dir jetzt vielleicht mal selbst beantworten :D
Ich würde vermuten, dass das dijenigen Fälle abdeckt, in denen unsere Bildmenge unendlich groß ist. Aber dann würde [mm] f(N_{gerade}) [/mm] = M doch auch genügen. Und diese Abbildung wäre bezogen auf N auch nicht total, dass sie nur jeder zweiten Zahl ein Element aus M zuordnet, man aber trotzdem alle Elemente erreicht.
Danke und Grüße
Mumrel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:24 Fr 20.07.2007 | | Autor: | Mumrel |
Ich sehe gerade, dass im Skript slebst schon ein Widerspruch ist.
Oben wird eine Surjektion gefordert unten eine Bijektion. Ich vermute das ist ein Fehler und es soll unten zweimal Surjektion statt Bijektioin heißen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:25 Mo 23.07.2007 | | Autor: | Zaed |
> > Hallo,
> >
> > eine Menge A heißt aufzählbar, genau dann wenn gilt:
> >
> > die Menge A ist leer oder es existiert eine allgemein
> > rekursive (also eine totale) Funktion mit [mm]f(\IN) = A[/mm]
> >
> > also haben wir eine totale Funktion [mm]f : \IN \to A [/mm], welche
> > natürlich surjektiv sein muss. Schließlich soll ja gerade
> > [mm]f(\IN) = A[/mm] (das kann man sich dadurch leicht überlegen)
>
> Also steht das im direkten Widerspruch zu:
>
> Mein Skript Seite 569
>
Die Definition ist meiner Meinung nach ziemlich schwammig, zudem nicht ganz korrekt. Zumindest würde das im Widerspruch zu jeder Vorleusng stehen, die ich bisher zur theoretischen Informatik gehört habe, da wir den Begriff aufzählbar immer mit surjektiver Abbildung in Verbindung gebracht haben. Bzw. haben wir gefordert [mm] f(\IN) = A [/mm], was ja aber am Ende Surjektivität beschreibt.
> > Das da rekursiv aufzählbar steht bedeutet lediglich, dass
> > wir partiell-rekursive Funktionen betrachten. Die
> > Definition ist wegen der Beziehung [mm]P = TM [/mm], wobei P die
> > Klasse aller partiell-rekursiven Funktionen ist und TM die
> > Klasse all jener Funktionen, die Turingberechenbar sind,
> > äquivalent zur Turingaufzählbarkeit.
> Ok den Abschnitt versteh ich nicht, aber das liegt daran,
> dass ich die Begriffe die du verwedndest bei uns noch nicht
> eingeführt wurden.
Sorry, ich ging davon aus, dass du eine Vorlesung der theoretischen Informatik hoerst, indem es um Berechnbarkeitsmodelle und formale Sprachklassen geht. Dem ist aber leider nicht so, es ist eher eine Einführungsveranstaltung. Deshalb wohl auch die schwammige Definition...
>
> > Die Frage, weshalb die Funktion f aber TOTAL sein muss
> > kannst du dir jetzt vielleicht mal selbst beantworten :D
>
> Ich würde vermuten, dass das dijenigen Fälle abdeckt, in
> denen unsere Bildmenge unendlich groß ist. Aber dann würde
> [mm]f(N_{gerade})[/mm] = M doch auch genügen. Und diese Abbildung
> wäre bezogen auf N auch nicht total, dass sie nur jeder
> zweiten Zahl ein Element aus M zuordnet, man aber trotzdem
> alle Elemente erreicht.
Die Idee der Aufzählbareit ist aber gerade die totale surjektive Abbildung auf die Menge. Du hast zwar im Grunde recht, aber es widerspricht formal ebend leider der Definition, welche gerade so gewählt wurde. (man könnte die Theorie aber damit auch durchführen, aber es macht die Sache nicht einfacher) Dir das jetzt im Detail nahe zu bringen ist schwierig, wenn du in der "theoretischen" Materie noch nicht richtig drinne steckst. Aber ich versuce mal grob die Idee wiederzugeben: Wir fordern eine totale surjektive Abbildung von [mm] \IN [/mm] auf A, damit wir die Elemente von unten nach oben aufzählen können. Wir können uns also eine wahllos geordnete Liste von Elementen aus A beschaffen, indem wir die Liste wie folgt konstruieren (wir konstruieren quasi ein Wörterbuch): [mm] A = \{f(0), f(1), f(2), f(3), ...\} [/mm]. Wir verwenden dabei, (und das ist jetzt der Teil der dir wohl fehlt) dass f berechenbar ist, sogar total (man sagt auch, f ist allgemein-rekursiv). Damit können wir die Liste erschaffen, wir können A also "aufzählen" (und das erade mit [mm] \IN). [/mm] Vor allem können wir mit dieser Konstruktion aber noch folgendes machen: wir können A semi-entscheiden, d.h. wir können testen, ob ein Element in A liegt. Leider liefert uns der Tester im Falle dass das Element nicht in A liegt kein Ergebnis, er wird ins unendliche weiterprüfen. Und genau das ist die Idee des Wörterbruchs, in dem wir linear suchen können, ob unser Element vorhanden ist. (wir wissen ja, dass f berechenbar ist) ...
Aber ich denke, dass du solche Sachverhalte och genau kennenelernen wirst. Dazu gibt es spezielle Vorlesungen, welche auch sehr interessant sind!
>
> Danke und Grüße
> Mumrel
>
mfG Zaed
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:01 Mo 23.07.2007 | | Autor: | Mumrel |
Hi Zaed,
danke nochml für deine ausfühlriche Antwort.
> Die Definition ist meiner Meinung nach ziemlich schwammig,
> zudem nicht ganz korrekt.
Ja, wie oben angemerkt, denke ich müsste es zweimal Surjektion anstatt Bijektion heißen, die textuelle Beschreibung oben stimmt ja, da es heißt jedes Elemnt ist das Bild _mindestens_ einer Zahl.
> > > Das da rekursiv aufzählbar steht bedeutet lediglich, dass
> > > wir partiell-rekursive Funktionen betrachten. Die
> > > Definition ist wegen der Beziehung [mm]P = TM [/mm], wobei P die
> Sorry, ich ging davon aus, dass du eine Vorlesung der
> theoretischen Informatik hoerst, indem es um
> Berechnbarkeitsmodelle und formale Sprachklassen geht. Dem
> ist aber leider nicht so, es ist eher eine
> Einführungsveranstaltung. Deshalb wohl auch die schwammige
> Definition...
Einführung in die Info 1 ja :).
Theo Info hab ich auch schon gehört, eine VL, aber da gings es durchweg nur um Sprachen und Automaten. Berechenbarkeit kommt erst im nächsten Semester.
> Die Idee der Aufzählbareit ist aber gerade die totale
> surjektive Abbildung auf die Menge. Du hast zwar im Grunde
> recht, aber es widerspricht formal ebend leider der
> Definition, welche gerade so gewählt wurde. (man könnte die
> Theorie aber damit auch durchführen, aber es macht die
> Sache nicht einfacher) Dir das jetzt im Detail nahe zu
> bringen ist schwierig, wenn du in der "theoretischen"
> Materie noch nicht richtig drinne steckst. Aber ich versuce
> mal grob die Idee wiederzugeben: Wir fordern eine totale
> surjektive Abbildung von [mm]\IN[/mm] auf A, damit wir die Elemente
> von unten nach oben aufzählen können. Wir können uns also
> eine wahllos geordnete Liste von Elementen aus A
> beschaffen, indem wir die Liste wie folgt konstruieren (wir
> konstruieren quasi ein Wörterbuch): [mm]A = \{f(0), f(1), f(2), f(3), ...\} [/mm].
> Wir verwenden dabei, (und das ist jetzt der Teil der dir
> wohl fehlt) dass f berechenbar ist, sogar total (man sagt
> auch, f ist allgemein-rekursiv). Damit können wir die Liste
> erschaffen, wir können A also "aufzählen" (und das erade
> mit [mm]\IN).[/mm] Vor allem können wir mit dieser Konstruktion aber
> noch folgendes machen: wir können A semi-entscheiden, d.h.
> wir können testen, ob ein Element in A liegt. Leider
> liefert uns der Tester im Falle dass das Element nicht in A
> liegt kein Ergebnis, er wird ins unendliche weiterprüfen.
> Und genau das ist die Idee des Wörterbruchs, in dem wir
> linear suchen können, ob unser Element vorhanden ist. (wir
> wissen ja, dass f berechenbar ist) ...
>
> Aber ich denke, dass du solche Sachverhalte och genau
> kennenelernen wirst. Dazu gibt es spezielle Vorlesungen,
> welche auch sehr interessant sind!
Ja also die Erklärung verstehe ich. Ich muss dabei an die Analogie d. haltproblems denken. Das in dem Sinne ja auch semientscheidbar ist. Wenn der Algo auf die Eingabe hält, dann wissen wir das, wenn nicht, wissen wir nichts. Und in der Prädikatenlogik erster Ordnung sind meines Wissens einege Probleme genauso gestrickt (semi-entscheidbar).
Ok jedenfalls weiß ich jetzt wie die Definition richtig heißen muss :)
Danke und Grüße
Mumrel
|
|
|
|
