0
$\begingroup$

Let $X = \mathbb{R}^2$ and define a function $d : \mathbb{R}^2 \times \mathbb{R}^2 \to \mathbb{R}$ by $d((x_1, x_2), (y_1, y_2)) = max( |y_1 - x_1|, |y_2 - x_2|)$, where $max(a, b)$ is the maximum of $a$ and $b$.

My Proof

Let $x = (x_1, x_2)$, $y = (y_1, y_2)$, and $z = (z_1, z_2)$.

$d(x, z) = max(|z_1 - x_1|, |z_2 - x_2|)$ (By the definition of $d$.)

$\le max(|z_1 - y_1| + |y_1 - x_1|, | z_2 - y_2 | + | y_2 - x_2 | )$ (Triangle inequality for $\mathbb{R}$.)

$\le max(|z_1 - y_1|, |z_2 - y_2|) + max(|y_1 - x_1| , |y_2 - x_2|)$ (Since, for any $a, b, c, d \ge 0, max(a, c) + max(b, d) ≥ max(a+b, c+d)$.)

$= d(y, z) + d(x, y) \ \ \ Q.E.D.$

I would greatly appreciate it if people could please review my proof for correctness and respond to the question embedded in my proof.

EDIT:

All I'm looking for is a review of my proof for correctness. If it isn't correct, then please specify why and what the correct proof is and/or how it can be made correct.

$\endgroup$
0
1
$\begingroup$

You can break it up into smaller pieces to make it clearer:

Assume (without loss of generality) that

$|z_1 - y_1|+|y_1-x_1| \geq |z_2-y_2|+|y_2-x_2|$.

Then

$max(|z_1 - y_1|+|y_1-x_1|, |z_2-y_2|+|y_2-x_2|) \leq |z_1 - y_1|+|y_1-x_1| \leq max(|z_1 - y_1|,|y_1-x_1|) + |y_1-x_1| \leq max(|z_1 - y_1|,|y_1-x_1|) + max(|z_2 - y_2|,|y_2-x_2|)$

edit: the last step was unjustified as pointed out by ndn.

A different approach:

$|x_1-z_1| \leq |x_1-y_1|+|y_1-z_1| \leq max(|x_1-y_1|,|x_2-y_2|) + max(|y_1-z_1|,|y_2-z_2|).$

Similarly,

$|x_2-z_2| \leq |x_2-y_2|+|y_2-z_2| \leq max(|x_1-y_1|,|x_2-y_2|) + max(|y_1-z_1|,|y_2-z_2|).$

Therefore $max(|x_1-z_1|, |x_2-z_2|) \leq max(|x_1-y_1|,|x_2-y_2|) + max(|y_1-z_1|,|y_2-z_2|).$

$\endgroup$
5
  • $\begingroup$ How do you know that |y1−x1|≤max(|z2−y2|,|y2−x2|)? $\endgroup$ – Sally G Apr 15 '18 at 16:16
  • 1
    $\begingroup$ You're right, that was a mistake. I think I've fixed it now. $\endgroup$ – Lukas Kofler Apr 15 '18 at 16:35
  • $\begingroup$ Can you please explain why we are assuming that $|z_1 - y_1|+|y_1-x_1| \geq |z_2-y_2|+|y_2-x_2|$? $\endgroup$ – The Pointer Apr 15 '18 at 17:23
  • $\begingroup$ And is there something incorrect about my proof? Or is it correct but can be broken-down? $\endgroup$ – The Pointer Apr 15 '18 at 17:32
  • $\begingroup$ My proof basically expands on yours. Where you write $d(x, z) = max(|z_1-x_1|, |z_2-x_2|)$ I looked at $|z_1-x_1|$ and $|z_2-x_2|$ separately and concluded both are less or equal than $max(|x_1-y_1|,|x_2-y_2|) + max(|y_1-z_1|,|y_2-z_2|)$. Therefore the maximum of the two, equal to $d(x, z)$, must satisfy the inequality too. $\endgroup$ – Lukas Kofler Apr 16 '18 at 9:49

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.