Tricki

## Convergent subsequences and diagonalization

### Quick description

A topological space is sequentially compact if every sequence has a convergent subsequence. One form of the Bolzano-Weierstrass theorem states that a closed bounded subset of is sequentially compact. More generally, compact metric spaces are sequentially compact. These facts have many applications. Also, some useful diagonalization techniques can be interpreted as saying that certain topological spaces are sequentially compact – as a result, one often hears the phrase "by compactness" when no topology has been specifically mentioned.

A common application of compactness is to use the compactness and contradiction method to derive finitary quantitative results from infinitary qualitative ones.

### Prerequisites

Basic notions of real analysis up to and including the definition of compactness.

### Related article

The article on how to use the Bolzano-Weierstrass theorem contains further examples of the use of convergent subsequences.

### Example 1

Let us define a binary word to be a finite sequence of s and s. Given two words and say that is an initial segment of if has length , has length , and the first terms in the sequence give you For example, is an initial segment of

Suppose now that you are given an infinite set of words. Is it always possible to find an infinite sequence of s and s such that every initial segment of that infinite sequence is an initial segment of a word in ? The answer is yes, and the proof is typical of a certain kind of compactness/diagonalization argument.

To prove it, we argue as follows. In our set there must either be infinitely many words that start with a or infinitely many words that start with a If there are infinitely many words that start with a then there must be infinitely many words that start or else infinitely many words that start Similarly, if there are infinitely many words that start with a then there must be infinitely many words that start or infinitely many words that start We can continue in this way, building up inductively a -sequence such that for every there are infinitely many words in that begin This sequence has the desired property.

### General discussion

If you are familiar with the proof of the Bolzano-Weierstrass theorem, then you will recognise that the above argument is essentially the same.

### Example 2

Let be an infinite tree such that every vertex has finite degree. Let be a vertex of Must there be an infinite path that starts at ?

Again, the answer is yes, and this is a fact known as König's lemma. The proof is very similar to the proof in the first example. Let us write Then we can partition the other vertices of according to which neighbour of you have to go through to get to them. So there must be a neighbour of such that is connected to infinitely many vertices of via a path that has to go through Let be the set of vertices that can be reached from only by going through Then we can find such that there are infinitely many vertices in that can be reached from only by going through and so on. This gives us an inductive construction of an infinite path in

### General discussion

This second example is a generalization of the first, which can be reinterpreted as a statement about binary trees. (To form a tree out of take an infinite binary tree and label its vertices as finite -sequences in the obvious way. Then take all vertices that correspond to initial segments of words in )

### Example 3

Here is a typical argument that would often be summed up by experts with the phrase "by compactness". One way of stating Van der Waerden's theorem is to say that for any two positive integers and if you colour the positive integers with colours then there will always be an arithmetic progression of length consisting of numbers of just one colour. (Such a progression is called monochromatic.) Another way of stating the theorem is "more finite": for every and every there exists such that if you colour the integers with colours then there will always be a monochromatic arithmetic progression of length

It is easy to see that the second formulation implies the first. But what is interesting is that the first implies the second – by compactness. What does this mean? To answer this question, let us first see the proof and then what it has to do with compactness.

First proof. Suppose that the second formulation is false. Then for every we can colour the integers from to with colours in such a way that there is no monochromatic arithmetic progression of length Let us be slightly formal, and call this colouring regarding as a function from to Thus, is our set of "colours" and assigns colours to the integers from to

We now want to put together the colourings to create a new colouring defined on the whole of in such a way that there is no monochromatic arithmetic progression of length This will contradict the first statement of van der Waerden's theorem and thereby give us the (contrapositive of the) deduction we wanted.

To do this, we first find infinitely many such that is the same. We set to be the set of all these and we define to be the value taken by whenever

Next, we find an infinite subset such that is the same for every and call the common value And we continue like this to define our colouring

We must check that there is no monochromatic arithmetic progression of length But suppose that is an arithmetic progression of length and that for every Let be the maximum element of Then for every and every our construction above gives us that Therefore, there must be some such that for every which contradicts our choice of as a colouring with no monochromatic progressions of length

Second proof. While we are at it, it is worth seeing that the deduction is also a consequence of König's lemma. Indeed, the finite colourings of can be regarded as vertices of a tree, where the neighbours of a colouring of are all colourings of that agree with up to as well as the restriction of to Now form a subtree by taking the colourings from the previous proof, as well as all their restrictions (which also do not contain any monochromatic arithmetic progressions. Then find an infinite path of such colourings, which naturally defines a colouring of with no monochromatic arithmetic progression of length

### General discussion

#### Relationship with compactness

So where does compactness come into it? Well, a colouring can be thought of as an element of the infinite product and by Tychonoff's theorem this product is compact in the product topology. Recall that a basic open neighbourhood of a function will be a set of the form for some That is two colourings are thought of as "close" if they agree on the first integers for some large In fact, it is not just compact but sequentially compact, which is essentially what we were showing in the first proof above. We say "essentially" here because that proof constructs a limit colouring from a collection of colourings of finite sets, but we could if we wanted have defined in some arbitrary way for integers greater than (e.g. by defining to be 1 whenever ) and the proof would have been the same.

Why do we call this a compactness argument rather than a sequential-compactness argument? Simply because the product topology on is metrizable (this is a nice exercise) and compactness and sequential compactness are equivalent for metric spaces.

#### Relationship with ultrafilters

Arguments such as the ones we have just seen can often be proved with the help of ultrafilters. See the article on how to use ultrafilters for the necessary background to this remark. In the proof above, we could instead have defined a colouring as follows. Let be a non-principal ultrafilter. Then for each there is a unique such that belongs to We define to be this Then if for every in some finite arithmetic progression the set of such that for every belongs to and is therefore non-empty, which gives us the contradiction we had above in a slicker way.

Essentially what the ultrafilter does here is decide for us how to define when we have a choice. (However, note that although the other proof appeared to use the axiom of countable choice, it was in fact easy to make the infinitely many choices needed in an explicit way, such as choosing the smallest possible at each stage and making each as large as possible.) It tends to be easy to translate back and forth between ultrafilter arguments of this basic kind and diagonalization arguments. (However, it becomes less routine when one uses ultrafilters with special properties such as being idempotent.)

#### Lack of quantitative bounds

An interesting feature of compactness arguments is that they give no information about bounds. The next two examples give two rather dramatic illustrations of this. The first is an easy compactness argument that proves that a certain function exists, but the function is known to grow so fast that it cannot be proved to exist in Peano arithmetic. The second is another easy compactness argument that proves that a function exists, but finding any sort of bound for the function is an open problem.

### Example 4

Let stand for the set of all sets of integers. Let us colour with colours. Then the infinite Ramsey theorem implies that there is an infinite set such that every subset of of size has the same colour. From this we can extract, for any , a finite set with the property that the cardinality of is at least as large as the minimal element of , and also at least as large as such that every subset of of size has the same colour.

This may seem a rather uninteresting observation, but we can now use a standard compactness argument to prove that for every and there must exist such that for any -colouring of the subsets of of size there is a subset with and such that every subset of of size has the same colour. The proof is just like the first proof in Example 3: one takes a sequence of purported counterexamples and lets them converge pointwise to a limiting colouring that contradicts the infinitary result that we deduced from Ramsey's theorem.

The interest in this result is that the dependence of on and is known to be so vast (because there is a clever way of constructing colourings that give rise to enormous lower bounds) that the resulting function cannot be described in Peano arithmetic. This means that the theorem itself cannot be proved in Peano arithmetic: in a certain sense we were forced to use the axiom of infinity to prove it. This fact, first shown by Paris and Harrington, was philosophically significant because it showed that there were unprovable statements that were far less artificial than the statement cooked up by Gödel in his incompleteness theorem.

### Example 5

Let be a finite graph with maximum degree and let be an integer. The -neighbourhood of a vertex is the set of all points that can be reached from by a path of length at most If you pick a random vertex of then you can look at its -neighbourhood as a graph, considered up to isomorphism. Let's call the -neighbourhood distribution of the probability distribution associated with these -neighbourhoods. In other words, given a graph of radius about some point one is asking what the probability is that a random vertex of has an -neighbourhood that is isomorphic to with an isomorphism that sends to

Given any a routine compactness argument shows that there is a finite set of graphs of maximum degree such that the -neighbourhood distribution of any finite graph differs by at most (pointwise, say, though since there are only finitely many different possible -neighbourhoods you can take any measure of closeness you like) from the -neighbourhood distribution of at least one of the The proof goes as follows: the set of possible -neighbourhood distributions lives in a compact set, by Tychonoff's theorem (since it belongs to raised to the power the set of all possible -neighbourhoods). Therefore, it is totally bounded. This means that it can be covered by a finite number of open balls of any given radius, which follows instantly from the definition of compactness. And that's all there is to it. But this proof gives no clue about the sizes of the graphs And in fact, no quantitative bound is known, which is rather extraordinary. Even a huge estimate would be interesting.

### General discussion

The last example above was not quite the same as the others: it was a direct application of compactness rather than of sequential compactness. However, it was similar enough in spirit to be contained in this article. (If, however, people can think of more compactness arguments that use total boundedness in this way, then it might be better to create a new sub-article of How to use compactness and transfer this example. The author learned of this open problem from Lászlo Lovász (which is discussed in Section 5.5 of this survey article).