Prove that $d(a,b) \le \inf ~\{ ~d(a,s)~|~s \in S \} + \inf ~\{ ~d(b,s)~|~s \in S \} + \sup ~\{~d(b,s)~|~s \in S\}$. Error in proof?

Question

Suppose $(X,d)$ is a metric space and $a,b \in X, S \subseteq X, S \ne \{\phi\}$.

Then, prove that $d(a,b) \le \inf ~\{ ~d(a,s)~|~s \in S \} + \inf ~\{ ~d(b,s)~|~s \in S \} + \sup ~\{~d(s_1,s_2)~|~s_1,s_2 \in S\}$

My Textbook ( Metric Spaces by Michael Searcoid) gives the following proof :

By definition of metric spaces :

$d(a,b) \le d(a,s_1) + d(s_1,s_2) + d(b,s_2)$ where $s_1,s_2 \in S$

$~~~~~~~~~~~\le d(a,s_1) + d(b,s_2) + \sup ~\{~d(s_1,s_2)~|~s_1,s_2 \in S\}~\forall s_1,.s_2 \in S$

$~~~~~~~~~~~$ where $\sup ~\{~d(s_1,s_2)~|~s_1,s_2 \in S\} = k$ is a constant.

$~~~~~~~~~~~\le \inf \{ d(a,s_1) + d(b,s_2)\} + k~~~;s_1,s_2 \in S$

$~~~~~~~~\le \inf \{ d(a,s)~|~s \in S \} + \inf \{d(b, s)~|~s \in S\} + k$

I think there is an error in the last step because $\inf$ has been distributed. In general $\inf f + \inf g \le \inf ( f + g) $ where $f,g$ are two random functions. Also, see this answer where distribution of the infimum has been cited as false: https://math.stackexchange.com/a/2852545/66069

Could anyone please clarify. Thanks a lot.

Answer 1

Separating the $s_1$ and $s_2$ dependent terms, \begin{align*} \require{color} &\inf\{d(a,s_1)+d(b,s_2)\mid s_1,s_2\in S\}\\ &=\inf\{\inf\{d(a,s_1){\color{red}{+d(b,s_2)}}\mid s_1\in S\}\mid s_2\in S\}\\ &=\inf\{{\color{blue}\inf\{d(a,s_1)\mid s_1\in S\}}{\color{red}{+d(b,s_2)}}\mid s_2\in S\}\\ &={\color{blue}{\inf\{d(a,s_1)\mid s_1\in S\}+}}\inf\{d(b,s_2)\mid s_2\in S\}\\ &=\inf\{d(a,s)\mid s\in S\}+\inf\{d(b,s)\mid s\in S\}. \end{align*} The red and blue terms are independent of the immediate variable in inf, so can be pulled outside as shown.

But there is indeed a mistake in the proof you wrote: $$ d(a,s_1)+d(b,s_2)+k $$ is not $\leq\inf\{d(a,s_1)+d(b,s_2)\mid s_1,s_2\in S\}+k$. One correct way is to give yourself some room first (another way is given by DanielWainfleet in the comments). For $\varepsilon>0$, pick $s_1,s_2\in S$ so that $$ d(a,s_1)+d(b,s_2)\leq\inf\{d(a,s_1)+d(b,s_2)\mid s_1,s_2\in S\}+\varepsilon $$ and hence \begin{align*} d(a,b)&\leq d(a,s_1)+d(b,s_2)+d(s_1,s_2)\\ &\leq\inf\{d(a,s_1)+d(b,s_2)\mid s_1,s_2\in S\}+\varepsilon+k\\ &=\inf\{d(a,s)\mid s\in S\}+\inf\{d(b,s)\mid s\in S\}+k+\varepsilon \end{align*} Now $\varepsilon>0$ is arbitrary, so $$ d(a,b)\leq\inf\{d(a,s)\mid s\in S\}+\inf\{d(b,s)\mid s\in S\}+k. $$

Answer 2

You are correct, that is an error, for the reasons you cited.

I think the first error has happened one step before, when they say

$$d(a,s_1) + d(b,s_2) \le \inf \{ d(a,s_1) + d(b,s_2)\}$$

which is of course wrong generally. It would work with supremum, but not infimum.

If you are interested in the proof, it could go like this, using your $k$, we start with the last correct line:

$$d(a,b) \le d(a,s_1) + d(b,s_2) + k, \quad\forall s_1,s_2\in S.$$

Now choose a sequence $s_{1n}\in S, n\ge 1$ such that $\lim_{n\to\infty} d(a,s_{1n})=\inf\{d(a,s_1),s_1\in S\}$. That's more or less the definition of the infimum. That means we have

$$d(a,b) \le d(a,s_{1n}) + d(b,s_2) + k, \quad\forall s_2\in S, s_{1n} \text { as defined above},$$

which we can rewrite as

$$d(a,b) - d(b,s_2) -k \le d(a,s_{1n}), \quad\forall s_2\in S, s_{1n} \text { as defined above}.$$

Now if we fix $s_2$ the above inequality has a constant on the left side. If we take the limit $n\to \infty$ on both sides, we get

$$d(a,b) - d(b,s_2) - k \le \inf\{d(a,s_1),s_1\in S\}, \quad\forall s_2\in S,$$

which we rewrite again as

$$d(a,b) \le \inf\{d(a,s_1),s_1\in S\} + d(b,s_2) + k, \quad\forall s_2\in S.$$

If we do the same procedure with a sequences $s_{2n}\in S, n\ge 1$ such that $\lim_{n\to\infty} d(b,s_{2n})=\inf\{d(b,s_2),s_2\in S\}$, we finally get the desired outcome:

$$d(a,b) \le \inf\{d(a,s_1),s_1\in S\} + \inf\{d(b,s_2),s_2\in S\} + k.$$

Because we had the freedom to choose our $s_1$ and $s_2$ as we wanted, we could bring in the infimum in 2 cases.

Answer 3

Let $ A=\inf \{d(a,s):s\in S\} $ and $ B=\inf \{d(b,s):s\in S\} $ and $ k=\sup \{d(s,s'):s,s'\in S\}.$

By contradiction, suppose $ d(a,b)=A+k+B+r \;$ with $r>0.$

Take $s_1\in S$ with $d(a,s_1)<A+r/2.$ Take $s_2\in S$ with $d(b,s_2)<B+r/2 .$ Then $$A+k+B+r=d(a,b)\le $$ $$\le d(a,s_1)+d(s_1,s_2)+d(s_2,b)\le$$ $$\le d(a,s_1)+k+d(s_2,b)<$$ $$<(A+r/2)+k+(B+r/2)=A+k+B+r$$ implying $A+k+B+r<A+k+B+r.$