More on proofs

[ciphergoth]

Some really interesting answers on what proofs you know. The most common proofs people mention are the ones I name, plus Cantor's diagonalisation argument that |R| > |N| - cool. More specific comments follow.

wildbadger -- product of two compact spaces is compact

A strong opening! I looked it up and found Tychonoff's Theorem - looks interesting.

cryptodragon -- A number of them from crypto stuff

Interesting, name us a favourite?

simple_epiphany -- As a third-year maths student, I'm required to know quite a lot of them, but the one for the Bolzano-Weierstrass theorem is quite nice.

Bolzano–Weierstrass theorem on Wikipedia. I think I could remember that proof. Cool, thanks!

aegidian -- Cantor's Diagonalisation, proving there are as many rational numbers as there are integers.

Ah, the proof that |Q| = |N| rather than the proof that |R| > |N|?

olethros -- Maybe I lied. I can prove (by recursion) that all marbles in the world are the same colour.

I know that proof :-) Oh go on, there must be a *valid* proof you like!

keirf -- Bolzano-Weierstrass theorem - every bounded sequence in R{n} has a convergent subsequence

A second showing for this theorem!

ajva -- that 0.999...=1

Don't you need to get into the construction of the real numbers to explain this one?

ergotia -- The infinite number of primes/hotel at the end of the universe one

Two proofs for the price of one :-)

nikolasco -- irrationality of sqrt(2) (fundamental theorem of arithmetic, even/odd, well-ordered)

What proofs are you referring to with "even/odd, well-ordered"?

Thanks all, please keep commenting :-)

Comments

[keirf.livejournal.com]

Following some of these links I rediscovered the delightfully named pointless topology.

Even/odd reminds me....

[akicif.livejournal.com]

I like the set in A Random Walk in Science: that not only did Alexander the Great have an infinite number of limbs but so did his non-existent horse....

[damerell.livejournal.com]

Of course the best proof of all is that e ^ (i pi) == -1 but I'd need to brush up on that one and there is too much meat on it for a party, assuming my other partygoer doesn't have a relevant background.

[makyo.livejournal.com]

You can prove e^iθ = cosθ + isinθ using Taylor–Maclaurin series (as long as you assume that the series converge everywhere in the complex plane - which I believe they do, but it's a while since I've done any complex analysis). Then set θ=π to get the special case e^iπ=-1.

[nikolasco.livejournal.com]

Wikipedia has a few proofs (http://en.wikipedia.org/wiki/Euler%27s_formula#Proofs), including the one makyo alluded to.

[olethros.livejournal.com]

Just because it's wrong doesn't mean it's not valid!!

Anyway, it's a hell of a lot more valid than the proof of "horses have an infinite number of legs."

[akicif.livejournal.com]

But that'd be a horse of another colour, which we've already proved doesn't exist (by analogy with marbles).

[drdoug.livejournal.com]

I got in to diagonalisation proofs when, in quick succession, my brother explained Cantor's diagonal argument and I read Hofstadter's GEB (or something else - but think it was GEB) with a diagonalisation proof of the halting problem. Many long years' lack of use means I cannot now recall what any of them actually proved (bar those two) ... and I'm sufficiently hazy about the halting problem one that I would never attempt it in public without practicing first.

I'm not usually a big fan of fake proofs, but I do like the juxtaposition of the 'proof that all positive integers are interesting', and the counter-argument, 'proof that all positive integers are boring'.

[simont]

You don't need the real numbers at all to show that 0.999... = 1, because it's true in the rationals as well!

0.999... is defined as the sum to infinity of 9/10 + 9/100 + 9/1000 + ..., and you can show just by summing geometric progressions that that's equal to 9/10 × 1/(1-1/10) = 9/10 × 10/9 = 1.

A proof without so much notation, but which follows the same line of argument and is in fact rigorous in spite of looking like one of those facile non-proofs, is to say: suppose x = 0.999... . Then 10x = 9.999... . Subtract the former from the latter to get 9x = 9, whence x = 1.

[ajva.livejournal.com]

Yes, the latter is my proof for non-mathmos, and therefore parties.

I'm not sure why, but I tend to find that conversation about Cauchy sequences and so on has the most extraordinary power to empty non-mathematicians' glasses such that after about two minutes they all mysteriously require re-filling in the kitchen.

[marnanel.livejournal.com]

"But it MUST be a different number! It's written differently!"

"Okay, subtract 0.999 from one. What's the answer?"

"Z..."

"Aha!"

"Er. The next real number after zero. See, got you."

"But there is no such number."

"Who says?"

et cetera.

The most comments I ever got on an LJ post, something like seventy of them, was by people attempting to disprove this when I asserted it in the course of talking about something else.

[emarkienna.livejournal.com]

"Okay, subtract 0.999 from one. What's the answer?"

"Z..."

I love it when they reply "0.0000 ... 1"

[valkyriekaren.livejournal.com]

And that's not the answer because...?

[ciphergoth.livejournal.com]

Because there's nowhere to put the "1". Every decimal place has to be at some numbered position; there are no extra places "at infinity", even though there are infinitely many places.

[marnanel.livejournal.com]

I try to tell people "you're asking for an infinite number of zeros and then a one. Have you considered what 'infinite' means and the problems in following it with 'and then'?"

[ciphergoth.livejournal.com]

You could do that just fine if you index the decimal places with something like 2ω instead of the natural numbers - I think this gives you the dual numbers (actually not quite but I think you can get there with some extra tweaking). We do have number spaces that have some of the behaviours people expect of the reals here, but the ordinary reals are not they.

[emarkienna.livejournal.com]

What ciphergoth said. Or to put it another way, "0.9..." or "0.9 recurring" [*] has a specific mathematic definition (an infinite sum), but "0.0...1" does not - and whenever I ask such a person for its definition, they are unable to provide one.

(Just to clarify - I don't mean to mock people who don't see that 0.9recurring = 1 - after all, the rigorous proof is rather high level, and the "simple proofs" aren't really rigorous. I mean more that the issue tends to attract some people who insist they are right, but are unable to either justify it, or find a fault in the proof that shows they are equal. I think it's a bit like the evolution of the mathematical world, except not with all the political and religious dispute.)

[*] I think one of the points that causes misunderstanding is the use of "...", which probably gets misunderstood as simply meaning "a lot of 9s". I'd prefer to use the notation of putting a dot or bar over the 9, but of course that's not so easy when writing online...

[ciphergoth.livejournal.com]

Nice analogy - there's a huge difference between "I don't understand how this feature evolved and I'd like to, it seems counter to my intuition because..." and "This seems counter to my intuition so EVILUTION IS A LIE!"

[elsmi.livejournal.com]

I tend to feel like arguing about 0.999... is a bit of a cheat, because really it isn't so much that the rigorous proof is obscure, it's that the *rigorous definition* is obscure. And then I feel like I'm telling people "ah-hah, you are wrong, because I am using a different definition than you! And normally switching around definitions is not a valid rhetorical technique, but it is valid in this case because this is Maths, which you were taught in school is the incomprehensible domain of people who know the secret code, which I do! So you must trust me!"

*cough* Right, err, I'll go lay down for a bit.

[battlekitty.livejournal.com]

I remember the second one. It makes maths geeks splutter *grin*

[johncoxon.livejournal.com]

Just a physicist, but I like the proof for the infinite number of prime numbers the best. It's very elegant and simple.

Isn't the proof that 0.9999... = 1 just as simple as saying 1/3 = 0.3333... and thus 1 = 3/3 = 3 * 0.3333... = 0.9999...? Or am I showing my ignorance?

[marnanel.livejournal.com]

Just a physicist, but I like the proof for the infinite number of prime numbers the best. It's very elegant and simple.

I explained this to a ten-year-old the other day and she understood it immediately.

[ciphergoth.livejournal.com]

No, it's just that...

well actually the proof is simpler than that, as marnanel points out. The trouble with all the proofs discussed here is that none of them really tackle the source of the confusion, and I'm not sure how you do that without talking about the construction of the reals.

[seph-hazard.livejournal.com]

Oh oh oh! I lied! I do know a proof, the same one as ergotia, because you taught it to me and I actually understood it and I can still remember it! [grin] (I think I forgot that it counted as a proper proof, because I can understand it and therefore it doesn't count. The workings of my brain never cease to amaze me.)

Irrationality of sqrt(2)

[nikolasco.livejournal.com]

Hopefully I wrote these without errors:

even/odd:

1. sqrt(2) = p/q for some integers p and q that are relatively prime (i.e. smallest reduced form)
2. 2 = p²/q²
3. p² = 2q²
4. note: p is clearly even, so q must be odd (by our premise)
5. note that the square of an even integer must be of the form 4k for some integer k . So, we can substitute: 4k = 2q²
6. 2k = q² , clearly q is even as well (contradiction)

well-ordering:

1. sqrt(2)*q = p for some integers p and q . w.l.o.g. let q by the smallest such integer
2. note that 1 < sqrt(2) < 2
3. so: sqrt(2) - 1 < 1
4. multiply both sides by q: (sqrt(2) - 1)*q < q
5. distribute: sqrt(2)*q - q
6. let: sqrt(2)*q - q = s where s is an integer
7. s*sqrt(2) is also an integer:
   1. s*sqrt(2) = (sqrt(2)*q - q)*sqrt(2)
   2. distribute: s*sqrt(2) = sqrt(2)*q*sqrt(2) - q*sqrt(2)
   3. simplify: s*sqrt(2) = 2*q - q*sqrt(2)
   4. substitute: s*sqrt(2) = 2*q - p
8. So s is both smaller than q and s*sqrt(2) is an integer. This violates our assumption that q was the smallest such integer.

Re: Irrationality of sqrt(2)

[ciphergoth.livejournal.com]

Ah, I misunderstood what you were saying - I had thought you were listing four different things you knew proofs for, but you were referring to three different proofs of that one thing that so troubled Pythagoras. Thanks! I didn't know that last one, it's neat.

[emarkienna.livejournal.com]

Your post left me thinking how it's been years since I had to rigorously prove anything, and how much of that I've forgotten off by heart.

Cantor's diagonal proof is the first one I remember coming across that both showed a very amazing result, and seemed a clever yet simple way to prove it.

I thought of 0.9recurring = 1 (the one that involves showing that the limit of 1/10^n is 0). That's certainly a classic for Internet forums to draw out the people who think they are experts at maths, but refuse to accept any proof you throw at them (Wikipedia has a whole sub-page dedicated to it, to stop people cluttering up the talk page...) But then I realised I was struggling to remember how to do all of it.

Bolzano-Weierstrass theorem is one of the few proofs I remember the name of (I remember my tutor's advice for exams was "It doesn't matter if you can't remember the name of the theorem you are going to use, just write 'By a theorem ...'"), but I'm long past remembering the proof. Or how to spell it.

I also liked the proof of the mean value theorem, as it seems like you're just proving the bleeding obvious - but then from that it's less work to get to proving l'Hopital's rule, which isn't at all obvious and is very useful indeed. Well, I liked the idea, but ISTR I hated actually having to prove it.

[djm4]

It may amuse you to know that I spent about two hours yesterday while coming down off the anaesthetic trying to prove that root 2 is irrational. I got there eventually after many blind alleys, and took it as a sign that the anaesthetic had finally worn off (I know the basic shape of the proof well, but my mind refused to make the right connections for ages.)

[ergotia.livejournal.com]

OK, 99% of this is going over my head now, but I am still getting some fun out of it.....I keep imaginimng a party with a blackboard the size of an asteroid and a geek proving Fermat's last theorem on it :)

[elsmi.livejournal.com]

> product of two compact spaces is compact
> A strong opening! I looked it up and found Tychonoff's Theorem - looks interesting.

Beware! Those are not the same! The former is elementary, the latter is equivalent to the axiom of choice!

Because... that might... be really important. Someday. That you not mix those up. You know.

The diagonalization proof of the Halting Problem that someone mentioned up above is truly beautiful, much better than the classic diagonalization results *or* Goedel's first incompleteness theorem. I mostly put that generalized diagonalization theorem as my answer because it has some personal significance.

It might be fun to talk about favorite results, too. Of the top of my head, Stone-Weierstrass comes to mind (the proof is boring and technical, but the result is so neat! I hadn't thought of it in years but the Bolzano-Weierstrass stuff reminded me), or the curious embedding properties of the Cantor set. (That dude just keeps popping up...)

[ciphergoth.livejournal.com]

Ah, yes, the Wikipedia article cautions that product-of-two is a lot more straightforward than general product.

More proofs

[(Anonymous)]

(You don't know me, but I came across this, and I can't help but reply; and hopefully with a couple interesting ones.) As someone who did a degree in maths, I could hopefully do quite a few. But the two I *like* (of the ones not previously mentioned) are:

• Construction by straightedge and compass giving algebraic extensions of degree power-of-2, and then proving the non-constructibility of certain numbers, giving you three unproven-for-thousands-of-years theorems at once: The Impossibility of Doubling the Cube (http://en.wikipedia.org/wiki/Doubling_the_cube), Trisecting the Angle (http://en.wikipedia.org/wiki/Trisecting_the_angle), and Squaring the Circle (http://en.wikipedia.org/wiki/Squaring_the_circle). (More (http://en.wikipedia.org/wiki/Constructible_number))
  
  
• Not-Burnside's Lemma (http://en.wikipedia.org/wiki/Burnside's_lemma). I don't know why, but I love this theorem. (And it's got the interesting weirdness with its name. See the "History" section.)
  

Re: More proofs

[ciphergoth.livejournal.com]

Funnily enough, I was looking at that the other day - in fact, you could check if the bit I added that says "the constructible numbers form the smallest field extension of the rational numbers which is closed under square root and complex conjugation" is correct!

BTW, anonymous posts are welcome but please sign with a nym!!

Re: More proofs

[insipidia.myopenid.com (from livejournal.com)]

To be honest, I can't really check that, since I haven't done any abstract algebra in 6 or 7 years. :) But it does *sound* right. (If it's clear to the reader that when you say "smallest", you mean "any other such field contains this one".) I can't think of a counterexample, anyway; although I am really rusty.

(Oh, and sorry about the anonymity. I don't use my LJ account any more, and I always forget that LJ accepts OpenID now. Old habits die hard. :) )
(Oh, and also sorry about that first badly formatted comment. I thought links were preserved properly.)