Tricki

## Discretization followed by compactness arguments

### Quick description

One of the basic difficulties associated with analysis is that it deals with infinite structures. One of the most common ways of dealing with this problem is to find ways of recasting apparently infinitary statements as finitary ones: for example, this is one of the motivations for the epsilon-delta approach to analysis. An even more explicit way of making analysis problems finite is discretization: one approximates an infinite structure by a finite one, proves a finite statement for the approximation, and finishes with a limiting argument. Compactness can be of great help with this process.

### Example 1

Here is a proof of the intermediate value theorem—but not the one usually given. Let be a continuous function from the closed interval to such that and . We would like to find such that . (This is not the most general form of the intermediate value theorem, but it is easier to discuss and the general form can easily be deduced from it.)

Our approach to this task will be to discretize it. The closed interval is an infinite, continuous structure. An obvious finite, discrete approximation is the set of points , where is some large positive integer. So let us imagine that we have a function defined on with and .

But just a moment – shouldn't we also decide what we mean by saying that is continuous? We shall return to this question, but for now let us simply forget about it and press on.

It is obvious that we can't hope to find a such that . In fact, we can't even hope to find a such that is close to 0, since we could define to be -1 up to a certain point and 1 thereafter. However, the idea of what follows is that if we start with a continuous function defined on and restrict it to for larger and larger , then counterexamples of this kind will become less and less of a problem.

Here is one thing we can say: there must be some such that and . The proof is highly reminiscent of the usual proof of the intermediate value theorem, since we just let be maximal such that .

It may seem perverse to give another proof, but actually there is an importantly different argument that establishes the same conclusion. Let us define to be if and if . Then . Therefore, there must exist such that But this can happen only if and , which tells us that and . (This is an example of just how useful averaging arguments can be.) We shall see later that this argument is more amenable to generalization.

Let us now see what happens if we try to apply a limiting argument, whatever that might mean. So far, we know that for each we can find some such that and . Let us write for and for .

Now a standard discretizer's move is to apply the Bolzano-Weierstrass theorem: since the sequence lives in the compact set , it has a convergent subsequence . Let be the limit of this subsequence. Since for each , we also have . But is continuous, so and . Since for every , . And since for every , . So .

### General discussion

What we did in the above proof can be viewed as a three-stage process. First, we converted a continuous problem into a discrete problem that depended on a parameter that measured its degree of refinement. Next, we solved the discrete problem. Finally we used a limiting argument to show that we could obtain a solution to the continuous problem from the sequence of solutions to the discrete problems.

Just to be completely explicit, the discrete problem in this case was to find such that and The way we phrased the continuous problem, it was not quite clear that this was the appropriate discrete problem, but it would have been clearer if we had used an equivalent version of the continuous problem: that if takes only the values and , and and , then cannot be continuous. The discrete problem would then have been to find a discrete version of a "sudden jump", namely a such that and .