What is your favorite proof?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

EstLladon
Beat you to the park. From RUSSIA.
Posts: 483
Joined: Tue Oct 17, 2006 10:23 am UTC

What is your favorite proof?

Postby EstLladon » Tue Mar 29, 2011 8:34 am UTC

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.
From Russia with math.

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: What is your favorite proof?

Postby mr-mitch » Tue Mar 29, 2011 9:10 am UTC

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.

User avatar
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?

Postby jestingrabbit » Tue Mar 29, 2011 10:26 am UTC

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.

greengiant
Posts: 272
Joined: Thu Jul 09, 2009 9:26 am UTC

Re: What is your favorite proof?

Postby greengiant » Tue Mar 29, 2011 10:30 am UTC

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.

MalachiConstant
Posts: 4
Joined: Fri Sep 24, 2010 3:58 pm UTC

Re: What is your favorite proof?

Postby MalachiConstant » Tue Mar 29, 2011 10:35 am UTC

I'm particularly partial to Archimedes' proof for the volume of a sphere. Cantor's diagonalization argument is a close second.

User avatar
mdyrud
Posts: 205
Joined: Fri Jun 13, 2008 10:34 pm UTC

Re: What is your favorite proof?

Postby mdyrud » Tue Mar 29, 2011 8:12 pm UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: What is your favorite proof?

Postby skeptical scientist » Tue Mar 29, 2011 8:28 pm UTC

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

User avatar
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?

Postby Yakk » Tue Mar 29, 2011 8:56 pm UTC

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.

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: What is your favorite proof?

Postby z4lis » Tue Mar 29, 2011 9:02 pm UTC

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.
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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: What is your favorite proof?

Postby skeptical scientist » Tue Mar 29, 2011 9:39 pm UTC

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

User avatar
Turtle_
Posts: 186
Joined: Mon Apr 14, 2008 10:27 pm UTC

Re: What is your favorite proof?

Postby Turtle_ » Wed Mar 30, 2011 12:57 am UTC

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

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: What is your favorite proof?

Postby Ankit1010 » Wed Mar 30, 2011 1:48 am UTC

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!

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: What is your favorite proof?

Postby Qaanol » Wed Mar 30, 2011 1:55 am UTC

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

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: What is your favorite proof?

Postby skeptical scientist » Wed Mar 30, 2011 3:27 am UTC

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

User avatar
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?

Postby jestingrabbit » Wed Mar 30, 2011 4:45 am UTC

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.

radams
Posts: 90
Joined: Fri May 14, 2010 12:49 pm UTC

Re: What is your favorite proof?

Postby radams » Wed Mar 30, 2011 10:00 am UTC

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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: What is your favorite proof?

Postby Qaanol » Wed Mar 30, 2011 10:11 am UTC

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”.
wee free kings

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: What is your favorite proof?

Postby skeptical scientist » Wed Mar 30, 2011 3:07 pm UTC

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.
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

User avatar
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?

Postby gmalivuk » Wed Mar 30, 2011 3:36 pm UTC

I love what my word filters have done to these discussions. :-)
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
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?

Postby jestingrabbit » Wed Mar 30, 2011 3:41 pm UTC

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

bbq
Posts: 186
Joined: Sat Dec 27, 2008 5:00 pm UTC

Re: What is your favorite proof?

Postby bbq » Wed Mar 30, 2011 4:27 pm UTC

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.
niinn.ininniinniininiini.n.iii...ininiiinnninnin.inn.niniininnnn.

Mere Accumulation Of Observational Evidence Does Not Constitute 'Proof'.

User avatar
Dason
Posts: 1309
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: What is your favorite proof?

Postby Dason » Wed Mar 30, 2011 4:50 pm UTC

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;

User avatar
Ivor Zozz
Posts: 169
Joined: Sun May 09, 2010 7:35 pm UTC

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

Postby Ivor Zozz » Wed Mar 30, 2011 7:37 pm UTC

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:

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

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

Postby skeptical scientist » Wed Mar 30, 2011 9:00 pm UTC

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.
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

User avatar
Dason
Posts: 1309
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

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

Postby Dason » Wed Mar 30, 2011 9:58 pm UTC

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;

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

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

Postby skeptical scientist » Wed Mar 30, 2011 10:15 pm UTC

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

JoshuaZ
Posts: 401
Joined: Tue Apr 24, 2007 1:18 am UTC
Contact:

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

Postby JoshuaZ » Thu Mar 31, 2011 12:49 am UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

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

Postby skeptical scientist » Thu Mar 31, 2011 1:17 am UTC

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.
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

JoshuaZ
Posts: 401
Joined: Tue Apr 24, 2007 1:18 am UTC
Contact:

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

Postby JoshuaZ » Thu Mar 31, 2011 4:39 am UTC

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.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

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

Postby WarDaft » Thu Mar 31, 2011 6:39 am UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

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

Postby skeptical scientist » Thu Mar 31, 2011 7:01 am UTC

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.
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

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

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

Postby WarDaft » Thu Mar 31, 2011 7:16 am UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

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

Postby skeptical scientist » Thu Mar 31, 2011 7:30 am UTC

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

greengiant
Posts: 272
Joined: Thu Jul 09, 2009 9:26 am UTC

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

Postby greengiant » Thu Mar 31, 2011 8:49 am UTC

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.).

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

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

Postby mr-mitch » Thu Mar 31, 2011 10:03 am UTC

The current word filters invalidate my proof there are infinite primes :cry:

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

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

Postby Mike_Bson » Thu Mar 31, 2011 10:14 am UTC

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).

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

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

Postby WarDaft » Thu Mar 31, 2011 11:16 am UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Eastwinn
Posts: 303
Joined: Thu Jun 19, 2008 12:36 am UTC
Location: Maryland

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

Postby Eastwinn » Sun Apr 03, 2011 10:45 pm UTC

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.

User avatar
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?

Postby Yakk » Mon Apr 04, 2011 4:52 am UTC

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.

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: What is your favorite proof?

Postby z4lis » Mon Apr 04, 2011 5:03 am UTC

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.
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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests