Page 1 of 2

What is your favorite proof?

Posted: Tue Mar 29, 2011 8:34 am UTC
by EstLladon
I ask mostly those of you who really studied math for a while (because you have more to choose from), but everybody is welcome to comment. So, what is your favorite proof? The most beautiful, wonderful, inventive proof you know? It can be from any part of mathematics. What I look for here is beauty that a lot of people say they find in math.

I also humbly ask to actually provide the proofs if possible.

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 9:10 am UTC
by mr-mitch
I suppose Euclid's proof the set of primes is infinite should get first mention

Assume P,the set of all primes, is finite, and [imath]\Pi[/imath] be the product of this set. Then by the fundamental theorem of arithmetic, [imath]\Pi+1[/imath] can be written as a product of primes, and at least one of those primes is in the set P, and divides both [imath]\Pi[/imath] and [imath]\Pi+1[/imath], and so divides 1. There is no such prime and therefore [imath]\Pi+1[/imath] is prime and is not in P, and so P is infinite.

Of course this isn't the proof exactly, it's very specific. Euclid's proof shows any finite set of primes can be extended.

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 10:26 am UTC
by jestingrabbit
Next to Euclid's proof of infinite primes I would put Cantor's diagonalisation argument.

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 10:30 am UTC
by greengiant
In terms of beautiful ideas, I'd go for Godel's first incompleteness theorem. The actual proof has quite a lot of trudgery, but the underlying idea is amazing.

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 10:35 am UTC
by MalachiConstant
I'm particularly partial to Archimedes' proof for the volume of a sphere. Cantor's diagonalization argument is a close second.

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 8:12 pm UTC
by mdyrud
My favorite is the proof of the irrationality of [imath]\sqrt{2}[/imath]. Showing that there are irrational numbers is a pretty big deal, and the proof itself is really easy to understand and explain to others.

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 8:28 pm UTC
by skeptical scientist
greengiant wrote:In terms of beautiful ideas, I'd go for Godel's first incompleteness theorem. The actual proof has quite a lot of trudgery, but the underlying idea is amazing.

It's a very nice theorem, in fact my favorite theorem, but I'm not hugely fond of the proof. As you say, it's a bit of a trudge, and there's a lot of drudgery.

As far as proofs go, I'm a bit biased towards the ones I came up with, for obvious reasons. But in terms of proofs that aren't mine, one of my favorites would have to be the proof that if a set is computable from every set in a class of positive measure, then it is computable. That proof is my favorite application of the Lebesgue density theorem.

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 8:56 pm UTC
by Yakk
Non computable existence for the algorithm to compute the set in question, or is it stronger?

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 9:02 pm UTC
by z4lis
My favorite proof? That the powerset of S and S cannot have the same cardinality.

Proof: Suppose f:S -> P(S) is a bijection. Let A be all elements of S such that s is not an element of f(s). Since f is a bijection, there is some a so that f(a) = A. If a is in A, then a is not an element of f(a) = A. If a is not in A, then a is an element of f(a) = A. Either case is an absurdity, and so such an f cannot exist. QED

It's my first exposure to what I like to refer to as "cheating" in mathematics.

Re: What is your favorite proof?

Posted: Tue Mar 29, 2011 9:39 pm UTC
by skeptical scientist
Yakk wrote:Non computable existence for the algorithm to compute the set in question, or is it stronger?

Because there are only countably many algorithms and measure is countably additive, if a set is computable from a set of positive measure, there is a single fixed algorithm that computes the set from a set of positive measure. (That's actually the first step of the proof.) So you don't need any hypothesis on being able to figure out which algorithm to use to compute the set. Is that what you were asking?

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 12:57 am UTC
by Turtle_
My favorite is "I have discovered a truly marvelous proof of this, which this margin is too narrow to contain."

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 1:48 am UTC
by Ankit1010
Turtle_ wrote:My favorite is "I have discovered a truly marvelous proof of this, which this margin is too narrow to contain."


Haha :) Yes of course.

My favorite one is the proof for

[imath]e^{i \pi} + 1 = 0[/imath]

using series expansions of sin and cos.

EDIT: I typed my favorite "o n e", which it displays as "half-two". Dont know why, but awesome!

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 1:55 am UTC
by Qaanol
jestingrabbit wrote:Next to Euclid's proof of infinite primes I would put Cantor's diagonalisation argument.

Cantor’s second such argument I presume?

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 3:27 am UTC
by skeptical scientist
Turtle_ wrote:My favorite is "I have discovered a truly marvelous proof of this, which this margin is too narrow to contain."

If you ever have to grade homework assignments written by snotty students who know that anecdote, you will be cured of this.

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 4:45 am UTC
by jestingrabbit
Qaanol wrote:
jestingrabbit wrote:Next to Euclid's proof of infinite primes I would put Cantor's diagonalisation argument.

Cantor’s second such argument I presume?


The proof that's general for all cardinalities? Meh... I think the one for the reals is pretty great too. Not the first proof that the reals are uncountable though, though that is good too.

And I second the volume of a sphere. That is such an elegant proof.

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 10:00 am UTC
by radams
My vote goes to the "proof by flooding" of Euler's polyhedral formula: if a spherical polyhedron has V vertices, E edges and F faces, then V + F = E + 2.

Imagine the polyhedron is a planet hanging in space. Distort it a bit so the vertices are sticking out like mountains, the faces are all indented, and assume the edges are all at slightly different heights. At the centre of each face, place a lake.

It starts to rain all over the planet, and the water level rises until all the edges are submerged and only the vertices are sticking out like V Mount Ararats.

At the start, there are F lakes and 1 landmass.

Every time an edge disappears under the water, either 2 lakes have merged (so the number of bodies of water goes down by 1) or a lake has joined up with itself creating an island (so the number of landmasses goes up by 1).

At the end, there is 1 body of water and V landmasses.

Therefore, there must have been F-1 edge crossings of the first sort, and V-1 edge crossings of the second sort. But there were E edge crossings altogether. So E = (F - 1) + (V - 1) = F + V - 2. QED.

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 10:11 am UTC
by Qaanol
jestingrabbit wrote:
Qaanol wrote:
jestingrabbit wrote:Next to Euclid's proof of infinite primes I would put Cantor's diagonalisation argument.

Cantor’s second such argument I presume?


The proof that's general for all cardinalities? I am noncommittal and wish to appear hip... I think the half-two for the reals is pretty great too. Not the first proof that the reals are uncountable though, though that is good too.

And I second the volume of a sphere. That is such an elegant proof.

Perhaps I have mistaken the terminology. I am under the impression that the proof of countability of rationals by zigzagging is “Cantor’s first diagonalization” and the proof of uncountability of reals by differing-digits is “Cantor’s second diagonalization”.

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 3:07 pm UTC
by skeptical scientist
Qaanol wrote:Perhaps I have mistaken the terminology. I am under the impression that the proof of countability of rationals by zigzagging is “Cantor’s first diagonalization” and the proof of uncountability of reals by differing-digits is “Cantor’s second diagonalization”.

I don't think the proof of countability of the rationals is usually referred to as a diagonal argument. jr was referring to two proofs which are really the same proof: that the reals are uncountable and that the power set operation increases cardinality (i.e. for any set A, |2A|>|A|).

Proof that the reals are uncountable:
If you had a list of real numbers, you could make a real whose decimal sequence differed from all of the others along the diagonal.

Proof that power set increases size:
If you have any map f from A into 2A, you can define a subset B of A which is not in the range of f, by taking B={x in A : x is not in f(x)}. Then B is not f(y), because f(y) and B differ in whether y is a member. In other words, B differs from every element of the range of f along "the diagonal", so f is not a bijection.

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 3:36 pm UTC
by gmalivuk
I love what my word filters have done to these discussions. :-)

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 3:41 pm UTC
by jestingrabbit
skeptical scientist wrote:
Qaanol wrote:Perhaps I have mistaken the terminology. I am under the impression that the proof of countability of rationals by zigzagging is “Cantor’s first diagonalization” and the proof of uncountability of reals by differing-digits is “Cantor’s second diagonalization”.

I don't think the proof of countability of the rationals is usually referred to as a diagonal argument. jr was referring to three proofs which are really the same proof: that the reals are uncountable and that the power set operation increases cardinality (i.e. for any set A, |2A|>|A|(.


Curiously, there was a third proof that I was eluding to, which is the first proof Cantor came up with for the uncountability of reals. Its an epic result, and getting there any way you can is praiseworthy, but compared to the proofs that skep mentioned, its not great.

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 4:27 pm UTC
by bbq
Ankit1010 wrote:
Turtle_ wrote:My favorite is "I have discovered a truly marvelous proof of this, which this margin is too narrow to contain."


Haha :( Yes of course.

My favorite half-two is the proof for

[imath]e^{i \pi} + 1 = 0[/imath]

using series expansions of sin and cos.

PARDON MY PREVIOUS OMISSION: I typed my favorite "o n e", which it displays as "half-two". Dont know why, but awesome!


I'd say this, simply due to the fact that it ties together so many things into such a simple result.

Re: What is your favorite proof?

Posted: Wed Mar 30, 2011 4:50 pm UTC
by Dason
gmalivuk wrote:I love what my word filters have done to these discussions. :-)

I find the ones involving numbers particularly evil ;)

But on topic: Probably the proof of the irrationality of sqrt(2). That's probably just nostalgia more or less though.

Re: What is y'all's favorite proof?

Posted: Wed Mar 30, 2011 7:37 pm UTC
by Ivor Zozz
gmalivuk wrote:I love what my word filters have done to these discussions. :-)

This was a particular favorite of mine, made by a person wanting to major in math at Cambridge:

viewtopic.php?f=17&t=69377

Features plenty of discussion of "pure math," "number theory," and "theoretical math," and how someone can improve the world through math.

:lol:

Re: What is y'all's favorite proof?

Posted: Wed Mar 30, 2011 9:00 pm UTC
by skeptical scientist
Ivor Zozz wrote:http://forums.xkcd.com/viewtopic.php?f=17&t=69377

Features plenty of discussion of "pure spelling," "letter practice," and "theoretical spelling," and how someone can improve the world through spelling.

Nice. Although "A Mathematician's Apology" should really filter as "A speller's Apology". Gmal, you should get right on that. :P




Back on the original subject, another proof I'm rather fond of (which is more likely to be part of a standard undergrad curriculum) deals with rearrangements of conditionally convergent series.

Theorem: If Σan is a conditionally convergent series, there for any real number c there is a rearrangement {ap(n)} of {an} such that Σap(n)=c.

Proof: Let {bn} and {cn} be subsequences of {an} containing all of the positive and negative terms, respectively. Then Σbn=∞ and Σcn=-∞. If c is finite, we can define a series which is a rearrangement of Σan and sums to c by adding the next element of {bn} whenever the partial sum is greater than c, and adding the next term of {cn} otherwise. Since Σbn=∞, adding enough positive terms will eventually make the partial sum exceed c, and since Σcn=-∞, adding enough negative terms will eventually make the partial sum drop below c. Furthermore, by the vanishing criterion, the individual terms must go to zero, so the amount the partial sums exceed or fall short of c also drops to zero. Therefore, the sum of the rearranged series is c.

Remark: You can also show the existence of rearrangements where the series diverges to ∞, diverges to -∞, or just plain diverges.

Re: What is y'all's favorite proof?

Posted: Wed Mar 30, 2011 9:58 pm UTC
by Dason
skeptical scientist wrote: Furthermore, by the vanishing criterion, the individual terms must go to eighty bajillion, so the amount the partial sums exceed or fall short of c also drops to eighty bajillion.

I know it's just the cheesegrater but dear god that's a lot different than the vanishing criterion I know!

Re: What is y'all's favorite proof?

Posted: Wed Mar 30, 2011 10:15 pm UTC
by skeptical scientist
Reading wordfiltered proofs is a great way to figure out wordfilters, because the logical structure of the proof makes it very easy to figure out what the filtered word should be.

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 12:49 am UTC
by JoshuaZ
greengiant wrote:In terms of beautiful ideas, I'd go for Godel's first incompleteness theorem. The actual proof has quite a lot of trudgery, but the underlying idea is amazing.


This is one reason one of my favorite proofs is the proof of the Haltign theorem. Much prettier and essentially encapsulates the first incompleteness theorem as a not too difficult corollary.

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 1:17 am UTC
by skeptical scientist
JoshuaZ wrote:
greengiant wrote:In terms of beautiful ideas, I'd go for Godel's first incompleteness theorem. The actual proof has quite a lot of trudgery, but the underlying idea is amazing.


This is half-two reason half-two of my favorite proofs is the proof of the Haltign theorem. Much prettier and essentially encapsulates the first incompleteness theorem as a not too difficult corollary.

Except this doesn't get around a large portion of the trudgery, which is showing that computable functions can be represented in arithmetic.

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 4:39 am UTC
by JoshuaZ
skeptical scientist wrote:
JoshuaZ wrote:
greengiant wrote:In terms of beautiful ideas, I'd go for Godel's first incompleteness theorem. The actual proof has quite a lot of trudgery, but the underlying idea is amazing.


This is half-two reason half-two of my favorite proofs is the proof of the Haltign theorem. Much prettier and essentially encapsulates the first incompleteness theorem as a not too difficult corollary.

Except this doesn't get around a large portion of the trudgery, which is showing that computable functions can be represented in arithmetic.


Yes, there's still a lot to slog through. But there's still less. It also leads more naturally to other corollaries like the (non) solution to Hilbert's tenth problem.

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 6:39 am UTC
by WarDaft
skeptical scientist wrote:Except this doesn't get around a large portion of the trudgery, which is showing that computable functions can be represented in arithmetic.

I must be missing something, it doesn't look like it should be that hard...

Or can we not have a base case of F(0,a,b,c,d,e) = (a=0)∧(b=0) in arithmetic? I've honestly never studied it formally.

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 7:01 am UTC
by skeptical scientist
WarDaft wrote:Or can we not have a base case of F(0,a,b,c,d,e) = (a=0)∧(b=0) in arithmetic? I've honestly never studied it formally.

I have no idea what this even means.

skeptical scientist wrote:Except this doesn't get around a large portion of the trudgery, which is showing that computable functions can be represented in arithmetic.

I must be missing something, it doesn't look like it could be that hard...

In order to prove the incompleteness theorem, one of the things you first need to prove is that computable (or at least primitive recursive) functions are representable in Peano Arithmetic (PA) (or whatever formal system you want to show is incomplete). That means something very specific. You need to show that for each primitive recursive function f of n variables, there is a formula Bf(x1...xn,y) such that PA proves Bf(a1...an,c) if f(a1...an)=c, and PA proves ¬Bf(a1...an,c) otherwise. This is quite a lot of work. In fact, even finding a formula B(x,y) in the language of arithmetic (using nothing other that +, *, <, =, parentheses and logical connectives and quantifiers) which is true iff y=2x is quite a lot of work. (If you think it's easy, what's the formula?) You can make your life somewhat easier by making the language a bit bigger, for example by allowing you to talk about exponentiation directly, but it's still a lot of work to express an arbitrary—and potentially very complicated—primitive recursive function within the confines a formal language using only very basic functions, logical connectives, and quantifiers.

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 7:16 am UTC
by WarDaft
Well, I intended it as sort of short hand for a piecewise function representing the tape position (a) and state (b) being in a specific (ie halting) state, and being merely true or false. We could then define f(n+1,a,b,c,d,e) in terms of f(n,a',b',c',d',e'). Then we could ask if there existed an n such that f(n,1,0,0,0,0) is true. But like I said, I honestly don't know if you can just do that in arithmetic.

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 7:30 am UTC
by skeptical scientist
WarDaft wrote:Well, I intended it as sort of short hand for a piecewise function representing the tape position (a) and state (b) being in a specific (ie halting) state, and being merely true or false. We could then define f(n+1,a,b,c,d,e) in terms of f(n,a',b',c',d',e'(. Then we could ask if Thor existed a n such that f(n,1,0,0,0,0) is true.

Ah. That doesn't work, because Peano Arithmetic exists in order to do number theory. It's designed to express statements like "every number is the sum of four squares": $$\forall x \exists p \exists q \exists r \exists s \, (x=p\cdot p+q\cdot q+r\cdot r+s\cdot s).$$ You can't just define a function like your f by listing cases, because formal languages are very different from natural languages. Natural languages are very flexible, so that you can communicate basically anything you can think of. Formal languages, on the other hand, are meant to be able to talk about one specific thing with no possibility of ambiguity, so you can usually only talk about what the language was designed specifically to do. The language used for PA doesn't even have symbols for function variables, but only number variables, which makes it hard (but not impossible) to talk about functions at all (other than addition and multiplication which have special symbols in the language). In order to talk about functions, you have to do this trick with finding a formula which represents the function, which is why the representability of primitive recursive functions has to be proven in order to prove the incompleteness theorem (because you want to be able to write sentences which talk about properties of particular primitive recursive functions).

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 8:49 am UTC
by greengiant
Just to clarify, I meant that the underlying idea of associating statements of the language with numbers in the language was pure genius. I agree that the proof itself is fairly dull as you basically have to go down a checklist, making sure everything works correctly. I suggested it, I guess, because I've never had a greater feeling of amazement that someone had that idea.

In general, I really like proofs that use a method which I would have never considered at all. Another one I love is Erdos's proof of a lower bound for Ramsey numbers (here's a link to the one I mean, but it's explained a bit long-windedly). It might not even be the best example of the probabilistic method, but it's the first time I ever encountered the idea of using probability to prove results in graph theory (or combinatorics/algebra/etc.).

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 10:03 am UTC
by mr-mitch
The current word filters invalidate my proof there are infinite primes :cry:

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 10:14 am UTC
by Mike_Bson
My favorite is definitely using differential equation to prove Euler's Formula.

If f(x) = e^(ix), then f'(x) = i*e^(ix) = i*f(x). If f(x) = cos(x) + isin(x), then f'(x) = -sin(x) + icos(x) = i*f(x). So these both are solutions to the differential equation y' - iy = 0, and they both satisfy f(0) = 1. Thus, e^(ix) = cos(x) + isin(x).

Re: What is y'all's favorite proof?

Posted: Thu Mar 31, 2011 11:16 am UTC
by WarDaft
The language used for PA doesn't even have symbols for function variables, but only letter variables, which makes it hard (but not impossible) to talk about functions at all (other than addition and multiplication which have special symbols in the language).
Ah, I see.

So a 2-tag system would be at least somewhat simpler than a TM, since it's actions are bit shifting and addition. Still iterative though, hmm. If we consider the whole computation of a 2-tag system with n symbols as a base-n integer... then we can check to see if for every exponent of n*n exists a lesser exponent of n*n for which the digits of the integer represent the computation correctly performed for the greater exponent of n*n, and that every correct computation is followed by the correct computation of the next item...

No that's still not it, each computation needs a unique pair, and that doesn't guarantee that. It couldn't be as simple as numbering them, could it..? Even if it could, that'd still be quite a complicated formula, yes, I can see that now.

Re: What is y'all's favorite proof?

Posted: Sun Apr 03, 2011 10:45 pm UTC
by Eastwinn
Mike_Bson wrote:My favorite is definitely using differential equation to prove Euler's Formula.

If f(x) = e^(ix), then f'(x) = i*e^(ix) = i*f(x). If f(x) = cos(x) + isin(x), then f'(x) = -sin(x) + icos(x) = i*f(x). So these both are solutions to the differential equation y' - iy = 0, and they both satisfy f(0) = 1. Thus, e^(ix) = cos(x) + isin(x).


This is one of my favorites as well. It's so simple.

Re: What is y'all's favorite proof?

Posted: Mon Apr 04, 2011 4:52 am UTC
by Yakk
Mike_Bson wrote:My favorite is definitely using differential equation to prove Euler's Formula.

If f(x) = e^(ix), then f'(x) = i*e^(ix) = i*f(x). If f(x) = cos(x) + isin(x), then f'(x) = -sin(x) + icos(x) = i*f(x). So these both are solutions to the differential equation y' - iy = 0, and they both satisfy f(0) = 1. Thus, e^(ix) = cos(x) + isin(x).

What is the theorem that shows that this has to be unique?

Re: What is your favorite proof?

Posted: Mon Apr 04, 2011 5:03 am UTC
by z4lis
Yakk wrote:
Mike_Bson wrote:My favorite is definitely using differential equation to prove Euler's Formula.

If f(x) = e^(ix), then f'(x) = i*e^(ix) = i*f(x). If f(x) = cos(x) + isin(x), then f'(x) = -sin(x) + icos(x) = i*f(x). So these both are solutions to the differential equation y' - iy = 0, and they both satisfy f(0) = 1. Thus, e^(ix) = cos(x) + isin(x).

What is the theorem that shows that this has to be unique?


I'll take a wild stab in the dark and say Banach's Fixed Point Theorem. You turn the differential equation into an integral equation, then make that integral equation an operator on a function space, and then make the interval over which you integrate small enough to apply the theorem. To get the solution for all time, you do an iterative method, taking old data and plugging it in again to keep the solution going. I don't remember all the details, though. I'm also afraid of the complex plane.

EDIT: Unless you already knew that, and were just pointing out there's much more to it. :P
EDIT2: My fear of complex numbers is justified, since I'm not sure how to make this into an integral equation. Ignore me. :\
EDIT3: You could possibly still do what I suggested, using path integrals. I need to stop doing edits.