# Proofs that every mathematician should know? [closed]

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.

-
I think this should be made CW. –  Pedro Tamaroff Aug 5 '12 at 1:10
@PeterTamaroff so do I but my reputation isn't high enough –  user10389 Aug 5 '12 at 1:45
There is a lot to be said for not clever arguments. –  André Nicolas Aug 5 '12 at 2:50
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 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. –  t.b. Aug 5 '12 at 12:56
@All Links to proof references, as far as possible, would be very cool! Thanks the ones given so far... –  draks ... Aug 5 '12 at 17:34

## closed as not constructive by Jasper Loy, Pedro Tamaroff, Asaf Karagila, Zhen Lin, Dominic MichaelisMar 16 '13 at 8:45

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

I think every mathematician should know the following (in no particular order):

1. Pythagorean Theorem.
2. Summing $\sum_{k = 1}^{n} k$ using Gauss' triangle trick.
3. Irrationality of $\sqrt{2}$ by proof without words.
4. Niven's proof of the irrationality of $\pi$.
5. Uncountability of the Reals by Cantor's Diagonal Argument.
6. Denumerability of the Algebraics by Heights and Counting Roots.
7. Infinitude of primes by both Euclid's proof and Euler's proof.
8. Constructibility of the Regular 17-gon by Gauss' explicit construction.
9. Binomial Theorem by Induction.
10. FLT $n = 4$ by Fermat's Infinite Descent.
11. Every PID is a UFD.
12. The $\lim_{n \to \infty} (1 + \frac{1}{n})^{n} = e$ by L'Hôpital's Rule.
13. Pick's Theorem by reduction to triangles and squares.
14. Fibonacci numbers in terms of the Golden Ratio by recurrence relations.
15. $\mathbb{R}^{n}$ is a metric space in more than one way.
16. Euler's Formula $e^{i \theta} = \cos \theta + i \sin \theta$ by differentiation.
17. Summing $\sum_{k \geq 1} \frac{1}{k^{2}}$ by Fourier series.
18. Quadratic reciprocity by Eisenstein's proof (counting lattice points).
19. $(\mathbb{Z}/n \mathbb{Z})^{\times}$ is a group (of units) for $n \in \mathbb{N}$, and $\mathbb{Z} / p \mathbb{Z}$ is a field for prime $p$.
20. Euler's formula $v - e + f = 2$ for planar graphs.
21. Fundamental Theorem of Algebra by Liouville's Theorem.

This is, of course, my opinion....

NB: When I write "by ..." I mean that particular proof methodology (as opposed to another perhaps easier method), because of the pedagogical benefit of that route of proof.

-
Euclid's proof of the infinitude of primes is not a proof by contradiction. (It does not even talk of infinity explicitly; the statement is that given any list of primes, we can extend the list by adding a prime not in the list.) And the version without contradiction is in fact easier for students to understand, and IMHO more elegant. –  ShreevatsaR Aug 5 '12 at 3:44
Absolutely, Euclid's proof is not by contradiction. Dirichlet said Euclid's proof was by contradiction, and so have zillions of otherwise respectable mathematicians. They're wrong. See my joint paper with Catherine Woodgold in the Fall 2009 issue of the Mathematical Intelligencer debunking this falsehood. Euclid's actual proof was simpler and better than the proof by contradiction conventionally attributed to him. –  Michael Hardy Aug 5 '12 at 4:33
If this list is a general consensus, then I am a terrible mathematician... Anyone else? –  Arthur Fischer Aug 5 '12 at 6:40
I don't think 11 is appropriately proved by L'Hospital. $\lim(1+1/n)^n$ is just the definition for $e$, and we only need to prove that it converges! –  Frank Science Aug 5 '12 at 13:50
Hmm. I think that items 11 and 15 depend on hiding the imprecisions in the definitions of $e^x$ as well as the trigonometric functions, so while they look sleek, they wouldn't be on my list. I quite like using an infinitesimal generator for the rotation group for proving 15 anyway. Thanks for the link to Niven's proof. A gem, indeed. 14 and 18 are too trivial unless I misunderstood? –  Jyrki Lahtonen Aug 5 '12 at 13:51

I'm particularly fond of Ramsey's Theorem.

-
Are you fond of the theorem or the proof? –  user10389 Aug 7 '12 at 22:18
Both. But the proof moreso because the R(3,3)≤6 proof is so cool and then it's basically "Well what if we just tried to do *more* of that?" –  Eric Stucky Aug 7 '12 at 23:19

Proofs from THE BOOK is a brilliant compilation of such beautiful succinct proofs.

-
If I said that my reaction to much of "Proofs from THE BOOK" was meh, then that would definitely be a bit harsh. But I am tempted to say it anyway, because by averaging out meh and brilliant I think one comes closer to the truth. –  Pete L. Clark Aug 5 '12 at 13:33
I had better add at least some substance to my previous comment. Someone once said that there is no beautiful proof of a theorem that is not itself beautiful. In line with this I cannot help but judge the book based on the theorems it includes rather than just the proofs. For instance, as a working number theorist I find their selection of theorems in the number theory chapter more than a little off-center. For instance they do not mention quadratic reciprocity but they discuss which binomial coefficients are perfect powers? Weird. –  Pete L. Clark Aug 5 '12 at 13:41
On the other hand, I wrote an entire paper generalizing the first proof they give of Fermat's Two Squares Theorem, so there's definitely some good stuff in there. (I was not struck by the proof of F2ST via Thue's Lemma at the time I read it there, but only later when a colleague brought it to my attention in a different context. But that sounds like my mistake...) –  Pete L. Clark Aug 5 '12 at 13:43

I would say the proof of the Brouwer Fixed Point Theorem for $D^n$ using the fact that $H_n(S^n) \cong \Bbb{Z}$ and $H_n(D^n) = 0$ is nice. The idea of the proof by contradiction that if for no $x$ is $f(x) = x$, we can draw a straight line through these points, that for me was very elegant.

-
The essence of this proof can also be found in Milnor's Topology from the differentiable viewpoint (p.13ff) where the crucial lemma is attributed to Hirsch, A proof of the nonretractibility of a cell onto its boundary, Proc. Amer. Math. Soc. 14 (1963), 364-365. Note: The simplicial version of Hirsch's original argument was recently subjected to criticism. –  t.b. Aug 5 '12 at 12:09

Gödel's theorem was definitely a "wow" for me.

Also interesting, the proof around the non-Enumerability of $\mathbb{R}$.

In the same area, the Fact that $\mathbb{Q}$ is a dense subset of $\mathbb{R}$, despite the fact that $\mathbb{Q}$ is numerable while $\mathbb{R}$ is not. It kind of suggests that $n(\mathbb{Q}) = n(\mathbb{R}-\mathbb{Q})$ while at the same time $\mathbb{R}-\mathbb{Q}$ is infinitely bigger than $\mathbb{Q}$...

Church numerals if you're into computer science.

-
This has received several upvotes, so perhaps we should mention that some of these proofs have names. Gödel's theorem stands alone, but it's generally Cantor's Diagonalization argument that proves the uncountability of the reals and Dirichlet's Box Principle that proves that the rationals are dense in the reals. –  mixedmath Aug 6 '12 at 1:36

Here is one strategy for proving Fermat's Last Theorem: suppose you could show that $x^n + y^n = z^n$ has no nontrivial solutions ${}\bmod p$ for infinitely many primes $p$. Then any nontrivial solution over $\mathbb{Z}$ necessarily reduces to a nontrivial solution mod a sufficiently large prime, so you've proven FLT.

Unfortunately, this is false: for fixed $n$, the Fermat equation has nontrivial solutions ${}\bmod p$ for all sufficiently large primes $p$! This was first proven by Schur (I am told), and the proof uses Ramsey theory and very little actual number theory. I think this proof teaches the following valuable lessons:

• What seems like a problem in one field might be best thought of as a problem in another.
• Sometimes the way to solve a problem is to ignore a lot of its structure.
-
Issai Schur, “Über die Kongruenz $x + y\equiv z\pmod{p}$.” Jahresvericht der Deutschen Mathematiker-Vereinigung 1917, 114–117. digizeitschriften.de/dms/img/… –  Andres Caicedo Nov 18 '12 at 7:49

The Weyl Character formula is an excellent example of a deep result with a clever proof. The result states (in one form) that the irreducible characters of a compact, connected Lie group are parametrized uniquely by their heighest weight vectors! The intuition is that characters on a compact, connected Lie group $G$ are class functions on $G$ and their restrictions to a maximal torus of $G$ are $W$-invariant functions on $T$ where $W$ is the Weyl group of $T$. The $W$-invariance of a character on $T$ allows you to parametrize it by a heighest weight vector using the theory of roots and weights. However, the clever point of the proof is that one studies $W$-anti-invariant functions on $T$ rather than $W$-invariant functions on $T$! The quotient of two $W$-anti-invariant functions on $T$ is a $W$-invariant function on $T$. I think that this is a deep and extremely important result in mathematics with a clever proof.

-

The full classical proof of the classification theorem of compact surfaces has always been-and remains-one of my favorite proofs. Despite it's tediousness, it demonstrates to the beginner how important it is to be able to prove results constructively,using very little beyond the definitions of a surface and the fundamental group.

-
Agreed; also, Massey's text does a great job with this proof, imo! –  james Aug 11 '12 at 20:30
@james So does John Lee in his terrific INTRODUCTION TO TOPOLOGICAL MANIFOLDS. In fact,the version of the proof in the second edition is even nicer! –  Mathemagician1234 Aug 31 '12 at 22:40

I would have to include (at least) one of the proofs available for quadratic reciprocity. My personal preference would be for the proof due to Eisenstein presented in Ireland and Rosen, but there are so many others to choose from.

A second one I would include would be Minkowski's lattice point theorem, as proved in Hasse's "Number Theory".

-

Here is my favourite "wow" proof .

Theorem
There exist two positive irrational numbers $s,t$ such that $s^t$ is rational.
Proof
If $\sqrt2^\sqrt 2$ is rational, we may take $s=t=\sqrt 2$ .
If $\sqrt 2^\sqrt 2$ is irrational , we may take $s=\sqrt 2^\sqrt 2$ and $t=\sqrt 2$ since $(\sqrt 2^\sqrt 2)^\sqrt 2=(\sqrt 2)^ 2=2$.

-
Actually $\sqrt 2^\sqrt 2$ is irrational, but this is a hard result, not needed in the elementary proof above. –  Georges Elencwajg Aug 5 '12 at 8:10
This proof (together with some other related facts) is mentioned here and here. –  Martin Sleziak Aug 5 '12 at 10:04
Is this proof exist the other way around? like s and t irrational and s pow(1/t) is rational –  Nicolas Manzini Aug 6 '12 at 7:59
@NicolasManzini consider t = 1 / sqrt 2 –  Jimmy Aug 7 '12 at 0:31
Haha that is a pretty awesome proof –  ZafarS Jan 5 '13 at 0:41

.... and of course the neat proof that $$\int_{-\infty}^\infty e^{-x^2}\,dx=\sqrt{\pi}.$$

-
Agreed. I suppose you know the story that some mathematician was talking to Grothendieck, alluded to this formula, and it turned out that Grothendieck was of the opinion that he had never seen it before? –  Pete L. Clark Aug 5 '12 at 8:08
@PeteL.Clark : no, actually I didn't! :) It goes well together with the Grothendieck's prime (57?) anecdote. I believe that was Lord Kelvin to claim that how to compute the above integral had to be known by "everyone", but a quick Google search didn't produce any reference. –  Andrea Mori Aug 5 '12 at 8:21
This trick is attributed to Poisson. Interestingly, it is essentially the only integral that can be solved by this method. See unf.edu/~dbell/Poisson.pdf –  Gregor Bruns Aug 5 '12 at 15:09
Andrea: The quote that you're looking for is probably "A mathematician is one to whom that is as obvious as that twice two makes four is to you." –  Eric Stucky Aug 5 '12 at 20:21
@EricStucky My least favorite mathematical quote by some margin. Also, I never learned a reason why every mathematician should know this proof. –  user31373 Aug 5 '12 at 21:42

Cantor's Theorem: There is no surjection from $A$ onto $\mathcal P(A)$.

-
+1: For my entire adult life I have felt that this is the number one theorem and proof that every mathematician should know. The value of $\frac{\operatorname{bang}}{\operatorname{buck}}$ is simply off the charts. –  Pete L. Clark Aug 5 '12 at 13:46
My Russian analysis professor even gave a "Soviet Poli Sci" proof of this result in the first lecture. –  M Turgeon Aug 5 '12 at 16:08
@Pete Totally agree and that's why I refuse to give up until I can reproduce this result several ways on demand. I think I'm missing an enzyme or something in my neural pathways preventing it...... –  Mathemagician1234 Mar 16 '13 at 5:43
To remember the proof, the idea behind is diagonalisation process. Surprise! –  enoughsaid05 Mar 22 '13 at 15:08
When one of my professors proved this, he said: "You need to be able to write this prove in the snow with pee even at night when drunk" –  Laugerizor May 4 '13 at 0:42
show 1 more comment

Perhaps geometric and algebraic proofs of the fundamental theorem of calculus.

-
Where would one find those? –  Pedro Tamaroff Nov 18 '12 at 5:59
@PeterTamaroff en.wikipedia.org/wiki/… and en.wikipedia.org/wiki/… ? –  Argon Nov 18 '12 at 15:09

The proof of the Fundamental Theorem of Algebra via Liouville's theorem is short and sweet.

-
How about the Fundamental Theorem of Algebra via Gauss-Bonnet? Hehe –  Jesse Madnick Nov 18 '12 at 6:28
Ok,you HAVE to tell me how the heck to do THAT,Jesse.......... –  Mathemagician1234 Mar 23 '13 at 22:47
Hah, I like the homotopy theory proof, because you can give a hand-wavy proof to someone who does not know homotopy or any complex analysis. –  Thomas Andrews Jun 13 '13 at 16:20
I like (1) the algebraic proof that works over $R[i]$ for any real closed field $R$, (2) advanced calculus proofs which boil down to the fact the complex polynomials are open mappings, (3) algebraic topology proofs which involve homotopy invariance of degree. The Liouville proof I'm not as keen on because using the machinery of complex analysis feels more like nuking a mosquito to me. Guess tastes differ on this one. –  user43208 Oct 16 '13 at 13:54

As a beginner (and far from being a mathematician) there are two proofs that I have come across that I would say, for me, were "symphonic" capers of some areas of study - showing what can be done with material you've studied.

An additional point is that the actual presentation of the proofs themselves were instructive in their elegance. Sort of like a virtuoso performer.

The Stone-Weierstrass Theorem - Vaughan Jones https://sites.google.com/site/math104sp2011/lecture-notes

The Sylow Theorems - Benedict Gross http://www.extension.harvard.edu/open-learning-initiative/abstract-algebra

-

The ultrafilter proof of Tychonoff's theorem.

The proof is simple, show the power of working with filters and incorporats a good deal of what "everyone should know about compactness".

The strategy-stealing argument for why the first player can force a win in hex.

The argument is simple, elegant, clever and there is eesentially no effort in learning it.

The proof of Zorn's lemma by way of ordinals.

Too many people believe that Zorns lemma is an inherently incomprehensible black box. It is not.

Heine-Borel by "induction."

The argument is very neat and shows exactly where the completeness of $\mathbb{R}$ matters.

The visual argument for finding the area of a circle, given radius and circumference.

It's simply beautiful.

-
Reference for the first proof: qchu.wordpress.com/2010/12/09/ultrafilters-in-topology –  Qiaochu Yuan Aug 10 '12 at 0:50
+1 for some subtly sophisticated and original proofs of some very standard results that are not common knowledge among graduate students and up. They are also very good examples of why a comprehensive working knowledge of such taken-for-granted basics as point set topology, modern logic and axiomatic set theory can give some very powerful tools to the mathematican for new takes on old results. –  Mathemagician1234 Mar 16 '13 at 5:39

I personally believe some of the proofs of Pythagoras' theorem can be both beautiful and elegant, though it is unfortunate that it is not taught in school (at least as far as I am aware).

Take any square with sides of length $x+y$. Then $x$ units from each corner, connect to the next corner, again $x$ units away. Call this distance $z$. Therefore you have a square with side length $x+y$ with four triangles with base and height $x$ and $y$ and a smaller square in the middle with a side length of $z$.

$$(x+y)^2=4\frac{1}{2}xy+z^2$$ $$x^2+y^2+2xy-2xy=z^2$$ $$x^2+y^2=z^2$$

-
I'm not sure why this got downvoted so hard, since it hasn't been edited, and it gives an honest answer to the question. I can see people not agreeing with it, but… –  Eric Stucky Aug 7 '12 at 23:24
@EricStucky I can understand why it was downvoted as it was possibly a bit simplistic for the site, but believe that it is elegant, and unfortunate that (as far as I know from my friends) is not massively widely known. –  jClark94 Aug 8 '12 at 10:20
@Eric: I didn't downvote this answer, but...I believe the culture of downvoting answers to community wiki questions is a bit different than that of other questions. For an "ordinary" question one should downvote an answer only when there is something objectively incorrect there. For an answer to a cw question the general sentiment seems to be that you may downvote to indicate a difference of opinion or taste. In any case, one should take such downvotes less personally... –  Pete L. Clark Aug 9 '12 at 4:03
I actually don't really understand the difference between the "main site" and the community wiki; would you mind explaining (or an appropriate link)? –  Eric Stucky Aug 11 '12 at 3:19
@EricStucky As I understand it, CW questions have too many different answers (like this one), or several linked yet separate answers (such as a question on tikz libraries and their uses), so no definite answer can be given, or no "right" answer, such as a code golf question. I'm probably wrong, but if anyone can explain where I'm wrong in this theory, I'd be grateful –  jClark94 Aug 11 '12 at 18:10
show 1 more comment

It is propably not something which everybody should know, nevertheless it is simply beautiful!

The stable Hurewicz theorem using that the sphere spectrum is a compact generator of the stable homotopy category. In particular Serre's theorem that the rational stable homotpy groups of spheres are trivial for degrees bigger than 1.

-

$$2+2=4$$

Of course I am talking in the context of Peano Axioms (or some other reasonable theory of arithmetics).

Indeed most mathematicians could come up with the proof in a matter of minutes, after seeing the axioms, the trick of course is to understand what is there to prove here anyway?

We defined $+$ by induction. We denote by $2=S(1)$ and $4=S(S(S(1)))$. Now we need to prove that the terms $S(1)+S(1)$ and $S(S(S(1)))$ are equal, because there is no axiom tell us that directly.

-

When I did my first analysis course I found the proof the Lebesgue differentiation theorem using maximal functions and covering lemma arguments to be very beautiful.

-

I really like the simple and nice proof of the 5-color theorem (i.e. that for every planar graph there exists a vertex coloring with not more than 5 colors) and how surprisingly difficult it is to proof the sharper 4-color theorem.

-

Euclid's proof. Very simple, very elegant

Theorem

There are more primes than found in any finite list of primes.

Proof

Call the primes in our finite list $p_1, p_2, ..., p_r$. Let P be any common multiple of these primes plus one (for example, $P = p_1p_2...p_r+1$). Now P is either prime or it is not. If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p. Notice p can not be any of $p_1, p_2, ..., p_r$, otherwise p would divide 1, which is impossible. So this prime p is some prime that was not in our original list. Either way, the original list was incomplete.

-
This appeared on the list already. –  Asaf Karagila Mar 16 '13 at 0:33
@AsafKaragila Sorry, I didn't notice that. –  Occupy Gezi Mar 16 '13 at 0:55

My all time favorite proof?

Furstenberg's proof of the infinity of primes by point-set topology. I know, a lot people think it's not a big deal. I think:

a) It's an immensely clever way to use point set topology to prove a result in a seemingly unrelated field, namely number theory.

b) I used it as the beginnings of my first research in additive number theory; looking to generalize this result to create similar proofs of results for sumsets and arithmetic progressions. Sadly, my health failed again,but I hope to return to this research soon.

-