Read on Twitter
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& #39;t have been only finitely many primes. QED
e is irrational: suppose for a contradiction that it& #39;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& #39;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& #39;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& #39;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
