Prove that a compact metric space can be covered by open balls that don't overlap too much.

Question

The problem is: For compact metric space $(X,d)$ prove that for every $r>0$ there exists a subset $S$ of $X$ such that $\{\mbox{Open balls of radius }r\mbox{ centered at }p \mid\mbox{ for all }p \in S\}$ forms a cover for $X$ and for every $p,q \in S$, $d(p,q) > r/2$.

I have an algorithm that would go like this: Form an open cover of $X$ by the set of open balls of radius $r/2$ around all points in $X$. By compactness there exists a finite number of these balls which cover $X$. Then for each point with a ball around it, "delete" the points which are inside of the ball and not the center of the ball. Then you will have a collection of points that are at least $r/2$ distance apart and the set of balls of radius $r$ around these points will cover $X$.

Does this "algorithm" work, and if so how do you denote such a set? I'm having problems figuring out exactly how to "delete" as I've used the word above.

Thanks!

Answer 1

The statement of the problem is not so correct, since we are allowed to choose $p,q \in S$ such that $p=q$, viz. $d(p,q)=0$, so from here later we'll assume $p\neq q$. Let's go back to the problem now: since we assume the contraint $d(p,q)>r/2$ then $S$ is finite, i.e. there exists a integer $n\ge 1$ such that $|S|=n$ and $S:=\{p_1,p_2,\ldots,p_n\}$. It's well known that the propositions:

i) $X$ is totally limited

ii) $X$ is compact

iii) $X$ is sequentially compact

are equivalent (the easiest way to prove it is that (i) implies (ii) implies (iii) implies (i)).

So, there exists a finite collection of open balls $B(x_1,3r/4),B(x_2,3r/4),\ldots,B(x_{k_1},3r/4)$ that covers the whole compact metric space $(X,d)$. We can also assume without loss of generality that $B(x_i,3r/4) \cap X \neq \emptyset$ for all $1\le i\le k_1$.

Define $x_1:=\alpha_1$, and also $X_1:=X\setminus B(x_1,3r/4)$: if $x_1$ is empty then we ended (see below), otherwise $X_1\neq \emptyset$ is a metric space too, bounded, and closed, hence compact too. Then there exist a finite collection of open balls $B(y_1,3r/4),B(y_2,3r/4),\ldots,B(y_{k_2},3r/4)$ that covers $X_1$. Define $y_1:=\alpha_2$.

Repeat this algorithm infinitely many times, we have two cases:

1) If the sequence $\alpha_1,\alpha_2,\ldots$ is finite, then just define $p_i:=\alpha_i$ for all $i$ and we are done, indeed $d(p_i,p_j)\ge 3r/4 > r/2$ for all $1\le i < j \le n$.

2) If the sequence $\alpha_1,\alpha_2,\ldots$ is not finite, then the infinite collection of open balls $B(\alpha_1,3r/4),B(\alpha_2,3r/4),\ldots$ is a cover of $X$. Since $X$ is compact there exists a finite set of pairwise disjoint positive integers $T:=\{t_1,t_2,\ldots,t_n\}$ such that $B(\alpha_{t_1},3r/4),B(\alpha_{t_2},3r/4),\ldots,B(\alpha_{t_n},3r/4)$ is a cover too. Just set $\alpha_{t_i}=p_i$ for all $1\le i\le n$ and we really made our subcover of open balls that "do not overlap too much". []