Talk:Prime number/Archive 1

From Wikipedia, the free encyclopedia

Contents

[edit] Formula for yielding primes

On the Prime number page it gives the formula f(n) = n^2 − n + 41 but on the link to the "formulas for primes" page it gives the formula as f(n) = n^2 + n + 41. I don't care to confirm which one is the correct one, or if they both are. Just pointing it out for someone else.

Both are correct and both are cited by sources. If f(n) = n^2 − n + 41 and g(n) = n^2 + n + 41, then f(n) = g(n-1), so the only difference is a change by 1 in the n values which give primes. PrimeHunter 14:07, 23 February 2007 (UTC)

[edit] Initial segment of primes

Links: http://www.utm.edu/research/primes/

The first 750,000 primes: http://www.geocities.com:80/ResearchTriangle/Thinktank/2434/prime/primenumbers.html

Now here's an interesting question which may even provide a valid use for subpages.

Would adding a list of all the prime numbers known to mankind be counter-productive to the idea of the Wikipedia? It is "a compendium of human knowledge", regardless of how obscure and arcane.

(I suppose one could extend this to listing Pi to a quadrillion digits, to be somewhat hyperbolic.)

Thoughts? --Colin dellow

I'd say that the encyclopedia should be a compendium of all useful knowledge. Digit number 323454 of Pi and the temperature at noon on May 7, 1976 in Salt Lake City are part of human knowledge, but really, nobody has a use for this information except maybe some highly specialized experts, who know where to look it up.

I perhaps didn't make my point clear. Wikipedia presents the ability to have "useless" trivia because of the Wikipedia is not paper argument.

Perhaps it will be useful only to a specialised group, but does it hurt to have it? It would increase the amount of information available in the Wikipedia. (I found the comment about temperature

s

in Salt Lake City at a

given year to be somewhat unrelated to this question, BTW.) --Colin dellow

Actually, I don't think it would be possible to list all the known primes. There are just too darn many of them, and it's too easy to find more. - Hank Ramsey

I don't think it would be a waste of space to have a separate article that lists say, all the primes less than 10,000. This is actually very little raw data, but having available the primes in this range is very useful to many people, especially for testing conjectures, making conjectures, playing around with numbers, etc. The information would NOT just be trivial as in the temperature of Salt Lake City at a certain time. Also, I think it would be very useful if there were an article that listed the complete prime factorisations of all integers less than 10,000. Again, this is not trivial information, it's very important if someone wants to quickly test whether or not a conjecture may or may not be true.

Agreed --Haggis 14:39, 24 Feb 2005 (UTC)

But don't forget, that there exist prime-tables (2-100.000, 100.001-200.000, ... ) in wikisource. --Arbol01 02:19, 25 Feb 2005 (UTC)


correcting Wikipedia entry of Euclid's Infinitude of Primes proof

Fixed font - Proportional font


Archimedes Plutonium Apr 14, 10:17 am show options Newsgroups: sci.math, sci.logic, sci.edu From: Archimedes Plutonium <a_pluton...@iw.net> - Find messages by this author Date: Thu, 14 Apr 2005 12:17:05 -0500 Local: Thurs,Apr 14 2005 10:17 am Subject: correcting Wikipedia entry of Euclid's Infinitude of Primes proof Reply | Reply to Author | Forward | Print | Individual Message | Show original | Report Abuse

Thu, 14 Apr 2005 12:23:29 -0000 SunCode wrote:

> > Yes, thanks, I will execute on your suggestion.

> Yes! do so, but please read this page first =)

> http://en.wikipedia.org/wiki/Wikipedia:No_original_research

> SunCode.

Correcting Euclid's Infinitude of Primes (IP) proof is not original research, especially in light of the fact that out of 31 authors of a publicly written IP proof only 3 of them gave a valid rendition, and the others which includes MathWorld and Wikipedia gave a flawed and invalid IP proof. So that hardly counts as original research in the fact that 3 authors of the past of Flath, Landau, and Stillwell managed to give a valid IP proof in a textbook and that it was the misfortune of MathWorld and Wikipedia to have chosen the other 28 authors who rendered a invalid and error filled rendition. If Wikipedia had copied Stillwell's rendition plus adding a line saying that Euclid gave a Direct Method Proof of increasing set cardinality then Wikipedia would not be on the list of flawed and invalid proofs.

So this is not original research but the correction of flawed and invalid past thinking and understanding.

I have not pinpointed as to where in the history of mathematics that this stain and tarnish on Euclid's IP started. I have a educated guess that it was Gauss himself who started the flaw because Gauss used Reductio Ad Absurdum so much in his own work of Number Theory that later mathematicians would fall into the trap of thinking that Euclid's IP was Reductio Ad Absurdum (the Indirect Method).

So thanks to SunCode, I am still going to apply to Wikipedia today to start the motion for them to change their entry on Euclid's Infinitude of Primes proof. If Wikipedia had a webpage where they claim that the addition of 2 plus 2 comes out to be equal to 3, then that should not be called original research when someone trys to correct them by pointing out it is equal to 4.

Thanks SunCode, and I think I will apply for a brevity Euclid's Infinitude of Primes proof considering that full details can always be referred to my website of File 106 in www.iw.net/~a_plutonium

Correction to Wikipedia website of Euclid's Infinitude of Primes Proof:

Euclid, from his own language of "prime numbers are more than any assigned multitude" gave a Direct Proof Method for Infinitude of Primes. This method is one of increasing the set cardinality of any given finite set of primes which by logic then generalizes to an infinite set. Many mathematicians in the 19th and 20th century erroneously thought that Euclid gave a Indirect Proof Method which caused them to render an invalid proof attempt by searching for a prime-factor.

Direct Proof of IP: Given any finite collection of primes 2,3,...,pn possessing a cardinality n We find another prime by considering P!+1 = (2x3x...xpn) +1 Either P!+1 itself is a prime or else it has a prime factor not equal with any of the primes on the finite list. Thus the cardinality of every finite set can be increased. And since all/any finite cardinality set can be increased by 1 more prime therefore the set of primes is an infinite set.

Euclid's IP was not Indirect or Reductio Ad Absurdum but I give it here anyway to show for instruction sake:

Proof: The prime numbers are the numbers 2,3,...,pn,... of set P Suppose finite, then 2,3,...,pn is the complete set of primes. Form P!+1 = (2x3x,...,xpn) + 1 Now P!+1 is necessarily a new prime because all the primes that exist leave a remainder of 1 when divided into P!+1 and so by the very definition of what it means to be prime this new number of P!+1 in this restricted space of primes is necessarily a new prime not on the original list. Contradiction, hence set of primes is infinite.

Euclid never used the Indirect Method to prove his Infinitude of Primes. Somewhere around the time of Gauss was the erroneous claim that Euclid used the Reductio Ad Absurdum for IP. Worse yet was the mixing up of methods of making a prime factor search in the Indirect Method when P!+1 once formed is automatically the new prime.

So I have corrected two items in Euclid's Infinitude of Primes proof. One item is the history of the proof is Direct and not Indirect method. The second item is that in a Indirect proof of IP there cannot be a prime-factor search because the definition of prime forces the new number P!+1 to be automatically the new prime given that restricted space of primes.

Copy send to Wikipedia editors.

Please note I can make the correction as brief as possible to one short paragraph.

Archimedes Plutonium www.iw.net/~a_plutonium whole entire Universe is just one big atom where dots of the electron-dot-cloud are galaxies

Archimedes Plutonium has been posting much to sci.math under the bizarre impression that Euclid's proof is somehow imprecise, too verbose, or incorrect. It is none of these things, and his strange explanation of how Euclid did not use a simple (in fact, seen by most as the protypical) reductio ad absurdum proof is merely clutter. Incorrect clutter. This is the first time I've edited a wikipedia page; I am going to attempt a revert. Tez 08:40, 15 Apr 2005 (UTC)
Of course, Archimedes Plutonium is correct and Euclid is wrong. Euclid's proof is formally incorrect because it actually states that given any three primes, one can find a fourth not on the list. Sometimes, I wonder if anyone has actually read Euclid's actual proof, which is widely available in English. -ilan
I have read Euclid's actual proof, in English transaltion, and I thought that it was clear that Euclid meant to imply the general case as an obvious extrapolation from the case of one and then three primes. He didn't explicitly say anything like "extending this argument to the general case proves the theorem," but I believe that was what he was thinking, and that he considered it too obvious to put in. Certainly it is implausible to suggest he meant nothing of this kind, and that he made an error of logic, since the proof is so obviously defective without it; Euclid was not so foolish as that. -- Dominus 19:20, 25 May 2005 (UTC)
Well, considering how much anger and frustration is observed in professors grading students who only did 3 steps in a mathematical induction proof, it is ironic to see that this was the exact method used by Euclid and Archimedes. I guess they would have miserably failed finite mathematics courses. The final irony is Doron Zeilberger's observation that doing 3 steps in an induction is actually a formally correct proof for the formulas for the sum of the first n positive integers. -ilan

[edit] Infinitude of primes

Note regarding the proof of the infinitude of primes: we use the fact that every composite number has a prime factor. I think that requires proof in itself.

Yes, perhaps, if it isn't obvious. It is clear that if a given number has a composite divisor, then the divisors of that divisor are also divisors of the original number (if A=B*C and C=D*E then A=B*D*E). If any of these divisors are composite, we can apply this principle recursively to find more divisors of the original number. We cannot recurse indefinitely because the number cannot have an infinite number of divisors. So eventually we must reach a point where all the new divisors are prime. QED

Re: every composite number has a prime factor; this is a direct corollary of the fundamental theorem of arithmetic. Done.

sub page or article on infamous research project "A Short List of Even Primes" which is of course, mainly acknowledgements and academic scaffolding, followed by the list, viz. 2

I wouldn't mind a link to a joke if it's clearly labeled as such. For that matter, I wouldn't mind adding the old "proof" that all primes are odd. -LC

The article says:

There are infinitely many prime numbers. The oldest known proof for this statement dates back to the Greek mathematician Euclid. It is also one of the oldest known proofs by contradiction.

I thought that Euclid stated the theorem as "Given any prime, there is a larger prime." With the theorem stated like this, the proof isn't a proof by contradiction -- the existence of the larger prime is shown directly. Can someone confirm this, or am I misremembering? --Zundark, 2001 Oct 11

I think you're right; I'll take the contradiction bit out. --AxelBoldt

I see someone has put it back in again. I will remove it (or reword it) if no one can provide a justification for it. --Zundark 15:09 Apr 3, 2003 (UTC)

Yes, I believe it IS a proof by contradiction. We wish to show there exist infinitely many primes. So, suppose not; suppose there only exist finitely many primes. Then certainly there exists a _largest_ prime since there are only finitely many. But given this largest prime, I can show that there must exist another prime larger than the largest prime. This is a contradiction. Hence, there must be an infinite number of primes.

It's not a question of what we wish to show, but of what Euclid actually showed. There is an English translation here. Euclid claims that there are more than any given finite number of primes, and proves this directly by taking a finite number of primes, and showing that there is another. To read this as a proof by contradiction that there are an infinite number of primes is to add a modern gloss that does not exist in the original.
If you read the above-mentioned translation you will see that Euclid's proof - like many of his other proofs - does involve a proof by contradiction: he proves by contradiction that G is not a member of the finite set of primes. But our article is wrong to claim that Euclid's proof of the theorem as a whole is a reductio ad absurdum. I will maybe try to rewrite that part of the article later today. --Zundark 11:19, 13 Oct 2003 (UTC)
It seems to me, at least from the translation linked above, that the theorem certainly does involve proof by contradition. It says, in part:
"I say that G is not the same with any of the numbers A, B, and C. If possible, let it be so. ... Therefore G, being a number, measures the remainder, the unit DF, which is absurd. Therefore G is not the same with any one of the numbers A, B, and C."
Euclid assumes that G (previously constructed as a prime factor of ABC+1) is identical with one of A, B, or C, derives a contradiction, and concludes the oppoisite, that G is distinct from A, B, and C. I don't know how free the translation is, but to assert that the proof is not an example of reductio ad absurdum in the face of the phrase "which is absurd" is rather absurd. -- Dominus 19:33, 25 May 2005 (UTC)
There is a difference between "involves a reductio ad absurdum" (which the proof certainly does, as I already pointed out above some 19 months ago) and "is a reductio ad absurdum" (which the proof isn't). --Zundark 20:38, 25 May 2005 (UTC)
Well, the distinction is lost on me personally, in the present case, then. Can you elaborate?? Revolver 05:28, 26 May 2005 (UTC)
The translation linked above is an eleven-paragraph proof, of which two-and-a-bit paragraphs near the end are a proof by reductio ad absurdum that G is not equal to A, B or C. You could even remove this reductio ad absurdum part and the proof as a whole would still make sense, so I don't see how the proof as a whole can possibly be considered as a reductio ad absurdum. --Zundark 08:20, 26 May 2005 (UTC)
I see. I was thinking again that it started "Thm: There are an infinite number of primes. Pf: Suppose not, then...", again forgetting this isn't how it's stated. Revolver 08:51, 26 May 2005 (UTC)

It seems that the source of confusion or differing interpretations is coming from different ways of translating Euclid's statement into logical statements involving quantifiers. The modern definition of an infinite set is usually taken to be the following (if not, then it is easily shown to be equivalent to the definition):

A set S is infinite if it cannot be put in 1-1 correspondence with a natural number or the empty set (if 0 is not considered a natural number).

This is a definition by negation. An infinite is defined to be one that is not finite. So, to prove by definition that a set is infinite, one can do the following:

Suppose for sake of contradiction that S CAN be put in 1-1 correspondence with a natural number or 0. Then....<contradiction is achieved>. Thus, S is infinite.

The way of expressing this definition in terms of logical quantifiers would be

~ (exists A)(P(A))

where ~ is negation and P(A) a statement involving A.

By modern rules of logic (at least, most logical systems, and certainly the one most working math people use), this is logically equivalent to

(for all A)(~ (P(A)))

This is the form of the theorem as stated by Euclid. He gave a direct proof of the positive assertion that for all A, ~ P(A) is true. What is happening is we come along, almost subconsciously without thinking, identify this statement with the logically equivalent form given above, and then realize that by the definition of infinite set, this is really a proof that the set of primes is infinite.

Now, how this should all be interpreted and presented, I don't have all the answers, maybe a short disclaimer explaining what I've mentioned above is in order. At any rate, it's open for discussion.

[edit] list a Direct Method plus an Indirect Method proof alongside one another for Euclid's Infinitude of Primes

Apparently the above evinces us that a long debate has been going on here in Wikipedia as to whether Euclid gave a Direct Method proof or Indirect Method proof. Zundark above discusses it. I also edited in 2005 but was reverted.

I am told that Arthur Rubin is the author of the now existing proof of Euclid IP. My gripe about his proof is that it is a mixture of both the Direct and Indirect all in one and leaves the argument as flawed and invalid since the lines do not flow logically. And how can they when they are a combination of two methods all muddled together. G.H. Hardy in his book A Mathematician's Apology stated outright that Euclid's IP was Indirect, even though Hardy botched it up. Stillwell in his book Mathematics and its History gives a Direct Method proof.

Wikipedia's Arthur Rubin (if he truly is the author since he seems not to want to admit or deny) gives a mishmash blend of Indirect by starting off with the Suppose finite, yet throwing into the midsection a prime factor search.

What I am asking is simply that a Expert TAG be placed on this Wikipedia entry and removed once authors display both a Euclid Infinitude of Primes Direct method alongside a Euclid Infinitude of Primes Indirect method. So any reader can see the difference and be assured that what is displayed is not some garbled mixture but a VALID and True proof argument. Plus, in addition mention a short paragraph of the history of Euclid's IP proof saying that the Reductio Ad Absurdum had been discovered in the ancient time of Euclid and that mathematicians back then did not realize most math proofs are offered two independent methods of proving. So that we can perhaps never be certain as to what Euclid intended-- whether he wanted the Direct method or the Indirect method.

We give full credit to Euclid for discovering this proof, and we simply list both methods whenever we display Euclid's IP.

So I am asking that Arthur Rubin place a Expert TAG on this Euclid IP proof and to be removed once author or authors agree on the listed two methods and the history paragraph. Why an Expert tag? Because the present Wikipedia entry is a copy version of the Niven Zuckerman Montgomery version with a few changes. This is evidence that the person who placed the entry into Wikipedia is not even self confident in writing his own Euclid IP, let alone write a Direct and Indirect valid proofs thereof. If the author has to resort to a rehash of some books IP, that author is no expert on Euclid IP.

Here is my own offering and I have written a book on this subject:

The oldest known proof for the statement that there are infinitely many prime numbers is given by the Greek mathematician Euclid in his Elements (Book IX, Proposition 20). Euclid states the result as "there are more than any given [finite] number of primes", and his proof is essentially the following:

It is unknown as to whether Euclid meant a Direct or Indirect proof, since his proof was over 2,000 years old and the concepts in ancient times are not amenable in our modern mathematics to differentiate whether Euclid intended to be Direct or Indirect, which is further complicated by the fact that Reductio Ad Absurdum was just discovered around the time of Euclid. One thing though is certain that if you combine the two methods into one, you end up with an invalid argument. Thus, the logical thing to do is to always give two proofs using the Direct Method in one and the Indirect in the other. This requirement makes Euclid IP crystal clear and valid.

Euclid Proof of Infinitude of Primes: Direct Method: Increase the cardinality of any finite set for example {3,5} form W+1 = (3x5)+1 which is 16. Now apply the prime factor search yielding the prime 2 out of 16. Thus you produced a new prime not on your list. And since *any* finite set is increased in cardinality implies it is infinite.

Euclid Proof of Infinitude of Primes: Indirect Method: Definition of prime. Suppose all primes finite, and keeping the example {3,5}. Form W+1 = (3x5)+1 which is 16. It is necessarily prime because 3 and 5 are all the primes that ever exist but when they divide into W+1 they leave a remainder of 1, hence W+1 is prime from the definition of prime and larger than 5. Contradiction. Thus we reverse the assumption which tells us that the set of primes is infinite.

By listing both methods together, we cut the confusion and misunderstanding of young people eager to learn the truth about one of the most vaunted math proofs. Superdeterminism 06:32, 11 April 2007 (UTC)

Your proposal does not meet the standards of a wikipedia article either grammatically or mathematically. This applies in particular to what you call your second indirect proof, which would be unacceptable in any revised form. You do not provide sources for your historical remarks about Euclid. If they form part of your own original research, they are not appropriate for inclusion in a wikipedia article. --Mathsci 07:53, 11 April 2007 (UTC)

In response to Mathsci. Think about what you have said. You have said that a flawed and error filled proof is acceptable to Wikipedia, but that a true and valid proof which has perhaps a grammar error is not acceptable. That is what you are saying.

No it is not. I am saying that you do not seem able to produce coherent mathematical arguments. Nor. from what you write here, do you seem able to understand a fairly elementary piece of mathematics, often used as an interview question for prospective undergraduates. --Mathsci 21:08, 11 April 2007 (UTC)

Questions for Arthur Rubin. Are you the author of the current Wikipedia Euclid Infinitude of Primes proof? And if so, how do you interpret your proof as to whether it is Direct method or Indirect Method? Also, did you copy the proof as given by this textbook where you made a few changes such as calling "r" as "m"?: quoting Niven, Zuckerman, Montgomery, AN INTRODUCTION TO THE THEORY OF NUMBERS 5ed, John Wiley & Sons 1991, pp 25 & 26

Theorem 1.17 Euclid. The number of primes is infinite. That is, there is no end to the sequence of primes 2,3,5,7,11,13,... Proof Suppose that p_1,p_2, ... ,p_r are the first r primes. Then form the number n = 1 + p_1 p_2 ... p_r Note that n is not divisible by p_1 or p_2 or ... or p_r. Hence any prime divisor p of n is a prime distinct from p_1, p_2, ..., p_r. Since n is either a prime or has a prime factor p, this implies that there is a prime distinct from p_1,p_2,...,p_r. Thus we see that for any finite r, the number of primes is not exactly r. Hence the number of primes is infinite. Student often note that the first few of the numbers n here are primes. However, 1+2x3x5x7x11x13 = 59x509. end quoting Niven, Zuckerman, Montgomery Superdeterminism 10:10, 11 April 2007 (UTC)

I checked my edition of Euclid's Elements, and sure enough, he doesn't phrase his proof as an indirect one. He simply shows that, for all positive integers m, if there are m primes, then there are m+1 primes. He doesn't mention infinity at all.
Our article here seems to present Euclid's proof pretty accurately, not claiming that it's an indirect proof. I fail to see what the problem is. -GTBacchus(talk) 16:41, 11 April 2007 (UTC)

In Reply to Bacchus You made a mistake Bacchus with this phrase of yours "for all positive integers m, if there are m primes, then there are m+1 primes" so I do not think your math abilities are cut out to judge and edit any of this debate over Euclid IP.

The problem is that you need not a Dispute Tag but an Expert Tag. Since Wiki entry of this proof is a outright copy of the above Niven Zuckerman Montgomery after changing a few words and sentences. The person who gave Wiki's Euclid IP is not an expert on this proof but is so far lacking in understanding of the proof that he/she cannot even do his own in his head without borrowing from NZM and changing a few words and sentences.

Why not copy G.H.Hardy's proof in his book A Mathematician's Apology where he states that Euclid was Indirect, and then whenever a reader questions what Wiki's version is, they can say "Well Hardy cited it as Indirect, so like a parrot puppet-- it is Indirect"

THE PROBLEM of Wiki's version is that it is not a proof since it is so flawed with errors with its mixing of two methods that tries to pass as a proof argument. It obfuscates the reader, not clarify the reader. One never knows what a valid Indirect or valid Direct Euclid IP is, after reading Wiki's entry. It is so riddled with error by starting with "Suppose finite" and then ending with increasing set cardinality. It is loaded with grammar and concept errors for example what is "finite set of primes" but a major mistake. What is the sentence "And one is not divisible by any primes." doing there, may as well sing a song in the middle of the proof. Perhaps the author wanted to disguise the fact that he copied NZM, unable to do a proof himself and so threw in some sentences that are irrelevant.

Here is the present pitiful entry:

Suppose you have a finite number of primes. Call this number m. Multiply all m primes together and add one (see Euclid number). The resulting number is not divisible by any of the finite set of primes, because dividing by any of these would give a remainder of one. And one is not divisible by any primes. Therefore it must either be prime itself, or be divisible by some other prime that was not included in the finite set. Either way, there must be at least m + 1 primes. But this argument applies no matter what m is; it applies to m + 1, too. So there are more primes than any given finite number.

What you need is not a Dispute Tag but a tag asking for someone who is expert on this proof who can do it without having to copy some book's proof and then never able to answer anyone's questioning the proof since they were never able to do a valid proof in the first place, let alone able to give a Indirect alongside a Direct. Superdeterminism 17:16, 11 April 2007 (UTC)

Hmm... I certainly didn't claim that Euclid's proof was indirect, and I'm not looking at Hardy, I'm looking in my copy of Euclid. Can you tell me clearly what is mistaken about what I said? You say "for all positive integers m, if there are m primes, then there are m+1 primes" is incorrect. Why? -GTBacchus(talk) 17:50, 11 April 2007 (UTC)
You know, I think it would be more constructive to stop feeding the trolls. —David Eppstein 17:56, 11 April 2007 (UTC)
Oh, you're probably right. I find it easy to be drawn in by arguments like this, but you're right. I'll let it drop. -GTBacchus(talk) 18:09, 11 April 2007 (UTC)

Newsgroups: sci.math From: "a_plutonium" <a_pluton...@hotmail.com> Date: 11 Apr 2007 10:51:47 -0700 Local: Wed, Apr 11 2007 12:51 pm Subject: Re: new standard for Euclid IP proof-- able to give both Direct and Indirect alongside one another Re: Correcting Wikipedia's Euclid's Infinitude of Primes Proof

Mark Nudelman wrote:

> I still don't think Wikipedia's proof is invalid. But here are my versions:

> By contradiction:

> Assume there are a finite number of primes. > Let N be the number of primes. > Let S be the set of all primes. S = {p_1, p_2, ..., p_N}. > Let g = (p_1 * p_2 * ... * p_N)+1. > Since g > p_i for all i (1 <= i <= N), g is not equal to any p_i and g > is not in S. > Since S was assumed to be the set of all primes, g must be composite. > Let k be the largest prime factor of g. For all i (1 <= i <= N), no p_i > is a factor of g, so k is not equal to any p_i and k is not in S. > But S was assumed to be the set of all primes, so k is not prime, which > contradicts k being g's largest prime factor. > Therefore the assumption is impossible, and there are not a finite > number of primes. > QED

> Direct:

> Let S be any finite set of N primes. S = {p_1, p_2, ..., p_N}. > Let g = (p_1 * p_2 * ... * p_N)+1. > g is either prime or composite. > Case 1. g is prime: Since g > p_i for all i (1 <= i <= N), then g is not > equal to any p_i and g is not in S. > Case 2. g is composite: Let k be the largest prime factor of g. For all > i (1 <= i <= N), no p_i is a factor of g, so k is not equal to any p_i > and k is not in S. > Thus in either case, there is a prime which is not S. > Therefore no finite set of primes contains all primes. > QED.

> --Mark

Mark I can understand now why you like the Wikipedia entry even though it is very flawed and invalid. Because yours is so much worse. And call me a jerk again because I hate wasting time.

It is apparent to me that you never really studied or understood Symbolic Logic, as such a subject pares away non-sequiturs and irrelevancies, but most of all Symbolic Logic gives a person a plan-of-attack on a proof.

Mark, neither one of yours above is a valid proof, but mistake ridden through and through.

If you knew these proofs, you would know that the Direct is set cardinality increase from any finite cardinality you increase it by one new prime, and thus finite becomes infinite. Your Direct above gives no hint of increasing set cardinality.

And since both Direct and Indirect uses W+1 (what you call g), and if you had mastered Symbolic Logic, you would know that a prime factor search would be carried on in only one method, not both. You would know that both methods really require you to find just one thing---- a new prime. So in the Direct Method of set cardinality increase, you have to conduct a Prime Factor Search for a new prime. But in the Indirect Method g is necessarily your new prime and you cannot flail around with a prime factor search.

Notice the symmetry of the two methods below, how they are connected because of W+1 is in both, and notice how a prime factor search can only be conducted in Direct, but since Indirect is under the reductio assumption there is no wiggle room to conclude anything about W+1 (your g), but only conclude that it is necessarily prime. Which is really all we wanted in the first place --- fetch a new prime.

Here are the two valid proofs of Euclid IP in shortform:

Euclid Proof of Infinitude of Primes: Direct Method: Increase the cardinality of any finite set for example {3,5} form W+1 = (3x5)+1 which is 16. Now apply the prime factor search yielding the prime 2 out of 16. Thus you produced a new prime not on your list. And since

  • any* finite set is increased in cardinality implies it is infinite.

Euclid Proof of Infinitude of Primes: Indirect Method: Suppose all primes finite, and keeping the example {3,5}. Form W+1 = (3x5)+1 which is 16. It is necessarily prime because 3 and 5 are all the primes that ever exist but when they divide into W+1 they leave a remainder of 1, hence W+1 is prime from the definition of prime and larger than 5. Contradiction. Thus we reverse the assumption which tells us that the set of primes is infinite.

Superdeterminism 18:06, 11 April 2007 (UTC)


Newsgroups: sci.math From: "a_plutonium" <a_pluton...@hotmail.com> Date: 11 Apr 2007 19:16:10 -0700 Local: Wed, Apr 11 2007 9:16 pm Subject: a simple test to recognize if a IP is valid or if invalid Re: Correcting Wikipedia's Euclid's Infinitude of Primes Proof

Mark Nudelman wrote:

(snip)

> This blather is completely meaningless. Point to where the error is in > my proof is rather than philosophizing about cardinality. My direct > proof clearly that any finite set of primes is incomplete. If you want > to phrase that in terms of cardinality, that's fine, but what I stated > was sufficient. > --Mark

When one translates the Direct Method Euclid IP into Symbolic Logic they end up with steps like this where each letter represents a step of the proof:

A B C D E P G H I J Y

When one translates the Indirect Method Euclid IP into Symbolic Logic they end up with steps like this:

A N O P Q R S T U V X Y

Now ANALYZE these proofs as steps of Symbolic Logic. Both proofs have a few steps in common and are equal. For instance the first step in both Direct and Indirect can be the definition of prime and this is required step in the Indirect. So, as you can see A=A are the same in both for the first step.

There is another step in both methods which are the same. It is the step where you form W+1. I estimated it as the step labeled "P" in the above.

Now there is another step which is the same in both and I labeled it G, which is the step that says a new prime not on the original list is found. And another step the same in both call it Y, which is the step that declares the set of primes is infinite.

Now there are some steps which have a different level of importance from other steps. Call these steps the crucial steps or the critical steps. The reductio-ad- absurdum step in the Indirect Method is a more important step than many other steps. I labeled it N above.

There are especially two Critical Steps in both proofs. It is the steps in which provide the mechanism of producing a new prime not on the original list. In the Direct Method it is step I labeled G in which a Prime Factor Search is conducted. In the Indirect Method it is step labeled Q where W+1 is necessarily a new prime.

So, the error Mark makes and what most people who attempt this will make is that the mechanism that produces the new prime, to them will all be the same--- a prime factor search.

That is the reason their proofs are flawed and invalid, because if the mechanism that yields the new prime is the same in both methods, means that there never was two distinct methods. If Mark spends a minute of reflection, he will see and notice that the mechanism to yield a new prime is the same mechanism in both his methods; he conducts a prime factor search.

The Symbolic Logic tells us that the methods are different, and that entails the mechanism has to be different. And what are (sic) the two different mechanisms? Easy. The Direct mechanism is the prime factor search. The Indirect mechanism is that W+1 is necessarily a new prime due to the reductio ad absurdum imposition.

So, as anyone dares to proffer two proofs, one Direct and one Indirect, to see if they are valid, must pass the test that the mechanism is different in the two proofs. If they are the same such as in Mark's then he has a failed and invalid proof.

Superdeterminism 03:02, 12 April 2007 (UTC)