Lemma for $d(p,q)$ to be a metric for $\mathbb{R}^1$.

Question

I have this exercise where I have to show whether or not $d(p,q)$ is a metric for $X = \mathbb R^1$, and I have come up with this lemma to help me with it. I need help proving it (if it is true).

The requiements for a metric is that a) $d(p,q) > 0$ unless $p=q$, b) $d(p,q) = d(q,p)$, and c) $d(p,q) \leq d(p,r) + d(r,q)$.

Lemma. This works when $p,q$ only appear in the formula for $d(p,q)$ in the pair $|p-q|$, e.g. $d(p,q) = \frac{|p-q|}{1 + |p-q|}$ and $X$ is $\mathbb{R}^1$. Denote $f(x)$ to be the function $d(p,q)$ except $|p-q|$ replaced with $x$, i.e. in the above example $f(x) = \frac{x}{1+x}$. Then if a) and b) are true, for c) to be true it is sufficient that $f'(x) \geq 0$ and $f''(x) < 0$ for $x \geq 0$. In other words, $f(x)$ must increase at a rate less than or equal to a linear function.

Proof. WLOG $p<q$. If $r\leq p\leq q$ or $p\leq q\leq r$, $c)$ is clear because $f'(x) \geq 0$.

So consider $p<r<q$. Let $a = r-p$, $b = q-r, a+b = q-p$. We have $f(a+b) \leq f(a) + f(b)$ because $f'' \leq 0$. Thus $c)$ is proven. (This is the part I'm not sure about)

Is this lemma correct? Is the proof correct?

---

EDIT: Refinement for the $p<r<q$ case:

$f(a+b) \leq f(a) + f(b) \Leftrightarrow f(a+b) - f(b) \leq f(a) - f(0)$

We have that $\displaystyle \int_{b}^{a+b} f' \leq \int_0^a f'\Leftrightarrow f(a+b) - f(b) \leq f(a) - f(0)$. Let $A_{f,x,y}$ represent the average value of $f$ from $x$ to $y$. Since $f'' \leq 0$, $f'$ is non-increasing, so $A_{f',b,a+b} \leq A_{f',0,a}$. Furthermore $\displaystyle \int_a^b f = (b-a)A_{f,a,b}$, so $\displaystyle \int_{b}^{a+b} f' \leq \int_0^a f'$.

---

EDIT I believe the lemma is also biconditional.

Given: A metric $d(p,q)$ described as above where there is only $|p-q|$.

If: $a)$ holds, $f' \geq 0$, and $f'' \leq 0$ for $x \geq 0$

Then: $d$ is a metric.

Above I have already proved the forward case. For the backwards case I will prove the inverse.

If: any of the requirements above do not hold

Then: $d$ is not a metric.

If $a)$ doesn't hold,then clearly it's not a metric.

If $f' < 0$, then by $a)$ it starts at $f(0)=0$ so $f$ becomes negative, so $a)$ doesn't hold, so it's not a metric.

If $f' > 0$, then $A_{f', b, a+b} > A_{f', 0, a}$ so the integral equality above for $c)$ doesn't hold, so it is not a metric.

Answer 1

Your idea to show a more abstract result is good, but you must be more precise in both the formulation and proof of your lemma. The statement you want to prove is true, although you don't have to require $f$ to be non-decreasing — every non-negative, concave function must be non-decreasing (see below).

The problem with your statement of the lemma itself is that the first part is purely verbal and that parts of the proof are already included in the statement. You first need to formalize that your lemma is just about metrics where the arguments $p$ and $q$ appear as $|p-q|$. Your technique of starting with a metric $d$ and then trying to "extract" a function $f$ such that $d(p, q) = f(|p-q|)$ is hard to formalize because not every metric can be written in such a way.

You can circumvent this by changing your perspective. Start with a function $f$ and then define the metric $d(p,q) := f(|p-q|)$ — I will say that $f$ induces the metric $d$ in this case. Now we see what your lemma really is about, mathematically: You give sufficient conditions for $f$ such that $d$ is a metric. You have to be really precise about what your conditions on $f$ are. For starters, the domain and range should be both $\mathbb R_{\geq 0} := [0, \infty)$ so that your metric is non-negative. Because you work with analytic properties of $f$ like $f''(x) < 0$ you also need differentiability (technicality: $\mathbb R_{\geq 0}$ is a closed set).

Now you have to go through the properties of your metric and carefully check if they are fulfilled. The symmetry is evident by definition, but the definiteness, i.e. $d(p, q) = f(|p-q|) = 0 \Leftrightarrow p = q$, is already not that obvious. For it to hold you have to require $f(0) = 0$ and that $f(x) \neq 0$ for $x > 0$. The latter follows by your requirement that $f$ must be strictly concave but your proof is missing any argument for this ($f \equiv 0$ is a non-decreasing, concave function which doesn't induce a metric).

The triangle inequality is truly the heart of your lemma, so you should try to leave out no steps here. You are right to observe that the subadditivity of $f$, i.e. $f(a+b) \leq f(a) + f(b)$ for all $a, b \in \mathbb R_{\geq 0}$, is crucial. You want to prove $$ d(p, q) \leq d(p, r) + d(r, q) $$ which is equivalent to $$ f(|p-q|) \leq f(|p-r|) + f(|r-q|).$$ Instead of doing a proof by cases for $p, q, r$ you could also use the triangle inequality of $|\cdot|$ and that $f$ is non-decreasing: $$ |p - q| = |p-r+r-q| \leq |p -r| + |r-q| \Rightarrow f(|p-q|) \leq f(|p-r| + |r-q|).$$ (This also works if you replace $|\cdot|$ by any other metric, see the lemma below.)

Now you have to use the subadditivity of $f$ on the last term on the right hand side. Your proof of that contains all the right ingredients, but I don't really understand how you put them together (and why you use averages). For me the property that $f'$ is non-increasing, due to $f'' < 0$, implies the integral inequality for $f'$ and then you can use the fundamental theorem of calculus (note again how you need $f(0) = 0$).

Your claim that your lemma is indeed an equivalence is false. Formally you need to be really careful about what that even means: Is any function which induces a metric in $C^2$ and fulfills your conditions? Or does any $C^2$-function which induces a metric satisfy your conditions? Anyway, your proof assumes that the negation of $f' \geq 0$ is $f' < 0$, but this is false. $f' \geq 0$ is an abbreviation for $\forall x \in \mathbb R_{\geq 0}\colon f'(x) \geq 0$, so the proper negation is $\exists x \in \mathbb R_{\geq 0}\colon f'(x) < 0$. Hence your metric doesn't have to become negative. The same applies to your $f'' < 0$ argument.

---

In the end, let me state another lemma which is a generalization of yours:

Lemma. Let $f\colon \mathbb R_{\geq 0} \to \mathbb R_{\geq 0}$ where $\mathbb R_{\geq 0} := [0, \infty)$. Let $f(x) = 0 \Leftrightarrow x = 0$ and $f$ be concave, i.e. for any pair $x$, $y \in \mathbb R_{\geq 0}$ there holds $$f(\theta x + (1-\theta) y) \geq \theta f(x) + (1-\theta) f(y) \quad \forall \theta \in [0, 1].$$ Then $d_f(p, q) := f(| p - q|)$ is a metric on $\mathbb R$. Or more generally: For any metric space $(X, d_X)$ the function $d_f(x, y) := f(d_X(x, y))$ is another metric on $X$.

The proof for this lemma is similar to yours. You need to show that $f$ is non-decreasing and subadditive. To see that every non-negative, concave function is non-decreasing you can e.g. work with a contradiction argument. If you sketch the situation you see that $f$ must become negative in this case at some point. Formally: If you assume there exist $a < b$ such that $f(a) > f(b)$ you pick $c > b$ and express $b$ as a linear interpolation between $a$ and $c$. Then you can use the concavity of $f$ to obtain an inequality for every $c$. If you take $c$ large enough this will lead to a contradiction.