Problem Detail: In the book
Computability, Complexity, and Languages (2nd edition), Martin Davis writes in chapter 1 (Preliminaries), section 2 (Functions):
A partial function on a set $S$ is simply a function whose domain is a subset of $S$. An example of a partial function on $mathbb{N}$ is given by $g(n) = sqrt n$, where the domain of $g$ is the set of perfect squares.
So far so simple. But he goes ahead and writes a couple lines later at the end of the section:
We will sometimes refer to the idea of closure. If $S$ is a set and $f$ is a partial function on $S$, then $S$ is closed under $f$ if the range of $f$ is a subset of $S$. For example, $mathbb{N}$ is closed under $f(n) = n^2$, but is not closed under $h(n) = sqrt n$ (where $h$ is a total function on $mathbb{N}$).
So in the first quote $sqrt n$ on $mathbb{N}$ is an example for a partial function, whereas in the second quote the same function is an example for a total function. Both examples seem to contradict each other. Or am I missing something in regard to closures here?
There’s no contradiction, here. The first case defines the partial function $gcolon mathbb{N}tomathbb{N}$ given by $$g(n) = begin{cases} x &text{if $xinmathbb{N}$ and }x^2=n text{undefined} &text{if no such $x$ exists.} end{cases}$$ As the text says, “the domain of $g$ is the set of perfect squares.” The second case defines the total function $hcolonmathbb{N}tomathbb{R}$ given by $$h(n) = x quad text{if }xinmathbb{R}_{geq 0} text{ and } x^2=n,.$$ The domain of $h$ is the set of all the natural numbers. You say that these are the same function, but they are not. $g(2)$ is undefined but $h(2)$ is defined (and equal to $sqrt{2}$). $h$ associates a square root with every natural number but $g$ only associates square roots with natural numbers that are perfect squares. $mathbb{N}$ is closed under $g$ because, whenever $g$ is defined, $g(n)inmathbb{N}$. $mathbb{N}$ is not closed under $h$ because, for example, $2inmathbb{N}$ but $h(2)notinmathbb{N}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63284
Related
