Spaces with a quasi triangle inequality - MathOverflow

Spaces with a quasi triangle inequality

2011-02-20T23:17:56Z

How do you call a space with a function which is symmetric, non negative, positive definite and which satisfies a quasi-triangle inequality:

$d(x,z) \leq C( d(x,y)+d(y,z) )$

for all $x,y,z$ and some $C > 1$?

That is, it satisfies all the axioms of a metric space except for the triangle inequality, which is replaced by the one above.

Can anyone provide any reference on these spaces?

Thanks.

Answer by ex falso quodlibet for Spaces with a quasi triangle inequality

2011-02-20T23:50:12Z

Your construction is a special case of semimetric spaces with relaxed triangle inequality: http://en.wikipedia.org/wiki/Semimetric_space#Semimetrics. This type of metric is sometimes also called non-Archimedian metric. There is a classical paper of W.A.Wilson "On semi-metric spaces", Amer. J. Math. 53 (1931) 361–373, on the subject. Also, I have seen this type of construction mostly used in fixed-point theory, so this would be an additional keyword to look for.

EDIT: To answer your second question about whether Banach fixed-point theorem would be applicable to semimetric spaces: In general one needs $(X,d)$ to be bounded, otherwise there are counter-examples. Consider $X=\mathbb{N}$, $d(n,m):=\frac{|n-m|}{2^{\min(n,m)}}$ and $f(n):=n+1$. Then $(X,d)$ is $d$-Cauchy complete semimetric space (!), but $f$ has no fixed points, even though it is a contraction w.r.t. $d$ with contraction constant $1/2$. This example is taken from the paper "Nonlinear Contractions on Semimetric Spaces" by J. Jachymski, J. Matkowski, T. Swiatkowski, Journal of Applied Analysis Vol. 1, No. 2 (1995), pp. 125–134, where you can also find the proof of the Banach Fixed-Point Theorem for bounded semimetric spaces and some more related results.

Answer by Mark Sapir for Spaces with a quasi triangle inequality

2011-02-20T23:58:07Z

This is called "C-relaxed triangular inequality". See, for example, this paper by Fagin and Stockmeyer.

Answer by Gideon Schechtman for Spaces with a quasi triangle inequality

2011-02-21T09:12:06Z

Here is a negative answer for your additional remark concerning Banach's fixed point theorem: Consider $d(x,y)=(\int_0^1|x-y|^p)^{1/p},$ $0<p<1$ which satisfies the quasi-triangle inequality. Look at the set of all (measurable real) functions on $[0,1]$ boundaed between 0 and 2 and of integral 1. Look at the Baker transformation on this set: first map $x$ to $y(t)=2x(2t)$, $0\le t\le 1/2$ then trancate at hight 2 and shift what remains ($(y-1)^{+}$) by $1/2$ to the right and $2$ down. I think I checked that it is a contraction (with constant $2^{p-1}$). This map is known not to have a fixed point, see the following paper of Dale Alspach: http://www.claremontmckenna.edu/math/moneill/Math%20138/papers138/Alspach.pdf