# What are the most elegant proofs that you have learned from MO?

One of the things that MO does best is provide clear, concise answers to specific mathematical questions. I have picked up ideas from areas of mathematics I normally wouldn't touch, simply because someone posted an eye-catching answer on MO.

In particular, there have been some really elegant and surprising proofs. For example, this one by villemoes, when the questioner asked for a simple proof that there are uncountably many permutations of $\mathbb{N}$.

The fact that any conditionally convergent series [and that such exists] can be rearranged to converge to any given real number x proves that there is an injection P from the reals to the permutations of $\mathbb{N}$.

Or this one by André Henriques, when the questioner asked whether the Cantor set is the zero set of a continuous function:

The continuous function is very easy to construct: it's the distance to the closed set.

There must many such proofs that most of us have missed, so I'd like to see a list, an MO Greatest Hits if you will. Please include a link to the answer, so that the author gets credit (and maybe a few more rep points), but also copy the proof, as it would nice to see the proofs without having to move away from the page.

(If anyone knows the best way to copy text with preservation of LaTeX, please advise.)

I realize that one person's surprise may be another person's old hat, so that's why I'm asking for proofs that you learned from MO. You don't have to guarantee that the proof is original.

-
Shortly: mathoverflow.net/questions/26520/…. –  Wadim Zudilin Jun 27 '10 at 1:32
Also shortly: How to capture a sphere in a knot? mathoverflow.net/questions/8091/… –  Gjergji Zaimi Jun 27 '10 at 2:10
I've tried in vain to answer this question, and I've come to realize that for me, learning slick proofs has not been the most attractive or memorable part of the MO experience (though I must have learned a few here). –  Thierry Zell Apr 16 '11 at 23:00

In this fantastic answer, Ashutosh proved that the Axiom of Choice is equivalent to the assertion that every set admits a group structure.

In ZF, the following are equivalent:

(a) For every nonempty set there is a binary operation making it a group

(b) Axiom of choice

Non trivial direction [(a) -> (b)]:

The trick is Hartogs construction which gives for every set $X$ an ordinal $\aleph(X)$ such that there is no injection from $\aleph(X)$ into $X$. Assume for simplicity that $X$ has no ordinals. Let $o$ be a group operation on $X \cup \aleph(X)$. Now for any $x \in X$ there must be an $\alpha \in \aleph(X)$ such that $x o \alpha \in \aleph(X)$ since otherwise we get an injection of $\aleph(X)$ into $X$. Using $o$, therefore, one may inject $X$ into $(\aleph(X))^{2}$ by sending $x \in X$ to the <-least pair $(\alpha, \beta)$ in $(\aleph(X))^{2}$ such that $x o \alpha = \beta$. Here, < is the lexic well ordering on the product $(\aleph(X))^{2}$. This induces a well ordering on $X$.

(The argument is due originally to Hajnal and Kertész, 1973.)

-

Unfortunately I can't find the link but someone mentioned this proof that there are irrational numbers $a$ and $b$ such that $a^b$ is rational: if $\sqrt{2}^\sqrt{2}$ is rational then we are done, if it is irrational then $2 = (\sqrt{2}^\sqrt{2})^\sqrt{2}$ is an irrational raised to an irrational.

-
@Waldim: Sorry but I don't understand your point. Obviously the statement is not deep or a difficult thing to prove using other means; I just found that proof to be very elegant. Different strokes for different folks, I guess. –  Eric O. Korman Jun 27 '10 at 2:49
@Wadim: the point is that without Gelfond or Gelfond-Schneider etc etc it is actually a neat little puzzle to find irrational a,b with a^b rational. Your continuity argument doesn't work without more effort, because you have to check that the map $x\mapsto x^{\sqrt{2}}$ does not have the property that the pre-image of every rational is rational. Of course it doesn't---far from it---but the issue is finding a proof without invoking a transcendence theory sledgehammer. –  Kevin Buzzard Jun 27 '10 at 8:16
Although this proof is pretty, I find it much more interesting as a demonstration of the meaning of the term "non-constructive proof", and I think this is the context in which it is usually presented. –  Dan Piponi Jun 27 '10 at 17:23
Here's a simple, constructive proof: $\sqrt{2}^{\log_{\sqrt{2}} 3} = 3$ and $\log_{\sqrt{2}} 3$ is irrational since otherwise $2^p = 3^q$ for some positive integers $p,q$. It's not as pretty as the $\sqrt{2}^{\sqrt{2}}$ proof, but it shows that no "transcendence theory sledgehammer" is needed to provide an explicit example. –  Mark Apr 15 '11 at 15:59
sigfpe is right when he tacitly suggests that this argument is well-known and classical (which is why I wasn't much wowed by it myself). Come to think of it, sigfpe got everything about it. right :-) –  Todd Trimble Apr 15 '11 at 16:40

I found several very nice proofs which I enjoyed:

1.Brilliant proof of fundamental theorem of algebra by Gian Maria Dall'Ara Ways to prove the fundamental theorem of algebra

2.Some proofs of quadratic reciprocity: What's the "best" proof of quadratic reciprocity? (I especially liked that one: What's the "best" proof of quadratic reciprocity?)

3.Proof that $\mathbb{R}^{2n+1}$ does NOT have a square root (quite elementary and beatiful) Is R^3 the square of some topological space?

4.Nullstellensatz using model theory What are some results in mathematics that have snappy proofs using model theory?

5.If in ring R every countably generated ideal is principal than R is a PID Do there exist non-PIDs in which every countably generated ideal is principal?

6.An infinite dimensional vector space have smaller dimension than it's dual. Slick proof?: A vector space has the same dimension as its dual if and only if it is finite dimensional

7.Topological proof that Z is a Bezout domain. Awfully sophisticated proof for simple facts.

-
"NUllstehlensatz" would be the zero stealing theorem. Instead, it's the zero point theorem, i.e. the "Nullstellensatz". –  Alex B. Apr 16 '11 at 9:41
Alex, now I want to learn enough analysis that I can state and prove a Nullstehlensatz. :-) –  L Spice Apr 16 '11 at 14:14
The Nullstehlensatz should be a security theorem about cryptographic protocols for digital cash. If you break such a protocol, that's a Positivstehlensatz. –  Henry Cohn Apr 16 '11 at 15:46
I imagined it as some sort of complement to pole-pushing. –  L Spice Apr 16 '11 at 18:16

I asked a question a while ago about proving that the real line is connected.

Connectedness and the real line

Omar Antolín-Camarena's Answer and comment prove that the closed interval $[0,1]$ is connected iff it is compact.

-
That is a very nice proof! –  David Roberts Jul 24 '11 at 23:18

My favorite is this proof by Bjorn Poonen that every finite Galois extension of $\mathbb{Q}$ has infinitely many completely split primes. Although Bjorn's proof does not give the density of such primes, as the proof using the Chebotarev Density Theorem does, it is refreshing to see that such an elementary proof exists.

-

My candidate is Jim Belk's one-line answer to the question about the existence of functions from $\Bbb{R}$ to $\Bbb{R}$ whose range is $\Bbb{R}$ on every open interval.

I do wonder, however, if Jim Balk's solution was known to founders of classical set theory (Cantor, Bernstein, Hausdorff, ...).

-
@Ali: I have no idea who first came up with that argument, but my first guess would be Sierpinski. Cantor, Bernstein, and Hausdorff undoubtedly knew the result, but they probably used a "construction" by transfinite induction, like the standard construction of a Bernstein set. –  Andreas Blass Jul 25 '11 at 8:13
@Andreas: I agree that the existence of such a function must have been known to the "founding fathers" of set theory; it is amusing that even though the one-line proof uses AC, there are other proofs that are implementable in $ZF$. Indeed $ZF$ can produce such a function that is equal to $0$ almost everywhere. –  Ali Enayat Jul 25 '11 at 13:36