Total boundedness for countable metric spaces

 Following up on my previous posts about total boundedness and Cauchy sequences, let's look at the special case of countable metric spaces, and see whether any of the proofs become simpler.

Along the way we can put together some of the results and arguments from earlier posts about sequences and their subsequences.

Of course, finite metric spaces are not very interesting. They are all discrete, compact, sequentially compact, totally bounded and complete. Indeed, every sequence in such a metric space has a constant subsequence. So we will look only at countably infinite metric spaces. 

Setting and terminology

Throughout this post we work in some countably infinite metric space \((X,d)\), which we enumerate as

\(\qquad X=\{a_1,a_2,a_3,\dots\}\)

with all the \(a_n\) being distinct.

[This fits with what I think is meant by an enumeration of a set. Not all authors agree: some authors might allow an enumeration to include repeats. Still, it looks like my version agrees with the "default" version described on https://en.wikipedia.org/wiki/Enumeration]

As before, where we discuss sequences, we mean infinite sequences, and by default our indices will be the positive integers. So (for example), by default, \((x_n)\) will denote a sequence \((x_n)_{n=1}^\infty\).

We recall our terminology concerning uniformly separated sequences and uniformly separated sets.

Definition

Let \((x_n)\) be a sequence in \(X\). Then \((x_n)\) is uniformly separated if there exists \(\varepsilon>0\) such that for all \(m,n \in \N\) with \(m\neq n\), we have

\(\qquad d(x_m,x_n)\geq ε\,.\)

Let us also say in this case that  \((x_n)\) is \(\varepsilon\)-uniformly separated.

More generally, let \(Y\) be a subset of  \(X\). Then we say that \(Y\) is uniformly separated if there exists \(\varepsilon>0\) such that for all \(y,y' \in Y\) with \(y\neq y'\), we have

\(\qquad d(y,y')\geq ε\,.\)

Again, we can then say that the set \(Y\) is \(\varepsilon\)-uniformly separated.

We note some easy facts

• As we noted last time, a sequence \((x_n)\) in \(X\) is uniformly separated if and only if all the terms in the sequence are distinct and the set \(\{x_n:n \in \N\}\) is uniformly separated.
• Of course, every finite subset of a metric space is uniformly separated, so we are mainly interested in infinite uniformly separated subsets. 
• In our special setting we see easily that \(X\) has an infinite, uniformly separated subset if and only if  our enumerating sequence \((a_n)\) has a uniformly separated subsequence.
• We also see that \(X\) is totally bounded if and only if, for all \(\varepsilon>0\), there exists \(N \in \N\) such that
  \(\displaystyle\qquad X=\bigcup_{k=1}^N B(a_n,\varepsilon)\,.\)

This makes it easy to prove the following easy lemma

Easy Lemma 1

Suppose that \(X\) is not totally bounded. Then \((a_n)\) has a uniformly separated subsequence.

Proof

We could use the usual proof valid for all metric spaces to show that there is a  uniformly separated sequence \((x_n)\) in \(X\). As noted in a previous post, \((x_n)\) might not itself be uniformly separated. But it does give us an infinite uniformly separated subset of \(X\), and that in turn gives us a uniformly separated subsequence of \((a_n)\).

Here, instead, is a quick direct proof.

Since \(X\) is not totally bounded, there exists \(\varepsilon>0\) with the property that, for all \(N \in \mathbb{N}\), 

\(\qquad \displaystyle\bigcup_{k=1}^N B(a_n,\varepsilon) \neq X\,.\)

We can now obtain a uniformly separated subsequence of \((a_n)\) (without using the axiom of choice at all) by specifying a suitable strictly increasing sequence of indices \((n_k)_{k=1}^\infty\) as follows.

Set \(n_1=1\).

We know that \(B(a_1,\varepsilon) \neq X\). Let \(n_2\) be the smallest positive integer \(n\) such that \(a_n \notin B(a_1,\varepsilon)\). Certainly \(n_2>1=n_1\).

[Or, if we were worried about it, we could include that in our choice of \(n_2\).]

More generally, for \(m \in \N\), having chosen positive integers \(n_1,n_2,\dots n_m\), we note that 

\(\qquad \displaystyle\bigcup_{k=1}^{n_m} B(a_k,\varepsilon) \neq X\,.\)

We take \(n_{m+1}\) to be the smallest positive integer \(n\) such that

\(\qquad \displaystyle a_n \notin \bigcup_{k=1}^{n_m} B(a_k,\varepsilon)\,.\)

Clearly \(n_{m+1}>n_m\).

The inductive choice may proceed, and gives us an \(\varepsilon\)-uniformly separated subsequence \((a_{n_k})_{k=1}^\infty\) of \((a_n)\). \(\qquad \square\)

Perhaps it might be even cleaner to put the obvious well-ordering on \(X\) (using the enumeration \((a_n)\)), in which case our next term in the subsequence, \(a_{n_{m+1}}\), is simply the first element of \(X\) that isn't in the union of the \(\varepsilon\)-balls so far.

The converse of our Easy Lemma 1 is also easy. Indeed, suppose that \(\varepsilon>0\) and the subsequence \((a_{n_k})_{k=1}^\infty\) is \(\varepsilon\)-uniformly separated. Then no finite number of open \(\varepsilon/2\) balls can be equal to \(X\), as each such ball can include at most one of the \((a_{n_k})\).

Of course, we should probably have already observed that a general metric space \(Z\) is totally bounded if and only if \(Z\) has no infinite uniformly separated subset, as this is also equivalent to \(Z\) having no uniformly separated sequence. But let's stick to our special setting for now.

Now suppose that \(X\) is totally bounded. We would like to show that every sequence in \(X\) has a Cauchy subsequence, but if possible simplifying the usual proof in our special setting.

Let \((x_n)\) be a sequence in \(X\), and set \(A=\{x_n:n\in\N\}\).

If \(A\) is finite, then \(x_n\) has a constant subsequence, so that case is uninteresting.

Even if \(A\) is infinite, the sequence \((x_n)\) might not be a subsequence of \((a_n)\). But in this case, certainly some subsequence of  \((x_n)\) will be a subsequence of \((a_n)\).

As a result, we just need to show that every subsequence of \((a_n)\) has a Cauchy subsequence. But I'm not sure whether this makes things any easier!

Perhaps it is best to use the usual proof, but without any need for the the axiom of choice again.

Of course, we can bootstrap the result a bit: we only really need to prove that \((a_n)\) itself has a Cauchy subsequence here, as we can then apply that result to the subsequence.

But, apart from using the well order we get from \(\mathbb{N}\) to make the choice constructive, it doesn't look as if things get much quicker.

Conclusions in the next post!