Ore's direct method improves mine own #612 Correcting Math
in [Logic]
|
Prev: How Can ZFC/PA do much of Math - it Can't Even Prove PAisConsistent (EASY PROOF)
Next: lemmas by contradiction usually mean the author forgot he invoked a theorem #613 Correcting Math
From: Archimedes Plutonium on 30 Jun 2010 04:00 Archimedes Plutonium wrote: > > [0] Michael *Hardy* and Catherine Woodgold, > > "*Prime* *Simplicity*", *Mathematical > > Intelligencer<https://mail.google.com/wiki/Mathematical_Intelligencer> --- quoting from Mathematical Intelligencer MI of Ore's direct proof --- page 65 of Øystein Ores book Number Theory and Its History [104]: Euclids proof runs as follows. Let a;b;c;...;k be any family of prime numbers. Take their product P ¼ ab...k and add 1. Then P + 1 is either a prime or not a prime. If it is, we have added another prime to those given. If it is not, it must be divisible by some prime p. But p cannot be identical with any of the given prime numbers a;b;...;k because then it would divide P and also P + 1; hence it would divide their difference, which is 1, and this is impossible. Therefore a new prime can always be found to any given (finite) set of primes. Within this argument, we do find one small lemma proved by contradiction. --- end quoting --- Now I was thinking that we never really needed any reductio ad absurdum anywhere and anyplace in the full Direct Euclid Infinitude of Primes. Can I make that so? I think so, for mine own direct method proofs have no contradiction. And as I wrote them in the early or mid 1990s I used the unique prime factorization theorem(UPFAT). I am sure that Euclid was privy to UPFAT and that every Direct method uses UPFAT, only we glide past saying so. One of the reasons that I like to give "reasons" alongside the statements is to keep me on track. Here are my most recent Direct Method in both shortform and longform: Euclid's IP, Direct or constructive in short-form goes like this: 1) Definition of prime 2) Given any finite set of primes 3) Multiply the lot and add 1 (Euclid's number) which I call W+1 4) Either W+1 is prime or we conduct a prime factor search 5) this new prime increases the set cardinality by one more prime 6) since this operation of increasing set cardinality occurs for any given finite set we start with, means the primes are infinite set. Notice in step 4 of shortform, we know that either W+1 or a factor of W+1 has a prime which is not in the finite list at the start and we know this from UPFAT. So UPFAT eliminates the need to do what Ore or even Euclid did, since when we invoke UPFAT, and we cannot escape from invoking UPFAT as Euclid invokes UPFAT and Ore invokes UPFAT. The Unique Prime Factorization theorem tells us that either W+1 is prime or has a prime factor. So the only thing remaining is to mechanically fetch the new prime and we do that by taking the square root of W+1 and going through all the primes less than or equal to the square root of W+1. DIRECT Method (constructive method), long-form; Infinitude of Primes Proof (1) Definition of prime as a positive integer divisible only by itself and 1. (2) Statement: Given any finite collection of primes 2,3,5,7,11, ..,p_n possessing a cardinality n Reason: given (3) Statement: we find another prime by considering W+1 =(2x3x...xpn) +1 Reason: can always operate on given numbers (4) Statement: Either W+1 itself is a prime Reason: numbers are either unit, composite or prime (5) Statement: Or else it has a prime factor not equal to any of the 2,3,...,pn Reason: numbers are either unit, composite or prime (6) Statement: If W+1 is not prime, we find that prime factor Reason: We take the square root of W+1 and we do a prime search through all the primes from 2 to square-root of W+1 until we find that prime factor which evenly divides W+1 (7) Statement: Thus the cardinality of every finite set can be increased. Reason: from steps (3) through (6) (8) Statement: Since all/any finite cardinality set can be increased by one more prime, therefore the set of primes is an infinite set. Reason: going from the existential logical quantifier to the universal quantification Now I can improve the above in that statements 4,5 have the reasons of Unique Prime Factorization theorem. Some where along the long road of writing those proofs I deleted the UPFAT, only to see that I now need it to streamline the Direct method. In the Direct method, no lemma is needed and no lemma having a argument of contradiction is needed. In the Direct method, it is all a constructive method. The so called lemma of Ore as stipulated by the authors Hardy/Woodgold, was excess baggage and that the either P+1 was prime or had a prime factor comes not from having a reductio ad absurdum but comes from UPFAT. I am convinced, only there can never be a proof of this, but convinced that in Ancient Greek times, and fairly common today in math circles, is that the expression "suppose false.." is a expression commonly blurted out and with no bearing to the proof at hand. Just as is the expression "absolutely so" or the expression "without a doubt". So I think what happened is that Euclid or the translators of Euclid, filled in spaces in the proof with expressions such "suppose false.." Expressions that fill in between sentences or phrases. And that the expression "suppose false.." was not a method that Euclid was engaged in, but merely some words that leads him into further steps of the proof. An expression in modern times of math proofs is the expression "this further implies..." Now when seeing the word "implies" in a proof, one can mistakenly think it is the logical implication, and it may well be, but often it is just the mathematician using common words to push along his argument. Now any one of us can take any easy test. We can pick up a proof and see how easy it is to insert the phrase "suppose not true.." Almost with any math proof we are reading, we can insert that phrase and although it does not launch a reductio ad absurdum lemma at that point of the proof write-up, it still looks like it fits in that spot of the proof. So what I am saying is that in Euclid's proof or in Ore's proof, both needed to say that either P+1 is prime or has a prime factor and the reason is UPFAT, but if you do not say UPFAT, you can mislead yourself by saying "suppose false, then the 1 between P and P+1 is divisable. Summary: I am convinced that no lemma of reductio ad absurdum is ever needed in the Direct/Constructive proof. I suspect that in Ancient Greek times the expression "suppose false.." was an expression of common usage and did not mean that the mathematician was launching a reductio ad absurdum. Archimedes Plutonium http://www.iw.net/~a_plutonium/ whole entire Universe is just one big atom where dots of the electron-dot-cloud are galaxies
From: sttscitrans on 30 Jun 2010 06:20
On 30 June, 09:00, Archimedes Plutonium <plutonium.archime...(a)gmail.com> wrote: > Archimedes Plutonium wrote: > > > [0] Michael *Hardy* and Catherine Woodgold, > > > "*Prime* *Simplicity*", *Mathematical > > > > So what I am saying is that in Euclid's proof or in Ore's proof, both > needed to say that > either P+1 is prime or has a prime factor and the reason is UPFAT, but > if you do not say > UPFAT, you can mislead yourself by saying "suppose false, then the 1 > between P and P+1 > is divisable. No proof whether direct or indirect will go through unless you can exclude the possibility that the integer following w= "some product of primes" or the "product of all primes assumed to exist" etc. is a unit i.e. has no prime divisors. The essence of this proof is that no two consecutive integers share a prime divisor. Whatever w+1 might be, you know it must have at least one prime divisor that is not a prime divisor of w otherwise GCD(w,w+1) <> 1. If w is the product of all primes you have a contradiction, there are no other primes that could divide w+1 without gcd(w,w+1)<> 1. If w is some product of primes then w+1 must be divisible by some other prime or primes. I am surprised it has taken you 20 years to realize this. |