![]() |
Quick description
Suppose one wants to show that all objects in some class obey some property
, if
is a sufficiently large parameter (independent of
). Then one way to establish such a result is by a "compactness and contradiction" argument, which runs as follows:
-
Suppose for contradiction that the claim is false. Thus, no matter how large one takes
, one can find an object
which fails to obey the property
.
-
Use some sort of compactness theorem to show that some subsequence
of these objects converges (in a suitable topology) to a limit object
.
-
Show that the limit object
obeys some limit property
.
-
Deduce that the approximating objects
obey the property
for sufficiently large
, obtaining the desired contradiction.
The original claim may involve "finitary" objects (e.g. finite sets of integers, finite graphs, discrete random variables, etc.), but in order to obtain compactness, the limit object
usually needs to live in some "infinitary" class (e.g. infinite sets of integers, infinite graphs, continuous random variables, etc.). On the other hand, while the original properties
to be proved tend to be of a fairly "quantitative" nature (due to the presence of the parameter
), the limit property
can be of a "qualitative" nature. Thus the compactness method allows one to trade a finitary, quantitative problem for an infinitary, qualitative one, thus bringing to bear the power of "soft analysis" tools such as measure theory, ergodic theory, topology, etc. However, one drawback of the compactness method is that it becomes rather difficult to extract explicit bounds on the parameter
that one obtains at the end of the day, due to the indirect nature of the argument (or more precisely, one can eventually obtain bounds by a large amount of effort, but they tend to be quite poor - tower-exponential bounds, for instance, are quite frequent.)
Prerequisites
Analysis
Example 1
See the blog posts "The correspondence principle and finitary ergodic theory" and "Soft analysis, hard analysis, and the finite convergence principle" for several examples.
Example 2
(Discuss minimal-energy blowup solutions in critical PDE)
General discussion
In order to get a sufficient amount of compactness, it is often necessary to settle for convergence in a weak topology, so that results such as the Banach-Alaoglu theorem, Prokhorov's theorem, or the Arzela-Ascoli theorem can be applied. In particular, the use of diagonalization arguments to extract the convergent subsequence are common; see "convergent subsequences and diagonalization" for further discussion. However, in some cases one can later try to "upgrade" the weak convergence to a stronger notion of convergence.
Instead of taking a convergent subsequence of the original sequence
, one can also try taking an ultralimit or ultraproduct of the
, or to transfer the problem to a non-standard model in which
becomes a non-standard parameter, larger than all standard parameters.
Comments
There is some overlap between
Sat, 02/05/2009 - 20:12 — gowersThere is some overlap between this and convergent subsequences and diagonalization. Perhaps some interlinking or merging would be appropriate.
Looks like this article is basically a special case
Sun, 03/05/2009 - 16:41 — tao... of the diagonalisation article, so I've interlinked and parented accordingly.