Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.