Proving Triangle Inequality for Metric Space with Modified Distance Function

  • Thread starter Thread starter insynC
  • Start date Start date
  • Tags Tags
    Metric
insynC
Messages
66
Reaction score
0

Homework Statement



Let X be a metric space with metric d. Show that the space X, where distance is measured by d' = d/(1+d), is also a metric space.

Homework Equations



Three requirements of a distance function for X to be a metric space:
1. d(x,y) = 0 <=> x=y
2. d(y,x) = d(x,y)
3. d(x,z) <= d(x,y) + d(y,z)

The Attempt at a Solution



It's demonstrating the triangle inequality (3. above) that has me stumped.

My starting point is to try and use (1) d(x,z) <= d(x,y) + d(y,z) to demonstrate (2) d'(x,z) <= d'(x,y) + d'(y,z).

I tried manipulating the RHS of (2) to get a common denominator and then tried to 'bash' it out, without any success. I then tried to manipulate the inequalities, but I can't get (2) whilst maintaining <= as opposed to simply <.

The problem wasn't set as a difficult one, so I presume there is something simple that I can't seem to see.

Any help would be greatly appreciated!

Cheers
 
Physics news on Phys.org
Hmmm your first approach should work (I remember it worked for me). Define f(t) = \frac{1}{1+t}. You basically need to show f(a) + f(b) \geq f(c) given a + b \geq c \geq 0. Multiplying out the first inequality gives
a + ac + ab + abc + b + ba + bc + abc \geq c + ca + cb + abc,
and yeah this should be true unless I made a mistake somewhere.
 
Thanks for the help, I think that sorts it.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top