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!
Best Answer
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". []