# Why do these inequalities in metric spaces hold?

The other day I stumbled across some inequalities regarding properties of metric spaces. I'm curious to see a proof of why it holds.

Suppose $(X,\rho)$ is any metric space. For a given $\epsilon\gt 0$, I let $N(X,\epsilon)$ denote the least $n$ such that $X=\bigcup\limits_{i=1}^n U_i$ where $U_i$ are sets such that $\operatorname{diam}(U_i)\leq 2\epsilon$. I also denote by $M(X,\epsilon)$ the greatest number of $m$ points $x_i$, $1\leq i\leq m$ such that $\rho(x_i,x_j)\gt\epsilon$ whenever $i\neq j$.

With this notation, what is it that $N(X,\epsilon)\leq M(X,\epsilon)$ and $M(X,\epsilon)\leq N(X,\epsilon/2)$? Thanks.

-

For given $\epsilon$, pick a set of $M(X,\epsilon)$ points at distances greater than $\epsilon$, and form closed balls with radius $\epsilon$ around them. If there is a point in $X$ that belongs to none of these balls, we can add it to the set, contradicting the maximality of $M(X,\epsilon)$. Thus these $M(X,\epsilon)$ sets of diameter $2\epsilon$ cover $X$, and hence $N(X,\epsilon)\le M(X,\epsilon)$.

For the other direction, note that a set with diameter $2\epsilon/2=\epsilon$ can contain at most one point of a set of $M(X,\epsilon)$ points at distances greater than $\epsilon$; thus we need at least $M(X,\epsilon)$ such sets to cover $X$.

-

Let $S$ be a set of the greatest number of points $x_i$, $1 \leq i \leq M(X,\epsilon) =: m$ such that $\rho(x_i, x_j) > \epsilon$ (call this property P).

Define balls centered around $x_i$ with radius $\epsilon$, $B(x_i, \epsilon) = \{ y \in X | \rho(x_i, y) \leq \epsilon \}$

Claim: $\displaystyle X = \bigcup _{1 \leq i \leq m} B(x_i, \epsilon)$

Proof: $\bigcup _{1 \leq i \leq m} B(x_i, \epsilon) \subseteq X$ is obvious.

Consider an arbitrary $x \in X$.

If $\forall i \leq m, \rho (x, x_i) > \epsilon$, then we can add $x$ to $S$ and which will contradict the fact that it is the greatest set with property P. Thus there must exist at least one index $1 \leq j \leq m$ such that $\rho (x, x_j) \leq \epsilon$. But this means $x \in B(x_j,\epsilon)$ and thus $x \in \bigcup _{1 \leq i \leq m} B(x_i, \epsilon)$. Hence $X \subseteq \bigcup _{1 \leq i \leq m} B(x_i, \epsilon)$ and we are done.

Due to the fact that diam$(B(x_i,\epsilon)) \leq 2\epsilon$ and the claim, we have:

$N(X,\epsilon) \leq m$

The idea for the second inequality is to consider the family of sets $T = \{ U_i\}$ for $1 \leq i \leq N(X,\frac{\epsilon}{2})$. Construct an injective map $\phi:S \to T$. $\phi$ maps $x_i$ to a set in the family $T$ that contains $x_i$. Can you complete the argument?

-