Suppose $d$ is a metric on the set $X$. For $x$, $y \in X$ define the function $c$ by $c(x,y) = \lceil d(x,y) \rceil$. Show that $c$ is a metric on $X$.

(The reason I put the question here is because I was wondering if it was possible to "discretise" a metric, and the simplest way that I thought of was to use the ceiling.)

  • 2
    $\begingroup$ I am confused as to why you asked and then answered your own question at the same time. If you know the solution, why did you ask? $\endgroup$ – N. Owad Nov 17 '14 at 16:59
  • 3
    $\begingroup$ Asking and answering your own question is explicitly encouraged on Stack Exchange: blog.stackoverflow.com/2011/07/… My own reason is because I thought it was interesting enough that someone else may want to know the answer in the future. $\endgroup$ – DavidButlerUofA Nov 17 '14 at 22:10
  • $\begingroup$ Comment after 5 years ;-) Your metric $c$ generates the discrete topology on $X$. If $x \ne y$, then $c(x,y) \ge 1$. Hence the open ball with radius $1$ and center $x$ only contains $x$. $\endgroup$ – Paul Frost Sep 30 at 23:24

To be a metric, $c$ must satisfy the following three conditions:

  1. $c(x,y) \geq 0$ for all $x$, $y \in X$.
  2. $c(x,y) = 0$ if and only if $x=y$.
  3. $c(x,y) = c(y,x)$ for all $x$, $y\in X$.
  4. $c(x,z) \leq c(x,y) + c(y,z)$ for all $x$, $y$, $z \in X$ (the triangle inequality)

Before we start considering these four conditions, let us consider the properties of the ceiling function $t \mapsto \lceil t \rceil$ for $t \geq 0$.

The ceiling function is non-decreasing, so if $s \leq t$ then $\lceil s \rceil \leq \lceil t\rceil$.

Also, given two numbers $s$ and $t$ with $s, t \geq 0$, $\lceil t \rceil$ is the smallest integer greater than or equal to $t$, so we have that $t \leq \lceil t \rceil$ and similarly $s \leq \lceil s \rceil$. Thus $s + t \leq \lceil s \rceil + \lceil t \rceil$. However, $\lceil s + t \rceil$ is the smallest integer greater than or equal to $s+t$ and $\lceil s \rceil + \lceil t \rceil$ is an integer greater than or equal to $s+t$. Therefore it must be that $\lceil s+t \rceil \leq \lceil s\rceil + \lceil t\rceil$.

Now we consider the four conditions in turn:

  1. Since $d(x,y) \geq 0$, $\lceil d(x,y) \rceil \geq \lceil 0 \rceil = 0$. So $c(x,y) \geq 0$.

  2. $c(x,y) = 0$ if and only if $\lceil d(x,y) \rceil = 0$, if and only if $d(x,y) = 0$ (since $d(x,y)$ is nonnegative), if and only if $x=y$.

  3. $c(x,y) = \lceil d(x,y) \rceil = \lceil d(y,x) \rceil = c(y,x)$ for all $x, y \in X$.

  4. Given $x, y, z \in X$, $$ \begin{align} d(x,z) &\leq d(x,y) + d(y,z)\\ \lceil d(x,z) \rceil &\leq \lceil d(x,y) + d(y,z) \rceil\\ &\leq \lceil d(x,y) \rceil + \lceil d(y,z) \rceil \end{align} $$ So $c(x,z) \leq c(x,y) + c(y,z)$.

Therefore $c$ is a metric on $X$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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