Read on Twitter
What are your favourite tweet-length mathematical proofs?
Here's a couple of mine.
Here's a couple of mine.
Infinitude of primes: suppose there are only finitely many, p1, p2...pn. Take the product & add 1 to define M := p1*p2*..*pn+1. Some thought shows M has no non-trivial divisors, thus is prime, but not on the original list, so there can't have been only finitely many primes. QED
e is irrational: suppose for a contradiction that it's not. Then e = 1 + 1/2! + 1/3! + ... = p / q for positive integers p & q. Multiply both side by q! & you see 1/(q+1) + 1/(q+1)(q+2)+... is an integer. But it's easily shown to be > 0 & < 1, a contradiction. QED
The halting problem is not decidable by any algorithm:
Suppose there is such an algorithm. Then the following is a valid algorithm, which when passed itself, halts iff it doesn't halt (for a contradiction)
def f(x):
if program x halts on input x: loop forever
else: stop
Suppose there is such an algorithm. Then the following is a valid algorithm, which when passed itself, halts iff it doesn't halt (for a contradiction)
def f(x):
if program x halts on input x: loop forever
else: stop
sqrt(2) is irrational:
Suppose sqrt(2) = p/q where p & q are integers. Square both sides & rearrange:
2 q^2 = p^2
The LHS has an odd number of prime factors, while the RHS has an even number, contradicting the uniqueness of the prime factorization. QED
Suppose sqrt(2) = p/q where p & q are integers. Square both sides & rearrange:
2 q^2 = p^2
The LHS has an odd number of prime factors, while the RHS has an even number, contradicting the uniqueness of the prime factorization. QED
Something I like about the last proof is that the same idea generalizes easily. E.g., suppose m & n are positive integers. Then the same idea shows the n'th root of m is irrational, unless m is an exact n'th power.
So the cube root of 17 is irrational, fourth root of 64 etc
So the cube root of 17 is irrational, fourth root of 64 etc
