4 ms·
A proof by contradiction works by assuming something incorrect, and using it to prove various incorrect things until finally we manage to prove both p and not p
by im3w1l 3y ago
A proof by contradiction works by assuming something incorrect, and using it to prove various incorrect things until finally we manage to prove both p and not p for some proposition p. Being able to prove such an absurdity shows that the assumptions must be wrong.
In this case we can prove that the constructed number both is prime (it's not divided by ANY prime hence it's prime) and isn't prime (it's not in the list hence it's not prime).
- lovecg 3y agoOk I see what you’re getting at. Maybe a better way to construct this version of the argument is - every integer > 1 is either a prime or a product of primes (this is easy to show by induction) - assume there’s a finite number of primes - then the product of all primes + 1 must be either a prime or a product of primes - but we know that it’s _neither_ (can’t be divided by any of the primes in the list, and not itself in the list), which is a contradiction - it had to be one or the other.