Kleiner Fehler in Berechenbarkeit, Komplexität und Sprachen?

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. $S$ $S$ $\mathbb{N}$ $g(n) = \sqrt n$ $g$

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 ). $S$ $f$ $S$ $S$ $f$ $f$ $S$ $\mathbb{N}$ $f(n) = n^2$ $h(n) = \sqrt n$ $h$ $\mathbb{N}$

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. $\sqrt n$ $\mathbb{N}$

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

mathematical-foundations Gute Nacht Nerd Pride
quelle

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

@ Wildcard: Wie ist das willkürlich?

N

$\mathbb{N}$ ist keine ungerade Wahl für den Bereich von

g (n)

$g(n)$ ..

MSalters

@ MSalters, trotzdem ist es eine Wahl wie in willkürlich .

Gute Nacht Nerd Pride

@GoodNightNerdPride: Wenn Sie diese Logik verwenden,

1 / x

$1/x$ ist 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

$g$ definiert als eine Funktion von

N

$\mathbb{N}$ zu

N

$\mathbb{N}$ , das ist ein ganz natürliches Objekt. Die Funktion ist an bestimmten Stellen undefiniert, da beispielsweise keine natürliche Zahl vorhanden ist

y

$y$ so dass

y^{2} = 2

$y^2=2$ . Das ist genau das gleiche wie in Ihrem Beispiel: Es ist sehr natürlich, eine Funktion von zu haben

R

$\mathbb{R}$ zu

R

$\mathbb{R}$ und die von Ihnen gewählte Funktion ist an einigen Stellen undefiniert, da beispielsweise keine reelle Zahl vorhanden ist

y

$y$ so dass

y \cdot 0 = 1

$y\cdot0=1$ .

David Richerby

Antworten:

Hier gibt es keinen Widerspruch. Der erste Fall definiert die Teilfunktion $g\colon \mathbb{N}\to\mathbb{N}$ gegeben durch

g (n) = {\begin{cases} x & if x \in N and x^{2} = n \\ undefined & if no such x exists. \end{cases}

$g(n) = \begin{cases} x &\text{if $x\in\mathbb{N}$ and }x^2=n\\ \text{undefined} &\text{if no such $x$ exists.} \end{cases}$ Wie der Text sagt, "die Domäne von

g

$g$ ist die Menge der perfekten Quadrate. "

Der zweite Fall definiert die Gesamtfunktion $h\colon\mathbb{N}\to\mathbb{R}$ gegeben durch

h (n) = x if x \in R_{\geq 0} and x^{2} = n .

$h(n) = x \quad \text{if }x\in\mathbb{R}_{\geq 0} \text{ and } x^2=n\,.$ Die Domain von

h

$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 $\sqrt{2}$ ). $h$ ordnet jeder natürlichen Zahl aber eine Quadratwurzel zu $g$ Assoziiert Quadratwurzeln nur mit natürlichen Zahlen, die perfekte Quadrate sind.

$\mathbb{N}$ ist geschlossen unter $g$ denn wann immer $g$ ist definiert, $g(n)\in\mathbb{N}$ . $\mathbb{N}$ ist nicht geschlossen unter $h$ weil zum Beispiel $2\in\mathbb{N}$ aber $h(2)\notin\mathbb{N}$ .

David Richerby
quelle

+1, obwohl ich denke, dass das Buch fehlerhaft ist, wenn es "

f

$f$ ist eine Teilfunktion auf

S

$S$ " meinen "

f

$f$ ist eine Teilfunktion von

S

$S$ zu 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

Im zweiten Beispiel $h(n)$ ist für alle natürlichen Zahlen definiert $n$ ;; wann $n$ 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 $\sqrt{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

@ GoodNightNerdPride Ich denke, Yuval ist genau richtig. Im ersten Beispiel ist die Quadratwurzelfunktion eine Teilfunktion von

N

$\mathbb{N}$ zu

N

$\mathbb{N}$ ;; im zweiten Beispiel ist es eine Gesamtfunktion von

N

$\mathbb{N}$ zu

R

$\mathbb{R}$ .

David Richerby