On proving that a certain set is not empty by proving that it is actually large

It happens occasionally that one can prove that a given set is not empty by proving that it is actually large. The word "large" here may refer to different properties.

For example, one can prove that a certain set is not empty by proving that its cardinality is big, as in the proof that there exist transcendental numbers : The set of algebraic numbers is countable, but the set of real numbers is uncountable, so there is uncountably many transcendental numbers.

One could also prove that a certain set is not empty by proving, for example, that it has positive measure, that it is dense, etc.

What are some good examples of such proofs?

-
Some of these proofs can be categorized as the probabilistic method, and “The Probabilistic Method” by Noga Alon and Joel H. Spencer (Wiley) seems to be a very good book on it. –  Tsuyoshi Ito Aug 3 '10 at 14:50
Community wiki? –  Dylan Wilson Aug 3 '10 at 18:47

Many existence proofs which exploit the idea of Baire category.

For instance, existence of a metrically transitive automorphism of the closed unit square was first obtained by the category method (see "Measure-preserving homeomorphisms and metrical transitivity" by Oxtoby and Ulam) . Another classical example is due to Banach who proved that every function from a residual subset of $C[0,1]$ is nowhere differentiable.

A nice and elementary book by Oxtoby discusses these and many other applications of the category method.

-
One of my favorites in this regard is the existence of a first-order linear PDE with no solution. One writes down a PDE of a certain form with one of the coefficients $f$ left undetermined, finds some conditions on $f$ necessary for the existence of a solution, and then shows the set of $f$ satisfying these conditions is meager in $L^\infty$. Fritz John's PDE book has the details. –  Nate Eldredge Aug 4 '10 at 22:32
That's an amazing example! Thanks. –  Andrey Rekalo Aug 4 '10 at 22:42
Nice example! I also like the proof of the existence of many continuous functions $f$ on the unit circle whose fourier series diverge at a given point, using Baire's theorem. –  Malik Younsi Aug 5 '10 at 12:17

Sard's lemma is an example - the set of regular values is non-empty since it has positive measure.

The following example also answers your question: Recently I proved the following lemma.

Let $f\colon M\to N$ be a smooth map, $M$ is a non-empty paracompact manifold. Let $k$ be a maximal rank of a differential $df(x)$ over $x\in M$. Then there exists a point $y$ in $f(M)$ such that the rank of the differential $df$ is maximal for all points of $f^{-1}(y)$.

-

Frequently in arguments in algebraic number theory, one has to choose a prime that satisfies some list of conditions, and is bigger than some given bound. (A simple example of the kind of condition that I am thinking of would be that the prime should lie in a given congruence class modulo some number $n$.) One then interprets the conditions in such a way as to be able to apply the Cebotarev density theorem to conclude that there are infinitely many primes satisfying the given conditions, and so in particular a suitable prime can be found that lies above the desired bound. (In the simple example, one would use Dirichlet's theorem on the existence of infinitely many primes in arithmetic progression, which from this point of view is a special case of Cebotarev density.)

-

Virtually any existence proof in analytic number theory goes by giving a quantitative lower bound (or asymptotic formula) for the number of objects of interest. For example, there are infinitely many primes of the form $x^2 + y^4$ was shown by Friedlander and Iwaniec by finding an asymptotic formula for the counting function of such primes.

When I was in graduate school, a paper appeared on the arxiv purporting to prove the twin prime conjecture by establishing an asymptotic formula for the number of twin primes up to $x$. I remarked to my advisor, Iwaniec, that surely there was a mistake since the conclusion was so strong. He responded by saying that giving the asymptotic formula was actually a good sign. (It should go without saying that there was a mistake in the paper).

-

This page of the Tricki describes exactly the technique you are looking for.

-

There are non-Borel sets that are Lebesgue measurable. This is proved in the following way. First show that the Borel sigma algebra for the real line is uncountable with cardinality of the real line. On the other hand, you have the Cantor set which is uncountable(cardinality = $\mathbb R$) and is of Lebesgue measure zero. Since Lebesgue measure is complete, every subset of the Cantor set belongs to the Lebesgue sigma algebra and therefore the Lebesgue sigma algebra has cardinality of the power set of the reals.

Construction of explicit examples would require axiom of choice.

-
When you say that the Borel sigma algebra is "uncountable," do you mean to say that its cardinality is the same as the cardinality of the reals? –  Charles Staats Aug 3 '10 at 15:15
@Charles Staats : Yes, that is what I mean. I have edited to incorporate this. –  Anweshi Aug 3 '10 at 15:25
Your "require Axiom of Choice" is, I think, wrong. As your link shows, without AC it is consistent that every set of reals is Borel, so even your cardinality proof fails. –  Gerald Edgar Aug 3 '10 at 17:24
@Gerald Edgar: What I had in mind when I linked, was the example of Hamel basis which I mentioned there. Yes, it is true that without AC the proof that the Borel sigma algebra has cardinality that of the real line, would fail. –  Anweshi Aug 3 '10 at 17:36
Explicit examples of sets that are Lebesgue measurable but not Borel are known. But, of course, not as easy as your cardinality proof. I mean here constructions of analytic sets that are not Borel, which are quite explicit. (Unlike the Hamel basis examples, which are not.) –  Gerald Edgar Aug 4 '10 at 13:37

C.Cornut and V.Vatsal's proof (as in e.g Inventiones mathematicae 148) of the non-triviality of CM points on zero and one-dimensional quaternionic Shimura varieties as one goes up an anticylcotomic $\mathbb Z_{p}$-extension $K_{\infty}$ is by showing that reduction modulo $\ell$ of CM points is actually onto points modulo $\ell$ for infinitely many $\ell$. In particular, their proof actually implies the much stronger statement that the $\mathbb Z_{p}[[\Gamma]]$-module generated by the image of the norm-coherent CM points under the Kummer map has trivial $\mu$-invariant (here $\Gamma$ is the Galois group of $K_{\infty}/K$).

-

The theme is prevalent in combinatorial number theory and ergodic theory. Consider the ergodic Szemerédi theorem, for instance. It says that if $(X,\mathcal{B},\mu,T)$ is a measure-preserving system and $A \in \mathcal{B}$ has $\mu (A) >0$, then $\forall k \in \mathbb{N}$ $\exists n \in \mathbb{N}$ so that $\mu (A \cap T^{-n}A \cap T^{-2n}A \cap \cdots \cap T^{-kn}A)>0$. It turns out that it's easier to prove that measure of the intersection is positive for infinitely many $n$. In fact, Furstenberg's original proof showed that $\liminf_{N \to \infty} \frac{1}{N} \sum_{n=1}^{N} \mu (A \cap T^{-n}A \cap T^{-2n}A \cap \cdots \cap T^{-kn}A) > 0$.

-

Not quite an answer to the question but related (large modulo $2$):

Zagier's beautiful proof (Amer. Math. Monthly 97 (1990), no. 2, 144) that every prime congruent to $1$ modulo $4$ is a sum of two squares is based on the fact that the cardinality of a certain finite set is odd and the set is thus non-empty.

-
5 = 1 (mod 4). Is 5 a square? –  John Bentin Aug 3 '10 at 17:24
Is any prime a square? –  Kevin Ventullo Aug 3 '10 at 18:24
Any prime in an empty set is a square. So first you have to establish that the set isn't empty. –  John Bentin Aug 3 '10 at 20:15
I do not understand these comments. The Theorem does not state that $5$ is a square (a prime is never a square by definition) but that $5$ is a sum of two squares: $5=2^2+1^1$. –  Roland Bacher Aug 6 '10 at 9:19

As Tsuyoshi Ito commented, the probabilistic method in combinatorics is an example. You use a probability measure on the space of possibilities, and show that the set with the desired probabilities has positive measure, hence is nonempty.

The classic example of this is the result by Erdős (1947) that the Ramsey number $R(t,t)$ grows at least exponentially with $t$. If you consider a random coloring of the edges of the complete graph on $n$ vertices, then the probability that a particular complete subgraph on $t$ vertices is monochromatic is $2^{1-{t \choose 2}}$. If ${n\choose t} 2^{1-{t \choose 2}} \lt 1$, then a random coloring has no monochromatic subgraph with positive probability. This is the case for $n = \sqrt 2^t$, $t\gt 2$, so $R(t,t) \ge \sqrt2^t$ for $t \gt 2$.

For slightly smaller $n$, most random colorings of the complete graph on $n$ vertices have no monochromatic subgraph of size $t$, but finding a construction has been an open problem.

-

A kind of analogue of Sard's Lemma in Algebraic Geometry is Bertini's Theorem:

"Given a linear sistem $|L|$ on a smooth projective variety X, its general element is smooth outside the base points".

In particular, if $|L|$ is base-point free then the set of smooth elements in $|L|$ is dense, in particular non-empty.

-

I just heard this in a talk by Jan Krajicek: It is known that there are Boolean functions that require a "large" circuit to compute them, but the proof is probabilistic. (I.e., the measure of the set of such Boolean function (say of arity n) is known to be nonzero.) No explicit construction of such functions is known.

-