Prove $|\max_{v}{f(v)} - \max_{v}{g(v)}| \leq \max_{v}{|f(v) - g(v)|}$

Question

In proving that the Bellman operator is a contraction, I need to use this theorem. This seems obviously true, and I have a proof that I think is almost but not quite there:

$$ \max_{v}{f(v)} - \max_{v}{g(v)} \\ = {f(v')} - \max_{v}{g(v)} \\ \leq f(v') - g(v') \\ \leq |f(v') - g(v')| \\ \leq \max_{v}{| f(v) - g(v) |} $$

If I just try replacing $\max_{v}{f(v)} - \max_{v}{g(v)}$ with $|\max_{v}{f(v)} - \max_{v}{g(v)}|$ in the first line though, it doesn't quite work because it seems like $|{f(v')} - \max_{v}{g(v)}| \leq |f(v') - g(v')|$ (where $v'$ is the $v$ that maximises $f$) isn't true. Any help with approach, or a simpler proof? Thanks!

Answer 1

What you have so far is that $\max_v f(v) - \max_v g(v) \leq \max_v|f(v) - g(v)|$. You now need to show that $-\left(\max_v f(v) - \max_v g(v)\right) \leq \max_v|f(v) - g(v)|$ or equivalently, $\max_v f(v) - \max_v g(v) \geq \max_v|f(v) - g(v)|$, which is done exactly as you just did above.

$$\max_v f(v) - \max_v g(x) \\ = \max_v f(v) - g(v') \\ \geq f(v') - g(v') \\ \geq -|f(v') - g(v')|\\ \geq -\max_v |f(v) - g(v)|,$$

which is that which was desired.

If the maximum does not exist in which case the maximum is replaced with a supremum (you can ignore this if the maximum exists):

I do not know if the maximum always exists, but you can use the case when the maximum exists as a lemma by approximating $g$ and $f$ by functions whose maximum exists and are gotten by cutting $f$ and $g$. That is, $f_n(v) = f(v)$ if $f(v) < \sup f - \frac{1}{n}$ and else equals $\sup f - \frac{1}{n}$. Define $g_n$ likewise. So, we have a sequence of function $f_n$ and $g_n$ that attain their maximum, $f_n \to f$, $g_n \to g$ as $n\to \infty$, and $0 \leq f - f_n, g-g_n \leq \frac{1}{n}$.

So, we get that $$|\sup f - \sup g| \\ = |\sup \lim_{n\to\infty}f_n - \sup \lim_{n\to\infty} g_n| \\ = | \lim_{n\to\infty} \sup f_n - \lim_{n\to\infty} \sup g_n| \\ = \lim_{n\to\infty} | \sup f_n - \sup g_n| \\ = \lim_{n\to\infty} |\max f_n - \max g_n|\\ \leq \lim_{n\to\infty} \max|f_n - g_n| \\ \leq \lim_{n\to\infty} \sup \left(|f_n - f| + |f - g| + |g_n - g|\right) \\ \leq \lim_{n\to\infty} \sup \left(|f - g| + 2/n\right) \\ = \lim_{n\to\infty} \left(\sup |f - g| + 2/n\right) \\ = \sup |f-g|.$$

Answer 2

Let $\max_vf(x)=f(x_1)$ and $\max_vg(x)=g(x_2).$

(1)If $f(x_1)\geq g(x_2)$ then $f(x_1)\geq g(x_2)\geq g(x_1)$ so $$\max_v|f(x)-g(x)|\geq |f(x_1)-g(x_1)|=f(x_1)-g(x_1)=[f(x_1)-g(x_2)]+[g(x_2)-g(x_1)]\geq$$ $$\geq f(x_1)-g(x_2)=|f(x_1)-g(x_2)|.$$

(2)If $g(x_2)\geq f(x_1)$ then $g(x_2)\geq f(x_1)\geq f(x_2)$ so $$\max_v|f(x)-g(x)|\geq |g(x_2)-f(x_2)|=g(x_2)-f(x_2)=[g(x_2)-f(x_1)]+[f(x_1)-f(x_2)]\geq$$ $$\geq g(x_2)-f(x_1)=|g(x_2)-f(x_1)|.$$