What is your favorite proof?
Moderators: gmalivuk, Moderators General, Prelates
What is your favorite proof?
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.
I also humbly ask to actually provide the proofs if possible.
From Russia with math.
Re: What is your favorite proof?
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.
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.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: What is your favorite proof?
Next to Euclid's proof of infinite primes I would put Cantor's diagonalisation argument.
Last edited by jestingrabbit on Tue Mar 29, 2011 11:27 am UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 272
 Joined: Thu Jul 09, 2009 9:26 am UTC
Re: What is your favorite proof?
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.

 Posts: 4
 Joined: Fri Sep 24, 2010 3:58 pm UTC
Re: What is your favorite proof?
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?
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.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is your favorite proof?
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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 Yakk
 Poster with most posts but no title.
 Posts: 11083
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: What is your favorite proof?
Non computable existence for the algorithm to compute the set in question, or is it stronger?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: What is your favorite proof?
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.
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.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is your favorite proof?
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?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: What is your favorite proof?
My favorite is "I have discovered a truly marvelous proof of this, which this margin is too narrow to contain."
"Sometimes lies were more dependable than the truth." ~ Ender's Game
"Ignorance more frequently begets confidence than does knowledge." ~ Charles Darwin
"Ignorance more frequently begets confidence than does knowledge." ~ Charles Darwin
Re: What is your favorite proof?
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 "halftwo". Dont know why, but awesome!
Re: What is your favorite proof?
jestingrabbit wrote:Next to Euclid's proof of infinite primes I would put Cantor's diagonalisation argument.
Cantor’s second such argument I presume?
wee free kings
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is your favorite proof?
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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: What is your favorite proof?
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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: What is your favorite proof?
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 F1 edge crossings of the first sort, and V1 edge crossings of the second sort. But there were E edge crossings altogether. So E = (F  1) + (V  1) = F + V  2. QED.
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 F1 edge crossings of the first sort, and V1 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?
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 halftwo 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 differingdigits is “Cantor’s second diagonalization”.
wee free kings
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is your favorite proof?
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 differingdigits 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, 2^{A}>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 2^{A}, 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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 gmalivuk
 GNU Terry Pratchett
 Posts: 26453
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: What is your favorite proof?
I love what my word filters have done to these discussions.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: What is your favorite proof?
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 differingdigits 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, 2^{A}>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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: What is your favorite proof?
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 halftwo 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 "halftwo". 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.
niinn.ininniinniininiini.n.iii...ininiiinnninnin.inn.niniininnnn.
Mere Accumulation Of Observational Evidence Does Not Constitute 'Proof'.
Mere Accumulation Of Observational Evidence Does Not Constitute 'Proof'.
Re: What is your favorite proof?
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.
double epsilon = .0000001;
Re: What is y'all's favorite proof?
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.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is y'all's favorite proof?
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.
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 Σa_{n} is a conditionally convergent series, there for any real number c there is a rearrangement {a_{p(n)}} of {a_{n}} such that Σa_{p(n)}=c.
Proof: Let {b_{n}} and {c_{n}} be subsequences of {a_{n}} containing all of the positive and negative terms, respectively. Then Σb_{n}=∞ and Σc_{n}=∞. If c is finite, we can define a series which is a rearrangement of Σa_{n} and sums to c by adding the next element of {b_{n}} whenever the partial sum is greater than c, and adding the next term of {c_{n}} otherwise. Since Σb_{n}=∞, adding enough positive terms will eventually make the partial sum exceed c, and since Σc_{n}=∞, 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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: What is y'all's favorite proof?
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!
double epsilon = .0000001;
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is y'all's favorite proof?
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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: What is y'all's favorite proof?
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.
Religion, Sets, and Politics (my blog)
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is y'all's favorite proof?
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 halftwo reason halftwo 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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: What is y'all's favorite proof?
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 halftwo reason halftwo 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.
Religion, Sets, and Politics (my blog)
Re: What is y'all's favorite proof?
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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is y'all's favorite proof?
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 B^{f}(x_{1}...x_{n},y) such that PA proves B^{f}(a_{1}...a_{n},c) if f(a_{1}...a_{n})=c, and PA proves ¬B^{f}(a_{1}...a_{n},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=2^{x} 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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: What is y'all's favorite proof?
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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: What is y'all's favorite proof?
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).
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson

 Posts: 272
 Joined: Thu Jul 09, 2009 9:26 am UTC
Re: What is y'all's favorite proof?
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 longwindedly). 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.).
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 longwindedly). 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?
The current word filters invalidate my proof there are infinite primes
Re: What is y'all's favorite proof?
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).
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?
Ah, I see.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).
So a 2tag 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 2tag system with n symbols as a basen 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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: What is y'all's favorite proof?
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.
http://aselliedraws.tumblr.com/  surreal sketches and characters.
 Yakk
 Poster with most posts but no title.
 Posts: 11083
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: What is y'all's favorite proof?
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?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: What is your favorite proof?
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.
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.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.
Who is online
Users browsing this forum: No registered users and 8 guests