HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Minor Mistake in Computability, Complexity, and Languages?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
languagesminorcomputabilitymistakeandcomplexity

Problem

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?

Solution

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}$.

Context

StackExchange Computer Science Q#63284, answer score: 12

Revisions (0)

No revisions yet.