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$.

I can't tell if the following proof is correct and would appreciate it if people could please take the time to review it.

At each step, I have done my best to explain my reasoning. If there is anything about my understanding that is incorrect and/or lacking, I would be grateful for explanation.

The Proof

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

We want to show that $d(x, z) \le d(x, y) + d(y, z)$; in other words, that the function $d$ satisfies the triangle inequality.

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

We will begin by looking at $|z_1 - x_1|$ and $|z_2 - x_2|$ separately.

  1. The case for $|z_1 - x_1|$ follows.

$|z_1 - x_1| \leq |z_1 - y_1| + |y_1 - x_1|$ (By the triangle inequality for $\mathbb{R}$.)

$\leq \underbrace{\max(|z_1 - y_1|,|z_2 - y_2|)}_\text{This is $d(y, z)$, which is $\ge \ |z_1 - y_1|$} \ + \underbrace{\max(|y_1 - x_1|,|y_2 - x_2|)}_\text{This is $d(x, y)$, which is $\ge \ |y_1 - x_1|$}$

  1. The case for $|z_2 - x_2|$ follows.

$|z_2 - x_2| \leq |z_2 - y_2| + |y_2 - x_2|$ (By the triangle inequality for $\mathbb{R}$.)

$\leq \underbrace{\max(|z_1 - y_1|, |z_2 - y_2|)}_\text{This is $d(y, z)$, which is $\ge \ |z_2 - y_2|$} \ + \underbrace{\max(|y_1 - x_1|, |y_2 - x_2|)}_\text{This is $d(x, y)$, which is $\ge \ |y_2 - x_2|$}$

Now we bring it all together to state the conclusion:

$\therefore d(x, z) = \max(|z_1 - x_1|, |z_2 - x_2|)$

$\leq \underbrace{\max(|y_1 - x_1|, |y_2 - x_2|)}_\text{This is $d(x, y)$} \ + \underbrace{\max(|z_1 - y_1|,|z_2 - y_2|)}_\text{This is $d(y, z)$} = d(x,y) + d(y, z)$

I've spent a tremendous amount of time on trying to understand this problem, so I would greatly appreciate reviews.

Since the kind reviewers are indicating that the proof is correct, I want to write a little note-to-self (and future viewers) that explains what I was misunderstanding.

What Was My Misunderstanding?

What I wasn't seeing was that we needed to show that each term in $d(x, z) = \max(|z_1 - x_1|, |z_2 - x_2|)$ -- $|z_1 - x_1|$ and $|z_2 - x_2|$ -- must be $\le d(x, y) + d(y, z)$. Why? Because if we show that $|z_1 - x_1| \le d(x, y) + d(y, z)$ and $|z_2 - x_2| \le d(x, y) + d(y, z)$, then we have that $d(x, z) = \max(|z_1 - x_1| \le d(x, y) + d(y, z), |z_2 - x_2| \le d(x, y) + d(y, z))$. By the properties of the $\max()$ function, this implies that $d(x, z)$ can at most be $\le d(x, y) + d(y, z)$! So essentially what we've done here is found an upper bound for each of the arguments of the $\max()$ function, $|z_1 - x_1|$ and $|z_2 - x_2|$.

  • 2
    $\begingroup$ Looks very precise to me, and correct. Good job :) $\endgroup$ – 57Jimmy Apr 17 '18 at 14:12
  • 1
    $\begingroup$ Your calculation looks precise and the have done a great job. $\endgroup$ – WKhan Apr 17 '18 at 14:30
  • 1
    $\begingroup$ Thank you all for the review and kind words. $\endgroup$ – The Pointer Apr 17 '18 at 14:30
  • 1
    $\begingroup$ +1 for the self note. $\endgroup$ – user370967 Apr 19 '18 at 9:38

For real $e,f,g,h$ we have $$(i)...\;\quad e+f\leq e+\max (f,h)\leq\max (e,g)+\max (f,h).$$ $$(ii)...\;\quad g+h\leq g+\max (f,h)\leq \max (e,g)+\max (f,h).$$ Therefore $ \max (e+f,g+h)\leq \max (e,g)+\max(f,h).$

With $e=|x_1-y_1|$ and $ f=|y_1-z_1|$ and $ g=|x_2-y_2|$ and $ h=|y_2-z_2|$ we have $|x_1-z_1|\leq e+f$ and $|x_2-z_2|\leq g+h.$ Therefore $$d((x_1,x_2),(z_1,z_2))=\max (|x_1-z_1|,|x_2-z_2|)\leq$$ $$\leq \max (e+f,g+h)\leq$$ $$\leq \max (e,g)+\max (f,h)=$$ $$=d((x_1,x_2),(y_1,y_2))+d((y_1,y_2),(z_1,z_2)).$$


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.