Discretization followed by compactness arguments

a repository of mathematical know-how

Discretization followed by compactness arguments

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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]

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

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Discretization followed by compactness arguments

Recent articles

Active forum topics

Recent comments