Theorems for nothing (and the proofs for free) [closed]

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Some theorems give far more than you feel they ought to: a weak hypothesis is enough to prove a strong result. Of course, there's almost always a lot of machinery hidden below the waterline. Such theorems can be excellent starting-points for someone to get to grips with a new(ish) subject: when the surprising result is no longer surprising then you can feel that you've gotten it.

Let's have some examples.

-

15
I like the Dire straits reference ;) – Grétar Amazeen Nov 13 2009 at 14:58

2
Time to put this one to bed. (ie, time to close it, I deem.) – Andrew Stacey Jun 23 2010 at 18:06

3
What happened between November and June that rendered this question no longer relevant? – I. J. Kennedy Oct 9 2010 at 23:52

1
Wow Andrew. I am not normally surprised when I see you on the list of closers of a question (and most times it is actually there for a good reason), but I did not expect you to go that far, particularly leaving us the mystery of how your question all of a sudden became no longer relevant. Did you intend to use the theorems-for-nothing list, e. g. a popular talk? If yes, what did you use and how well was it absorbed? But even then, I am not sure whether the question is no longer relevant just because it is not relevant to you... – darij grinberg May 4 2011 at 7:06

1
Darij: Vaguely relevant meta threads: meta.mathoverflow.net/discussion/210 and meta.mathoverflow.net/discussion/459 (If you really want to discuss this, start a thread on meta about it) – Andrew Stacey May 4 2011 at 9:01
show 1 more comment

25 Answers

Every compact metric space is (unless it's empty) a topological quotient of the Cantor set.

What, every compact metric space? Yes, every compact metric space.

-
That's quite surprising! What are some good references for this? – Justin DeVries Nov 13 2009 at 16:59

5
Surprising, yes, but once you know about it, it seems easy enough to cook up a proof. Just write the set as a union of two closed subsets, decide to map the left half of the Cantor set onto one and the right half to the other, then do the same to each of these two sets, and so on. In the limit you have the map you want, provided you have arranged for the diameters of the parts to go to zero. – Harald Hanche-Olsen Nov 13 2009 at 19:04

6
Right! Once you know it, it's fine. But I think it's capable of changing one's intuition on what spaces and maps are. After all, the Cantor set is just a sprinkling of dust; how could it be capable of covering a big fat space like the 3-ball? – Tom Leinster Nov 14 2009 at 0:25

6
After this theorem has done its job changing your intuition, though, it's pretty easy to believe. A surjective continuous map glues stuff together. And the Cantor set is not "just" a sprinkling of dust; it's a sprinkling of a whole lot of rather clumpy dust. So it shouldn't be surprising that you can glue all this clumpy dust into many different forms. – Mark Meckes Dec 2 2009 at 14:36

1
I also like the fact that every countable compact Hausdorff space is homeomorphic to a countable successor ordinal equipped with its order topology. This is the Mazurkiewicz-Sierpinski theorem, published originally in French (I think) but also available in English in Z. Semadeni's book 'Banach spaces of continuous functions' in section 8 (the chapter on compact 0-dimensional spaces). A proof of the Alexandroff-Hausdorff theorem (i.e., every compact metric space is a continuous image of the Cantor set) is also there, as well as a bunch of other tasty topology. – Philip Brooker Feb 21 2010 at 12:04
show 1 more comment

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

For me, the theorem that every subgroup of a free group is free is a good example of this: it seems to come for free from covering spaces and the fundamental group, but really all the heavy machinery is just moved underground.

-

Wedderburn's theorem: "Every finite division ring is a field." This is really astonishing if you think of quaternions: nothing analogous in the finite case.

Then of course the classification of finite fields is also very beautiful: exactly one with p^n elements (p a prime and n an integer) and no others.

And as a bonus, Wedderburn's theorem is one of the crispest in all of mathematics: seven words ( or six and a half if you replace division ring by skew-field).

-

You can save one word by replacing "a field" by "commutative" (but maybe we should count syllables rather than words).   – Andreas Blass Jun 20 2011 at 19:44
Great idea, Andreas, thanks! – Georges Elencwajg Jun 21 2011 at 17:23

I had that feeling of getting more than you ought to a couple of weeks ago when reading the first chapter of Rota and Klain's Introduction to Geometric Probability. In particular, I was familiar with the usual derivation of the probability of Buffon's needle crossing a line. So it was amazing to read the solution to a harder problem, Buffon's noodle, which is solved by appealing to a much simpler seeming general symmetry argument. And like you describe, it forms a kind of teaser trailer to draw you you into the rest of the subject.

-

1
I agree, this is a completely wonderful argument. It's also a spectacular example of a more general theorem that's easier to prove. – Tom Leinster Nov 13 2009 at 18:00

3
Here is a related discussion gilkalai.wordpress.com/2009/08/03/… – Gil Kalai Nov 21 2009 at 11:15

Isn't almost every theorem in mathematics an example of a theorem "for free"? One defines natural numbers, and then it follows each of them is a sum of four squares; one defines a notion of a continuous function and of Euclidean space, and Brouwer's fixed point theorem follows. Surely, that is amazing!

With that said here are a handful of the example that lie closer to the surface:

1) Complex-differentiable functions are infinitely-differentiable, and in fact analytic.

2) A function of several complex variables that is holomorphic in each variable is holomorphic in all of them (if it reminds you of 'theorem' that a function that is continuous in each variable separately is continuous... well, then, it should). That is Hartogs' theorem.

3) Any bound on the error term in primes number theorem of the form $\psi(x)=x+O_{\varepsilon}(x^{a+\varepsilon})$ implies the bound $\psi(x)=x+O(x^a \log x)$.

4) Morally related to (3) is the tensor power trick, of which the earliest widely-known example is perhaps the proof of Cotlar-Stein lemma. One of my favorite examples is lemma 2.1 from a paper of Katz and Tao on Kakeya's conjecture.

-

Four squares is nothing, every natural number is also the sum of three triangular numbers.  – Zsbán Ambrus Apr 16 2010 at 19:32

Faithfully-flat descent:

It tells you that you can construct quasicoherent sheaves locally on a faithfully-flat cover. This is pretty amazing, because quasicoherent sheaves are, a priori, only Zariski local. So to specify a sheaf it requires a lot less data than it initially appears.

-

My "canonical example" is Banach-Steinhaus in functional analysis: that, in nice locally convex topological spaces (Banach will do), weakly bounded (or pointwise bounded) implies bounded.

The machinery is quite technical, usually involving the Baire category theorem, but the result is very simple and very surprising. One especial point I like about this is that when you compare normed vector spaces with Banach spaces, then the process of adding more stuff (i.e. completion) actually limits the things that can go wrong. My intuition is that if you want to limit the bad behaviour then you need to work in smaller spaces rather than larger.

-

2
My intuition (for this kind of issue, anyway) is actually the opposite. If you work with a larger space, then there's more "stuff" that nice things (functions, sequences, whatever) have to play nicely with. So the bigger the space, the nicer they must be. – Mark Meckes Nov 13 2009 at 15:12
I agree with Mark: adding stuff tends to rigidify things, think for example of localization. – Alex Collins Nov 13 2009 at 15:18
I agree. It always does seem like you get something for nothing. – Dinakar Muthiah Nov 13 2009 at 15:59
There is a Zabreiko's theorem which extracts the juice of Baire's Category and by invoking it, the Banach-Steinhaus, Open Mapping and Closed Graph theorems come just easily. It says: Every countably subadditive seminorm on a Banach space is continuous. Unfortunately I don't know a good reference. – Abhishek Parab Feb 21 2010 at 2:47

2
@Abhishek Parab: Zabreiko's theorem is proved in Megginson's book 'An Introduction to Banach Space Theory'. It is near the beginning of Section 1.6, which is entitled 'Three Fundamental Theorems'. – Philip Brooker Feb 21 2010 at 11:45

Kuratowski's theorem is a great example of a theorem of the form "the only obstructions are the obvious ones," which are always fun to learn about.

-

I can´t resist to mention the Cayley-Hamilton theorem. Something intuitively correct turns out to be mathematically correct too, but for non-intuitive reasons! I still remember, its proof (I´m here referring to the one using the correspondence between operation and representation) worked from my perspective like a magic, clear, simple, non-trivial and beautiful, and it also made me interested in algebra, beyond the lecture in linear algebra for first-year students. It was nice time...

-
Indeed this is a wonderful theorem. Why is it intuitive correct? From all the first year algebra theorems it was the one where I had no intuition whatsoever. – Gil Kalai Nov 22 2009 at 6:48

3
The cheezy-easy proof that works over the real or complex numbers is to observe diagonalizable matrices are dense in the space of matrices, and the theorem is true for diagonalizable matrices (by computation) then notice the set of matrices that satisfy the theorem are closed. If you want to avoid this kind of argument you can enhance your intuition with the Jordan Canonical Form. :) – Ryan Budney Nov 22 2009 at 10:19

9
Then you just realize that det(tI-A) evaluated at A is some matrix whose entries are monstrously complicated polynomials in the n^2 entries of the matrix A, and since they're identically 0 on C^{n^2} each of those entries must be the zero polynomial; thus the theorem holds over any commutative ring as well. – Steven Sivek Nov 22 2009 at 13:46

1
Gil: maybe what was meant was the following: consider det(tI-A), and plug in A for t. Personally I wouldn't say this makes C-H "intuitively correct"; instead C-H is suggested by this simple heuristic. – Mark Meckes Nov 23 2009 at 14:03

Tychonoff's theorem — product of any collection of compact spaces is still compact — is amazing and incredibly useful.

-

1
it is not surprising thinking of net convergence and that the product topology is not the box topology (which is not compact). – Martin Brandenburg Dec 30 2009 at 2:35

The Kline sphere characterization, proven by Bing:

A compact connected metric space (with at least two points) is the 2-sphere if and only if every circle separates and no pair of points does.

-

Nitpick: A singleton set seems to be an exception. The wikipedia article seems to have missed that. I'll edit it later if nobody beats me to it. (I have a bus to catch.) – Harald Hanche-Olsen Nov 13 2009 at 19:11
Thanks.  Corrected. – Richard Kent Nov 13 2009 at 19:24

Once the machinery of (co)homology is developed, Brouwer's Fixed Point seems to come for free, it's extremely straightforward to prove and has quite a lot of important consequences.

-

I'm not sure I really understand the question though; do you just mean surprisingly easy to prove results (that have many substantial consequences)? – Sam Derbyshire Nov 13 2009 at 20:50

Unfortunately, a lot of these kinds of statements in combinatorics are only conjectural. One example (again, only conjectural) that came up in conversation the other day doesn't give a particularly natural result, but it's hugely surprising: the Erdos-Gyarfas conjecture in graph theory, which has pretty much the weakest possible condition for any statement of its form.

Now that I think about it, though, Ramsey theory is all about "theorems for nothing." I'm a big fan of the sunflower lemma when it comes to Ramsey-theoretical statements that deserve to be better known -- the only condition there is that your sets have to be relatively small, and there have to be a lot of them. (And that second part is conjecturally not even necessary...)

-

To me, the canonical example is the Poincare Conjecture. Why SHOULD a three dimensional manifold with trivial fundamental group actually be the sphere? In higher dimensions, there are LOTS of simply connected things, but in two and three, simply connected and compact manifold determines the manifold uniquely.

-

6
The proof in this case seems rather pricey. – Ryan Budney Nov 13 2009 at 18:59

1
Well, there's a lot of machinery hidden underneath it, yeah. But the statement looks like you're getting a huge amount of specificity from just a small hypothesis. – Charles Siegel Nov 13 2009 at 19:26

That there are infinitely many primes has some simple proofs, but I remember being shown that the sum of the reciprocals of the primes diverges which had some more machinery in it that was kind of neat to my mind.

-

I am not sure I fully understand the question. Is it the case that the theorem itself gives you a huge mileage while its proof is extremely difficult, (Characterization of finite simple group is an ultimate example; the Atiyah-Singer index theorem and the BBD(G)-decomposition theorem are other examples; or is it a case that understanding the proof (which is feasible) gives you a lot of mileage and a feeling that you got grip with the subject.

Anyway, a theorem which, to some extent, has both these features is Adams's theorem asserting that d-dimensional vectors form an algebra (even non-associative) in which division (except by 0) is always possible only for , 2, 4, and 8. (In these cases there are examles: the Complex, Quaternions and Cayley algebras.)

-

Although not exactly what you're after, the question reminds me of Reynolds' parametricity theorem, or as Philip Wadler puts it: Theorems for Free!

The basic idea is that a polymorphic construction (in a polymorphic lambda calculus) must behave uniformly, and so must preserve relations. For example, any term of type $\Pi X. X\to X$ must be the identity function, and every term of type $\Pi X Y. X\times Y\to X$ must be the first projection.

-

The Gauss-Bonnet theorem is a deep result relating the geometry of a surface to its topology, and its proof is very simple (the local version comes almost from nothing, and the main difficulties for the global one are topological results about triangulations). Also, it has some amazing corollaries: the integral of the gaussian curvature over a compact orientable surface is a topological invariant (${\int\int}_{S}{K}d\sigma = 2\pi\chi(S)$, where $\chi(S)$ is the Euler-Poincaré characteristic of $S$); every compact regular surface with positive gaussian curvature is homeomorphic to the sphere $S^2$; and so on.

-

The only group with order $p$ a prime is $\mathbb{Z}/p\mathbb{Z}$

-

I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).

Gallai's Lemma.

Let $G$ be a connected graph such that $\nu(G-x)=\nu(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$

Remark: $\nu(G)$ is the size of a maximum matching of $G$, and def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.

Proof for free. In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.

Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Therefore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. In particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.

Edit. For completeness, I decided to include the derivation of Tutte-Berge from Gallai's lemma. Choose $X \subset V(G)$ maximal such that def$(G-X) -|X|=$ def$(G)$. By maximality, every component of $G-X$ satisfies the hypothesis in Gallai's lemma. Applying Gallai's lemma to each component, we see that $X$ gives us equality in the Tutte-Berge formula.

-

The Riesz-Thorin interpolation theorem; the complex analysis behind it never fails to surprise me.

-

Artin-Schreier Theorem: If k is a field of characteristic p and strictly contained in its algebraic closure K and such that [K:k] is finite THEN (was surprising for me..) p is actually 0 and K = k(sqrt(-1)) and k is a real closed field!

A not so well known but deserving result from the "failed" thesis of Abhyankar: If K and L are algebraically closed fields contained in another algebraically closed field, then the compositum KL is not necessarily algebraically closed.

-

1
Abhyankar's result is probably not that surprising to many of us. But I was simply amazed since we take algebra in undergrad and know algebraically closed fields and compositums and we hardly ask that question.. I needed to answer that question later while writing my PhD and to my surprise Abhyankar was doing the same in his thesis. – Jose Capco Nov 21 2009 at 22:01

Oh! From uniqueness of the countable dense linear order without endpoints: take (for instance) a countable ordinal $λ$, and consider the anti-lex order on $\mathbb{Q}\timesλ$. This is a countable dense linear without endpoints, so it's order-isomorphic to $\mathbb{Q}$; in particular, $\mathbb{Q}$ contains a subset with order-type $λ$ --- e.g. the isomorphs of anything $(\frac{5}{8},j)$. The same result for subsets of $\mathbb{R}$ is a more usual application of transfinite induction/AC/Zorn's lemma; here it's all hidden in the $\aleph_0$-categoricity result about dlow/oep.

-

I like the theorem, I think it's Gallagher's, that says: Most polynomials with integer coefficients are irreducible and have the full symmetric group as Galois group (over the rational numbers).

The precise formulation asserts that the number of bad polynomials, i.e., the number of polynomials $X^r + a_1 X^{r-1} + \cdots + a_r$ with $|a_i|\leq N$ that DO NOT have the full symmetric group as Galois group is $$O(r^3(2N+1)^{r-\frac{1}{2}}\log N)$$ (out of $(2N+1)^r$ polynomials).

-

Another good example is the Johnson-Lindenstrauss Lemma that says that any $n$ points in a Hilbert space can be embedded in a $O(\log n)$-dimensional Euclidean space with distances preserved upto any factor. It turns out that JL-style results crop up in many different versions, the main result itself has proofs ranging from 1 page to 10 pages, and it just keeps on giving :)

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 62, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.940354585647583, "perplexity_flag": "middle"}