393
$\begingroup$

There are mathematical proofs that have that "wow" factor in being elegant, simplifying one's view of mathematics, lifting one's perception into the light of knowledge, etc.

So I'd like to know what mathematical proofs you've come across that you think other mathematicans should know, and why.

  • 21
    There is a lot to be said for not clever arguments.2012-08-05
  • 3
    As an extraordinarily elegant theorem whose proof is extraorinarily _in_elegant, I would nominate Matijasevich's theorem, which disposed of Hilbert's 10th problem in 1970. Think of it like this: A set $A$ of $n$-tuples of integers is "decidable" if there is an algorithm that, when given $n$, returns "yes" or "no" according as $n\in A$ or not. And $A$ is "semi-decidable" if there is an algorithm that when given $n$, eventually halts if $n\in A$ and runs forever otherwise. In the '30s it was shown by Turing, Kleene, Church, and other that some semi-decidable sets are not decidable. Then.....2012-08-05
  • 2
    .....then call a set $A$ of $n$-tuples of integers "Diophantine" if there is a polynomial $f(x_1,\ldots,x_k,y_1,\ldots,y_\ell)$ such that $(x_1,\ldots,x_k)\in A$ if and only if $\exists y_1\ \ldots\ \exists y_\ell\ f(x_1,\ldots,x_k,y_1,\ldots,y_\ell)=0$. It's obvious that every Diophantine set is semi-deciable. Matijasevich's theorem says every semi-decidable set is Diophantine. If you see the proof presented step-by-step in lectures meeting one hour per week, it will go maybe from six to eight weeks. The _statement_ of the theorm is stunning; the _proof_ of the theorem is.....involved.2012-08-05
  • 0
    OK, it seems I used the same notation, "$n$", for two different things above: the number of components in the tuple, and the tuple itself. Parse everything accordingly.2012-08-05
  • 2
    For those who want to take a closer look at a version of the "extraordinarily __in__elegant" proof of Matiyasevich's theorem mentioned by Michael may wish to consult Stephen Simpson's [notes](http://www.math.psu.edu/simpson/notes/topics-s05.pdf) following Davis's Monthly article. I think there is more than a bit of beauty and elegance to it and that it is involved strikes me as rather unsurprising.2012-08-05
  • 0
    @t.b. : Probably you're right, except that in going through the proof step by step the first time without having thought about the methods before, one may be able to see only the steps and not the structure of the proof as a whole. Whereas the statement of the theorem, on the other hand, is instantly startling.2012-08-05
  • 0
    @Michael: I agree with that. Probably the main difficulty (apart from the cleverness that goes into the proof) is that we are not as a rule trained in this kind of formal analysis of our arguments. Let me apologize for not pinging you in my previous comment, I didn't mean to talk behind your back.2012-08-05
  • 1
    @All Links to proof references, as far as possible, would be very cool! Thanks the ones given so far...2012-08-05
  • 0
    I'd be interested in the "why" as well, but so far this seems to have been overlooked.2012-08-05

23 Answers 23