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).