- 20,819
- 28,465
Well, it is what I consider the most basic proof I've ever seen. I like it for several reasons: it is so simple. that you can convince a preschool kid, it uses one of the most fundamental principles at all: you cannot derive false from true, and it is old enough to count as such:
No, sorry kids, not Pythagoras. Euclid's (##\approx 300\, BC##) proof about the number of primes.
For any finite set ##\{p_1,\ldots,p_r\}## of primes, consider the number ##n = p_1p_2 \cdots p_r + 1.## This ##n## has a prime divisor ##p##. But ##p## is not one of the ##p_k## : otherwise ##p## would be a divisor of ##n## and of the product ##p_1p_2 \cdots p_r##, and thus also of the difference ##n − p_1p_2 \cdots p_r = 1,## which is impossible. So a finite set ##\{p_1,\ldots,p_r\}## cannot be the collection of all prime numbers.
Can you phrase the statement which is proven, and rephrase this proof, such that
Can you find all the hidden assumptions in the above proof?
Hint: There are many.
No, sorry kids, not Pythagoras. Euclid's (##\approx 300\, BC##) proof about the number of primes.
For any finite set ##\{p_1,\ldots,p_r\}## of primes, consider the number ##n = p_1p_2 \cdots p_r + 1.## This ##n## has a prime divisor ##p##. But ##p## is not one of the ##p_k## : otherwise ##p## would be a divisor of ##n## and of the product ##p_1p_2 \cdots p_r##, and thus also of the difference ##n − p_1p_2 \cdots p_r = 1,## which is impossible. So a finite set ##\{p_1,\ldots,p_r\}## cannot be the collection of all prime numbers.
Can you phrase the statement which is proven, and rephrase this proof, such that
- it is clearly an indirect proof
- it is clearly a proof by contradiction
Can you find all the hidden assumptions in the above proof?
Hint: There are many.