Sequences that have no Cauchy subsequences

 In the last post we were looking at sequences which have no Cauchy subsequences. 

Setting and terminology

Throughout this post we work in some metric space \((X,d)\). 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\).

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 \varepsilon\,.\)

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 \varepsilon\,.\)

Here we see that 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.

My "conjecture" was the following. 

[The quotes are because it must be very well known, and I should probably just be looking in a suitable textbook. But it is fun to work it out anyway!]

"Conjecture"

Let \((x_n)\) be a sequence in \(X\). Then the following statements are equivalent.
(a) \((x_n)\) has a Cauchy subsequence.
(b) \((x_n)\) has a subsequence \((y_n)\) such that \((y_n)\) has no uniformly separated subsequence.

This is surely all well-known, and we'll come back to it shortly.

Let's first note some easy facts.

(1) No Cauchy sequence is uniformly separated.

(2) Every subsequence of a Cauchy sequence is Cauchy.

(3) Let \((x_n)\) be a Cauchy sequence. Then no subsequence of \((x_n)\) is uniformly separated.

How about some sort of converse for (3)?

Let \((x_n)\) be a sequence in \(X\) and suppose that no subsequence of \((x_n)\) is uniformly separated. Must \((x_n)\) be Cauchy? Must \((x_n)\) at least have a Cauchy subsequence?

Well, we can easily find examples where \((x_n)\) itself is not Cauchy. For example, \(x_n = (-1)^n\) in \(\R\) is not Cauchy, but has no uniformly separated subsequence. But we can prove that it is true that if no subsequence of\((x_n)\) is uniformly separated, then \((x_n)\) must have a Cauchy subsequence. 

Let's see why we "know" this is true via total boundedness. Set 

\(\qquad A=\{x_n: n \in \N\}\,.\)

Then our sequence \((x_n)\) is a sequence in \(A\) and \((x_n)\) has no uniformly separated subsequence. But it follows that there is no uniformly separated sequence at all in the set \(A\), because any such sequence would give us a uniformly separated subset of \(A\), and this then allows us to construct a uniformly separated subsequence of \(x_n\). 

[There are various alternative arguments here, but note that, for several reasons, a sequence in \(A\) need not itself be a subsequence of \((x_n)\).]

It follows that \(A\) must be totally bounded (see the previous post). But then (see the previous post) every sequence in \(A\) has a Cauchy subsequence, and so, in particular, \((x_n)\) has a Cauchy subsequence. Our conclusion is (as noted on https://math.stackexchange.com/questions/9964/if-no-cauchy-subsequence-exists-must-a-uniformly-separated-subsequence-exist ) the following:

(4) Let \((x_n)\) be a sequence in \(X\)  such that no subsequence of \((x_n)\) is uniformly separated. Then \((x_n)\) has a Cauchy subsequence.

We also have (using the contrapositive):

(4') Let \((x_n)\) be a sequence in \(X\) which has no Cauchy subsequence. Then \((x_n)\) has a uniformly separated subsequence.

This is all very well, but for this argument we only needed those last few implications (concerning total boundedness) for the special case of a countable set \(A\). So is that case easier to prove than the general one? We'll come back to that in my next post! But for now we can at least see that my "conjecture" is correct.

Recall the statement of my "Conjecture":

"Conjecture"

Let \((x_n)\) be a sequence in \(X\). Then the following statements are equivalent.
(a) \((x_n)\) has a Cauchy subsequence.
(b) \((x_n)\) has a subsequence \((y_n)\) such that \((y_n)\) has no uniformly separated subsequence.

Proof of "Conjecture"

First suppose that (a) holds, so that \((x_n)\) has a Cauchy subsequence \((y_n)\). Then, by (3), (y_n) has no uniformly separated subsequence. So (b) holds.

Next, suppose that (b) holds. Then we have a subsequence \((y_n)\) of \((x_n)\) such that \((y_n)\) has no uniformly separated subsequence. Then, by (4), \((y_n)\) has a Cauchy subsequence, and this is also a Cauchy subsequence of \((x_n)\). 

So we have a theorem.

Theorem

Let \((x_n)\) be a sequence in \(X\). Then the following statements are equivalent.
(a) \((x_n)\) has a Cauchy subsequence.
(b) \((x_n)\) has a subsequence \((y_n)\) such that \((y_n)\) has no uniformly separated subsequence.

Similarly, taking negations, the following statements are equivalent.

\((\textrm{a}')\) \((x_n)\) has no Cauchy subsequence.

\((\textrm{b}')\) every subsequence of \((x_n)\) has a uniformly separated subsequence.

It now looks as if understanding the totally bounded story properly for countable sets allows us to prove the general results. So in my next post I am going to look at the special case of  countable sets.