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.

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

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

[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?

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

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

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