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

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.