proofs
Contents
3.2. proofs#
3.2.1. proofs#
induction
must already know formula
doesn’t give intuition
there are uncomputable functions e.g. Halting Problem, 3x+1 problem
non-existence proofs
must cover all possible scenarios, harder than existence
3.2.2. interesting#
Biggest primes, the twins
Infinite twin primes – guy working at subway
Different infinites – people driven crazy
Four-Color problem – Computer aided proof in 1977, basically checks cases
Bruower’s Fixed Point Theorem
Fermat’s Last Theorem – Pythagorean thm untrue for anything bigger than squared
Pf in 1995
Godel’s Thm: there are unprovable statements
Pigeonhole Principle
Claim: Consider a 10 foot by 10 foot square room. Let every point on the floor of the room be colored either red or blue. Then there exists somewhere on the floor two points of the same color that are exactly one foot apart.
Proof: Consider an equilateral triangle on the floor of the room with side lengths equal to one foot. As every point is either red or blue, two vertices of the triangle must have the same color, satisfying the claim.
There must be 2 people in London with the same amount of hairs on their head