[Math] What are the most elegant proofs that you have learned from MO

alternative-proofexamples

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.

Best Answer

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

Related Question