7
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ This is pedagogically a bad example of a partial function, because the domain is restricted only by arbitrary definition. A better example of a partial function is f(x) = 1/x, which is undefined when x = 0. $\endgroup$
    – Wildcard
    Commented Sep 9, 2016 at 3:06
  • 1
    $\begingroup$ @Wildcard: How is this arbitrary? $\mathbb{N}$ is not an odd choice for the range of $g(n)$.. $\endgroup$
    – MSalters
    Commented Sep 9, 2016 at 8:01
  • $\begingroup$ @MSalters, nethertheless it's a choice as in arbitrary. $\endgroup$
    – Good Night Nerd Pride
    Commented Sep 9, 2016 at 8:06
  • 1
    $\begingroup$ @GoodNightNerdPride: If you use that logic, $1/x$ is not a better example, because there are ranges (e.g. projectively extended real line) in which that too is defined. $\endgroup$
    – MSalters
    Commented Sep 9, 2016 at 8:13
  • $\begingroup$ @Wildcard It's not arbitrary at all. $g$ defined as a function from $\mathbb{N}$ to $\mathbb{N}$, which is a completely natural object. The function is undefined in certain places because, e.g., there is no natural number $y$ such that $y^2=2$. That's just the same as your example: it's very natural to have a function from $\mathbb{R}$ to $\mathbb{R}$, and the function you've chosen is undefined in some places because, e.g., there's no real number $y$ such that $y\cdot0=1$. $\endgroup$
    – David Richerby
    Commented Sep 9, 2016 at 8:59

2 Answers 2

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ +1, though I think the book is in error when it uses "$f$ is a partial function on $S$" to mean "$f$ is a partial function from $S$ to some set". $\endgroup$
    – ruakh
    Commented Sep 9, 2016 at 20:23
  • $\begingroup$ @ruakh What's wrong with that? $\endgroup$
    – David Richerby
    Commented Sep 9, 2016 at 20:32
  • $\begingroup$ In my experience, unless you explicitly add a modifier like "real-valued" (so that the codomain is clear), a function on a set is a function from that set to itself (analogously to how a relation on a set is a relation from that set to itself). But maybe that's not an error, and is just a different terminological tradition? $\endgroup$
    – ruakh
    Commented Sep 9, 2016 at 22:34
6
$\begingroup$

In the second example, $h(n)$ is defined for all natural numbers $n$; when $n$ is not a square, $h(n)$ is some irrational quantity, and in particular not a natural number.

In other words, the set of natural numbers is not closed under taking square roots: for example, $\sqrt{2}$ is not a natural number.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry, I think I wasn't clear enough. Please see the 2nd to last paragraph I added to my question. $\endgroup$
    – Good Night Nerd Pride
    Commented Sep 8, 2016 at 21:10
  • 4
    $\begingroup$ @GoodNightNerdPride I think Yuval is exactly right. In the first example, the square root function is a partial function from $\mathbb{N}$ to $\mathbb{N}$; in the second example, it's a total function from $\mathbb{N}$ to $\mathbb{R}$. $\endgroup$
    – David Richerby
    Commented Sep 8, 2016 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.