4
$\begingroup$

Which are the deepest theorems with the most elementary proofs?
I give two examples:
i) Proof_of_the_Euler_product_formula_for_the_Riemann_zeta_function
ii) Proof that the halting problem is undecidable using diagonalization

  • 7
    @GM2001: If you edit this question any more, I will lock it, which will prevent further edits, comments, and answers.2011-10-26

2 Answers 2

9

These perhaps aren't particularly deep, but they are the first that come to mind.

  1. Irrationality of $\sqrt{2}$ by contradiction.
  2. Uncountability of the reals by diagonalization.
  3. Existence of graphs with arbitrarily high girth and chromatic number by the probabilistic method.
  • 0
    I think the linked proof in (1) is misnamed, and is not a proof by *infinite descent* (unlike [this one](http://en.wikipedia.org/wiki/Infinite_descent#Irrationality_of_.E2.88.9A2)).2011-10-22
3

I think one should not confuse "important with "deep". The facts that $\sqrt{2}$ is irrational, that there is no surjective map $X\to2^X$, or that there are an infinity of primes, are certainly important or even "fundamental", but their proofs are so simple that one cannot call them "deep". A theorem is "deep" when its proof is really hard and, above all, requires a theory that transcends the realm the problem is formulated in. Consider, e.g., Gauss' theorem about which regular $n$-gons can be constructed with ruler and compass.

  • 3
    To add on Srivatsan's comment, the proof of |P(X)|>|X| while seemingly trivial nowadays required the development of an entire new field in mathematics. I'd say this qualifies as pretty deep.2011-10-23