Yuhang's Blog

Distributivity of the min and max operators over each other

2024-11-04 Mathematics

On $\mathbb R$, we have the usual $\min$ and $\max$ operators. They are distributive over each other. In other words,
$$
\displaylines{
\max(x,\min(y,z))=\min(\max(x,y),\max(x,z)), \\
\min(x,\max(y,z))=\max(\min(x,y),\min(x,z)).
}
$$
This result is proven here. However, I don’t like the idea of having to list all the cases. Here is an alternative way to prove it.

We first give two lemmas.

Lemma 1. For any $a, b \in \mathbb R$, we have $\min (a, b) \le a$.

This is obvious.

Lemma 2. For a fixed $x \in \mathbb R$, the functions $f(t) = \min(x, t)$ and $g(t) = \max(x, t)$ on $\mathbb R$ are non-decreasing. In other words, $\min(x, -)$ and $\max(x, -)$ preserves the $\le$ relation.

This is obtained by breaking the cases of $\min$ and $\max$ and drawing the function graphs.

Now we can prove the main proposition: $\max(x,\min(y,z))=\min(\max(x,y),\max(x,z))$.

First notice that $y$ and $z$ are symmetric, so without loss of generality, we may assume $y \le z$. Then $\min(y, z) = y$ and $\text{LHS} = \max(x, y)$.

By Lemma 1, $\text{RHS} \le \max(x, y) = \text{LHS}$.

By Lemma 2, $\max(x, z) \ge \max(x, y)$. Then $\text{RHS} \ge \min( \max(x, y), \max(x, y)) = \max(x, y) = \text{LHS}$ by using Lemma 2 again.

Thus $\text{LHS} = \text{RHS}$. QED.

The other proposition $\min(x,\max(y,z))=\max(\min(x,y),\min(x,z))$ can be proved in a similar fashion.

In fact, this is a special case of the following general statement:

Every totally ordered set is a distributive lattice with max as join and min as meet.

The above proof can be easily adapted for this general statement.

This article was last updated on days ago, and the information described in the article may have changed.