Kleiner Fehler in Berechenbarkeit, Komplexität und Sprachen?

7

In dem Buch Berechenbarkeit, Komplexität und Sprachen (2 nd edition), schreibt Martin Davis in Kapitel 1 (Preliminaries), Abschnitt 2 (Funktionen):

Eine Teilfunktion auf einer Menge ist einfach eine Funktion, deren Domäne eine Teilmenge von . Ein Beispiel für eine Teilfunktion von ist , wobei die Domäne von die Menge der perfekten Quadrate ist.SSN g(n)=ng

So weit so einfach. Aber er geht voran und schreibt ein paar Zeilen später am Ende des Abschnitts:

Wir werden manchmal auf die Idee der Schließung verweisen . Wenn ein Satz ist , und ist eine Teilfunktion , dann wird unter geschlossen , wenn der Bereich von eine Teilmenge von ist . Zum Beispiel wird unter geschlossen , ist aber nicht geschlossen , unter ( wobei eine Gesamtfunktion auf ).SfSS ffSNf(n)=n2h(n)=nhN

So in dem ersten Zitat auf ist ein Beispiel für eine Teilfunktion, während in der zweiten Quote die gleiche Funktion , ein Beispiel für eine ist insgesamt Funktion.nN

Beide Beispiele scheinen sich zu widersprechen. Oder fehlt mir hier etwas in Bezug auf Schließungen?

Gute Nacht Nerd Pride
quelle
1
Dies ist pädagogisch ein schlechtes Beispiel für eine Teilfunktion, da die Domäne nur durch eine willkürliche Definition eingeschränkt ist . Ein besseres Beispiel für eine Teilfunktion ist f (x) = 1 / x , was undefiniert ist, wenn x = 0.
Wildcard
1
@ Wildcard: Wie ist das willkürlich? N ist keine ungerade Wahl für den Bereich von g(n)..
MSalters
@ MSalters, trotzdem ist es eine Wahl wie in willkürlich .
Gute Nacht Nerd Pride
1
@GoodNightNerdPride: Wenn Sie diese Logik verwenden, 1/xist kein besseres Beispiel, da es Bereiche gibt (z. B. projektiv erweiterte reelle Linie), in denen auch dies definiert ist.
MSalters
@ Wildcard Es ist überhaupt nicht willkürlich. g definiert als eine Funktion von N zu N, das ist ein ganz natürliches Objekt. Die Funktion ist an bestimmten Stellen undefiniert, da beispielsweise keine natürliche Zahl vorhanden isty so dass y2=2. Das ist genau das gleiche wie in Ihrem Beispiel: Es ist sehr natürlich, eine Funktion von zu habenR zu Rund die von Ihnen gewählte Funktion ist an einigen Stellen undefiniert, da beispielsweise keine reelle Zahl vorhanden ist y so dass y0=1.
David Richerby

Antworten:

12

Hier gibt es keinen Widerspruch. Der erste Fall definiert die Teilfunktiong:NN gegeben durch

g(n)={xif xN and x2=nundefinedif no such x exists.
Wie der Text sagt, "die Domäne von g ist die Menge der perfekten Quadrate. "

Der zweite Fall definiert die Gesamtfunktion h:NR gegeben durch

h(n)=xif xR0 and x2=n.
Die Domain von h ist die Menge aller natürlichen Zahlen.

Sie sagen, dass dies die gleiche Funktion ist, aber nicht. g(2) ist aber undefiniert h(2) ist definiert (und gleich 2). h ordnet jeder natürlichen Zahl aber eine Quadratwurzel zu g Assoziiert Quadratwurzeln nur mit natürlichen Zahlen, die perfekte Quadrate sind.

N ist geschlossen unter g denn wann immer g ist definiert, g(n)N. N ist nicht geschlossen unter h weil zum Beispiel 2N aber h(2)N.

David Richerby
quelle
+1, obwohl ich denke, dass das Buch fehlerhaft ist, wenn es "f ist eine Teilfunktion auf S" meinen "f ist eine Teilfunktion von Szu einem Satz ".
Ruakh
@ruakh Was ist daran falsch?
David Richerby
Nach meiner Erfahrung ist eine Funktion in einer Menge eine Funktion von dieser Menge zu sich selbst (analog dazu, wie eine Beziehung in einer Menge eine Beziehung ist , es sei denn, Sie fügen explizit einen Modifikator wie "reellwertig" hinzu (damit die Codomäne klar ist) von diesem Satz zu sich selbst). Aber vielleicht ist das kein Fehler und nur eine andere terminologische Tradition?
Ruakh
6

Im zweiten Beispiel h(n) ist für alle natürlichen Zahlen definiert n;; wannn ist kein Quadrat, h(n) ist eine irrationale Größe und insbesondere keine natürliche Zahl.

Mit anderen Worten, die Menge der natürlichen Zahlen wird nicht geschlossen, wenn Quadratwurzeln gezogen werden: zum Beispiel 2 ist keine natürliche Zahl.

Yuval Filmus
quelle
Entschuldigung, ich glaube ich war nicht klar genug. Bitte lesen Sie den vorletzten Absatz, den ich meiner Frage hinzugefügt habe.
Gute Nacht Nerd Pride
4
@ GoodNightNerdPride Ich denke, Yuval ist genau richtig. Im ersten Beispiel ist die Quadratwurzelfunktion eine Teilfunktion vonN zu N;; im zweiten Beispiel ist es eine Gesamtfunktion vonN zu R.
David Richerby