Re:Answer to a 150-Year-Old Math Conundrum Brings More Mystery
by bluecheese33 on Sunday June 21, 2015 @10:04PM
(#9755791)
It is a common simplification of Euclid's proof to convert it to a proof by contradiction. In fact, I believe I was taught this version of the proof in an early undergraduate math class. This version is not constructive, actually the first example of the wikipedia article on constructive proofs points this out:
Euclid's proof is constructive. But a common way of simplifying Euclid's proof postulates that, contrary to the assertion in the theorem, there are only a finite number of them, in which case there is a largest one, denoted n. Then consider the number n! + 1 (1 + the product of the first n numbers). Either this number is prime, or all of its prime factors are greater than n. Without establishing a specific prime number, this proves that one exists that is greater than n, contrary to the original postulate.
Step 1 is the specific example. You say:
But you haven't said that p_1 through p_n are all the primes up to and including p_n. A set that satisfies your step 1 is the set { 7 }. I can read your step 1 and say: OK, I'll assume that { 7 } is the set of all primes.Then you say:
The natural reading of this is to think you're saying that p_1, p_2, p_3, ..., p_n are the primes up to p_n. If not, why have you called it p_n and not simply called it P. Doing so makes it clear that in step 2 you are taking all the primes up to some limit, rather than taking all the primes in a collection of size n, with p_n the maximum element.This is exacerbated by the fact that the usual proof does start with a specific collection, which is at odds with what you seem to be saying.
You say:
Yes, but only if you use this unexpected interpretation that p_n is simply a limit, and not the largest/last element of an arbitrary set of primes.So the proof you've given is not exactly the usual proof, it's subtly different. The notation you use brings to mind the usual proof, and creates a confusion about what you're actually saying. The objective of the proof I gave is to avoid those potential mis-interpretations.
Does that make it clear? Perhaps it's important to add that I'm not saying your proof is actually wrong, I'm just saying that if an undergrad produced it I'd be asking for clarification on a few points to see if they really understood it, or if they'd just memorised it and perhaps missed a point, or muddled two formulations.