# Showing a compact metric space has a countable dense subset

I know that this is separable, but that has not been covered by the text at this point. I believe my proof (below) to be correct, but not very rigorous. Assuming that it actually is correct, could someone please help me make it more formal? (If it's not correct, please help with the proof). Thanks.

Proof: Let $X$ be a compact metric space. Let $B_n = \{B(x,\frac1{n}) : x\in X\}$. be the collection of open balls centered at $x$. Let $\{x\}^{(n)}$ be the set of centers for some particular $n$. Then by compactness of $X$, there are also a finite number of centers for a particular $n$ (corresponding to each open ball).

[This is where I have trouble properly saying what's on my mind:]

Consider $B(x,r_0)$, where $r_0 = \frac{1}{n_0}$. When we decrease the magnitude of $r_0$ to $r_1$, we must still be able to cover $X$. Meaning some open ball(s) must be "formed" where $B(x,r_0)$ was once "covering". So by adding open balls, we also add to our collection of centers. This means at $B(x,r_0)$, there was originally a point $y \in B(x,r_0)$ s.t. $B(y,r') \subset B(x,r_0)$ for some $r'$. That is, $B(x,r_0)$ contained another point of $X$. Thus, by definition, $X$ contains a countable dense subset.

-
Instead of keeping the center constant and changing the radius, when you change the radius, just allow yourself to pick new centers. Since it'll still cover $X$, then every point will still be a distance $r$ away from some point. – Christopher A. Wong Jun 8 '13 at 0:56

First a notational observation: the notation $\{x\}^{(n)}$ is truly horrible. It looks as if you’re performing some operation on the singleton set $\{x\}$ whose sole element is $x$.

Your basic idea is just fine, but you’re making it too complicated; that’s part of why you’re having trouble expressing it clearly. As others have suggested, you don’t need to try to relate the centres of one ‘level’ to those of any other ‘level’. Here’s a relatively efficient version of the idea:

For each $n\in\Bbb Z^+$ let $$\mathscr{U}_n=\left\{B\left(x,\frac1n\right):x\in X\right\}\;;$$ $\mathscr{U}_n$ is an open cover of the compact space $X$, so there is a finite $F_n\subseteq X$ such that $$\left\{B\left(x,\frac1n\right):x\in F_n\right\}$$ covers $X$. Let $D=\bigcup_{n\in\Bbb Z^+}F_n$; $D$ is a countable union of finite sets, so $D$ is countable. To see that $D$ is dense in $X$ let $y\in X$ and $\epsilon>0$ be arbitrary. There is an $n\in\Bbb Z^+$ such that $\frac1n\le\epsilon$, and there is then an $x\in F_n$ such that $y\in B\left(x,\frac1n\right)$. But then $d(x,y)<\frac1n\le\epsilon$, so $y\in D\cap B(x,\epsilon)$, and $D$ is indeed dense in $X$. $\dashv$

You might like to note, by the way, that we could have got the same result had each of the sets $F_n$ been countable: we did not actually need them to be finite. Thus, the same argument shows that every Lindelöf metric space is separable. And this actually is a stronger result, since $\Bbb R$ with its usual metric is Lindelöf but not compact.

-
I'm struggling with why $d(x,y)$ has to be less than $1/n$. If the definition of a dense set just requires that another point of $D$ lie in some open neighbourhood of $x \in X$, couldn't it be possible that $y$ is still in $B(x,\epsilon)$ but that the distance between the two points is not less than $1/n$? – AlanH Jun 9 '13 at 0:54
@Alan: I don’t understand the problem. Every point of $X$ is in some $B\left(x,\frac1n\right)$ with $x\in F_n$, so we pick an $x\in F_n$ such that $y\in B\left(x,\frac1n\right)$. By the very definition of $B\left(x,\frac1n\right)$ we then know that $y\in B\left(x,\frac1n\right)$. And since we chose $n$ big enough so that $\frac1n\le\epsilon$, that further means that $d(x,y)<\epsilon$. Thus, no matter how small an $\epsilon$ we pick, we can always find a point of $D$ within $\epsilon$ of $y$, which is exactly what it means for $D$ to be dense in $X$. – Brian M. Scott Jun 9 '13 at 4:24
I wish I could upvote this answer a million times. – Don Larynx Nov 5 '13 at 13:48
@Don: $F_n$ isn’t a cover of $X$; it’s a subset of $X$ with the property that the family of open $\frac1n$-balls centred at points of $F_n$ is a cover of $X$. – Brian M. Scott Nov 12 '13 at 16:59
@Don: Each $F_n$ is finite: the points of $F_n$ are the centers of the members of a finite subcover of the cover $\mathscr{U}_n$. – Brian M. Scott Nov 12 '13 at 20:51

I think that you can pretty much ignore where exactly are the new balls that replaced the old balls. There is no harm in adding in redundant ball center as long as it is still finite, so you can keep the centre of the big ball and the centre of the small ball.

So I think the 2nd part can be fixed simply by this:

For each $n$ there is a finite set of centre $C_{n}\subset \{x\}^{(n)}$ such that all ball of radius $\frac{1}{n}$ around these centre cover $X$ completely.

Simply produce the set $Z=\bigcup\limits_{i=1}^{\infty} C_{i}$ which is countable.

Given any point $x\in X$, and any $\epsilon>0$ then the ball $B_{\epsilon}(x)$ must intersect $Z$. Why? Because remember that there exist a $C_{n}\subset Z$ where $\frac{1}{n}<\epsilon$ that means that there is a collection of ball radius $\frac{1}{n}$ with centre $C_{n}$ that cover $X$ completely, that means $x$ is not more than $\frac{1}{n}<\epsilon$ from at least 1 point in $C_{n}\subset Z$. Since this apply to all $\epsilon>0$ then $x$ is in the closure of $Z$.

-

Let $\epsilon > 0$. Then, since the space is compact, there are $x_0, x_1, \cdots x_n$ so that that $$X = \bigcup_{k=0}^n B_\epsilon(x_k).$$ Such a set is called an $\epsilon$-net of $X$.

For each positive integer $p$, choose a (finite) $1/p$-net $N_p$ of $X$. Then $\bigcup_p N_p$ is a countable union of finite sets, so it is countable. It is also easy to argue it is dense in $X$.

-