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 $f$ be a continuous function from the closed interval $[0,1]$ to $\mathbb{R}$ such that $f(0)<0$ and $f(1)>0$ . We would like to find $u\in[0,1]$ such that $f(u)=0$ . (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 $[0,1]$ is an infinite, continuous structure. An obvious finite, discrete approximation is the set of points $X_n=\{0,1/n,2/n,\dots,(n-1)/n,1\}$ , where $n$ is some large positive integer. So let us imagine that we have a function $f$ defined on $X_n$ with $f(0)<0$ and $f(1)>0$ .

But just a moment – shouldn't we also decide what we mean by saying that $f$ 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 $j$ such that $f(j/n)=0$ . In fact, we can't even hope to find a $j$ such that $f(j/n)$ is close to 0, since we could define $f(j/n)$ 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 $f$ defined on $[0,1]$ and restrict it to $X_n$ for larger and larger $n$ , then counterexamples of this kind will become less and less of a problem.

Here is one thing we can say: there must be some $j$ such that $f(j/n)<0$ and $f((j+1)/n)\geq 0$ . The proof is highly reminiscent of the usual proof of the intermediate value theorem, since we just let $j$ be maximal such that $f(j/n)<0$ .

It may seem perverse to give another proof, but actually there is an importantly different argument that establishes the same conclusion. Let us define $g(j/n)$ to be $0$ if $f(j/n)<0$ and $1$ if $f(j/n)\geq 0$ . Then $\sum_{j=0}^{n-1}(g((j+1)/n)-g(j/n))=g(1)-g(0)=1$ . Therefore, there must exist $j$ such that $g((j+1)/n)-g(j/n))>0.$ But this can happen only if $g((j+1)/n)=1$ and $g(j/n)=0$ , which tells us that $f((j+1)/n)\geq 0$ and $f(j/n)<0$ . (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 $n$ we can find some $j=j(n)$ such that $f(j/n)<0$ and $f((j+1)/n)\geq 0$ . Let us write $u_n$ for $j(n)/n$ and $v_n$ for $(j(n)+1)/n$ .

Now a standard discretizer's move is to apply the Bolzano-Weierstrass theorem: since the sequence $(u_n)$ lives in the compact set $[0,1]$ , it has a convergent subsequence $(u_{n_k})$ . Let $u$ be the limit of this subsequence. Since $|u_{n_k}-v_{n_k}|\leq 1/n_k$ for each $k$ , we also have $v_{n_k}\rightarrow u$ . But $f$ is continuous, so $f(u_{n_k})\rightarrow f(u)$ and $f(v_{n_k})\rightarrow f(u)$ . Since $f(u_{n_k})<0$ for every $k$ , $f(u)\leq 0$ . And since $f(v_{n_k})\geq 0$ for every $k$ , $f(u)\geq 0$ . So $f(u)=0$ .

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 $n$ 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 $j$ such that $f(j/n)<0$ and $f((j+1)/n)\geq 0.$ 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 $f$ takes only the values $0$ and $1$ , and $f(0)=0$ and $f(1)=1$ , then $f$ cannot be continuous. The discrete problem would then have been to find a discrete version of a "sudden jump", namely a $j$ such that $f(j/n)=0$ and $f((j+1)/n)=1$ .

Comments

The above example is arguably

Thu, 30/04/2009 - 12:38 — b.jacelon

The above example is arguably an instance of a more general discretization strategy: that of replacing compact spaces by finite complexes. For example, every compact manifold has the homotopy type of (and hence the same cohomology as) a finite CW complex. Perhaps more in the spirit of this article, every compact subset $X$ of $\mathbb{R}^n$ can be written as the intersection of a decreasing sequence $(X_j)$ of compact sets, each of which is a finite simplicial complex. (Just take successive triangulations and keep the bits that intersect $X$ .) One can hope to use simple arguments (such as induction on the number of simplices) to deduce some property about the $X_j$ , and then use a limiting argument to deduce the property for $X$ . For example, the C*-algebra $C(X)$ of continuous functions on $X$ is the direct limit of the algebras $C(X_j)$ . If one is, say, interested in proving something about the $K$ -theory of $X$ , then the relevant continuity property is that $K_*(\lim C(X_j)) = \lim K_*(C(X_j))$ (and a useful observation might be that $K_*(C(X_j))$ is finitely generated).