[Solved]: Minor Mistake in Computability, Complexity, and Languages?

Problem Detail: 

In the book Computability, Complexity, and Languages (2^nd 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?

Asked By : Good Night Nerd Pride

Answered By : David Richerby

There's no contradiction, here. The first case defines the partial function $g\colon \mathbb{N}\to\mathbb{N}$ given by $$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}$$ As the text says, "the domain of $g$ is the set of perfect squares."

The second case defines the total function $h\colon\mathbb{N}\to\mathbb{R}$ given by $$h(n) = x \quad \text{if }x\in\mathbb{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)\in\mathbb{N}$. $\mathbb{N}$ is not closed under $h$ because, for example, $2\in\mathbb{N}$ but $h(2)\notin\mathbb{N}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63284