No Highest Prime, by definition?
George Dance
discussing a different topic.
To summarize: I had been explicating Huxley's agnostic principle
('believe nothing unless you have logically satisfactory evidence to
do so'), and argued that merely defining a god as having an a property
was *not* giving logically satisfactory evidence that that god had
that property. One person's reply was:
<quote>
> By that standard you could insist that anybody who says there's
> no highest prime number can't be an agnostic. All of math is based
> on persuasive definition, not evidence.
</quote>
Not being a mathematician, I don't know the best way to respond to
this; so I was hoping that someone with more knowledge of the subject
could address it.
Robert J. Kolker
George Dance wrote:
>
> Not being a mathematician, I don't know the best way to respond to
> this; so I was hoping that someone with more knowledge of the subject
> could address it.
The assumption that there is a largest prime leads to a flat out
contradiction. Therefore there is no largest prime.
Bob Kolker
José Carlos Santos
> <quote>
>
>>By that standard you could insist that anybody who says there's
>>no highest prime number can't be an agnostic. All of math is based
>>on persuasive definition, not evidence.
>
> </quote>
>
> Not being a mathematician, I don't know the best way to respond to
> this; so I was hoping that someone with more knowledge of the subject
> could address it.
It is *false* that the statement "there is no highest prime" is true
by definition. If some number p was the highest prime, then p! + 1 would
not be prime, since it would be greater. But, not being prime, it can
be written has a product of several prime numbers. If p' is one such
prime number, then p! + 1 is a multiple of p'. But then so is p! and
therefore 1 is a multiple of p', which is not possible, since every
prime number is greater than 1.
Best regards,
Jose Carlos Santos
Dale Worley
It's not too complicated, but it's not obvious.
Let me define "Foo-Bar" as "the mile-high diamond cube outside of Las
Vegas". As a definition, that's fine, it's clear what Foo-Bar would
be like if it existed, and if you're standing there staring at some
thing, you know how to tell whether it is Foo-Bar or not.
Note that this definition doesn't tell you anything about whether or
not Foo-Bar exists or not. You have to go to Las Vegas and look to
find that out.
Thus, the definition doesn't commit you in one way or another about
whether Foo-Bar exists. It isn't *persuasive*.
On the other hand, suppose my dog is named Rover and I say "Rover is
brown." That's not a definition, since the word "Rover" already has a
meaning. It's a statement of fact. Of course, to tell whether it's
true or not, you have to go look at Rover.
In regard to God, one has to first figure out how you want to define
"God". Let us suppose your correspondent means by God "that being
which is more powerful than any other thing in the universe". Good
enough. Now you have to go check whether there actually *is* such a
being -- your definition only says what you'd call it if it existed.
But your correspondent may prefer "that being which is more powerful
than any other thing in the universe and which observes everything
that happens in the universe". In that case, you have to go check
again -- he's made a new definition for what is really a new word, and
you've got to go out and check whether there is a thing that fits
under the new definition.
In regard to "there is no highest prime number", that isn't a matter
of definition. You can work out a proof of that fact.
Dale
Jim Burns
George Dance wrote:
>
> I need some help with a mathematical claim that came up while
> discussing a different topic.
>
> To summarize: I had been explicating Huxley's agnostic principle
> ('believe nothing unless you have logically satisfactory evidence
> to do so'), and argued that merely defining a god as having an a
> property was *not* giving logically satisfactory evidence that
> that god had that property. One person's reply was:
>
> <quote>
> > By that standard you could insist that anybody who says there's
> > no highest prime number can't be an agnostic. All of math is
> > based on persuasive definition, not evidence.
> </quote>
This is in Message-ID: <2003101921...@lsil.com>, I believe.
> Not being a mathematician, I don't know the best way to respond to
> this; so I was hoping that someone with more knowledge of the
> subject could address it.
There is no highest prime, not by definition (directly) but rather
by a clear chain of reasoning from definitions. It's not a hard proof
to understand: assume there are a finite number of primes; multiply
them all together and add one; no prime divides this new number, so
it is a new prime: contradiction, thus there are an infinite number
of primes. (I'm pretty sure I left out some important and difficult
steps, but the structure should be clear.)
That's the only part of your question which would seem to require
the services of a mathematician. The rest of it seems to be more
about the nature of mathematical truth, evidence, and so on. I
could understand mathematicians being interested in all that (I am,
myself), but it doesn't really impact what they do as
mathematicians, it seems to me.
I went to your original thread to try to understand how "persuasive
definition" was being used, but I got caught in some kind of
hall-of-mirrors effect, with you and Paul Filseth going a couple
rounds of each trying to out-agnostic the other. Here is my
understanding of your discussion, at least as it pertains
to "persuasive definitions".
[paraphrase] "quote"
GD: [So-called agnostics can not prove it's impossible to prove or
disprove the existence of god.]
PF: [Can you prove that they can not prove that? Anyway, for some
definitions of God, it is provable.]
GD: [You can prove anything you want from a properly chosen
("persuasive") definition.]
PF: [Then it would follow that all of math is based on "persuasive"
definitions.]
GD: "Excuse me? An example of 'persuasive definition' in math would
be one of someone proving that 2+2=4 (for example) simply by
defining 2+2 as 4 or vice versa. But that's not how all of math is
done, so I guess you mean something else by the phrase."
PF: "Math is persuasion by exhibiting the collective implications
of groups of definitions. It's the same sort of argument as my
argument above about omnipotence; it asks you to contemplate
definitions rather than observe the world."
What you called a persuasive definition was a short argument starting
from a commonly used (partial) characterization of God. As I see it,
PF took the definition of "persuasive definition" implicit in that
and applied it to mathematics. You then clarified "persuasive
definition" so that it did not apply to all of mathematics -- but
that clarified version doesn't apply to PF's short argument either.
That's how it seems to me. If you're asking me how you should respond,
I would tell you to concede that one point and move on.
Alternatively, I think you should back up to his point that it's
impossible for us to distinguish between an omnipotent being ("God")
and super-powerful yet finite being ("Godzilla"). Show how that is
equivalent to proving 2+2=4 by defining 2+2=4.
Jim Burns
Mark Atherton
> There is no highest prime, not by definition (directly) but rather
> by a clear chain of reasoning from definitions. It's not a hard proof
> to understand: assume there are a finite number of primes; multiply
> them all together and add one; no prime divides this new number, so
> it is a new prime: contradiction, thus there are an infinite number
> of primes.
None of the primes *you already know about* divide this number. Either
it is a new prime, or it is composite and divisible by a new prime.
> (I'm pretty sure I left out some important and difficult
> steps, but the structure should be clear.)
Only one I saw.
Mark Atherton
Virgil
georg...@hotmail.com (George Dance) wrote:
Huxley supports evidence before belief in the physical world, but
what about the mathematical world? If (physical) evidence is requred
there, then should one believe *anything* mathematical?
My own view is that the logical consequences of an assumption, such
as the infinitude of primes following from the definition of natural
numbers, requires logical proof, not physical evidence.
If someone chooses to call that "persuasive definition", that is his
problem, and is irrelevant in issues of agnosticism.
Victor Eijkhout
> On the other hand, suppose my dog is named Rover and I say "Rover is
> brown." That's not a definition, since the word "Rover" already has a
> meaning. It's a statement of fact. Of course, to tell whether it's
> true or not, you have to go look at Rover.
Suppose Rover is actually brown, then the statement is true by
definition, since you defined some animal to be called "Rover". Any
properties of the-thing-labeled-Rover follow from the properties of
the-animal and the fact that you defined Rover to be the name of the
animal.
> In regard to "there is no highest prime number", that isn't a matter
> of definition. You can work out a proof of that fact.
Doesn't the statement follow from the definition of prime number? Once
you've defined a prime number, the fact that there is no largest follows
from, is implicit in, this definition.
(note: I don't mean any of the above, I'm just trying to imagine how the
the anselmist would answer.)
V.
--
email: lastname at cs utk edu
homepage: cs utk edu tilde lastname
fishfry
see...@for.addy (Victor Eijkhout) wrote:
> Dale Worley <wor...@dragon.ariadne.com> wrote:
>
> > On the other hand, suppose my dog is named Rover and I say "Rover is
> > brown." That's not a definition, since the word "Rover" already has a
> > meaning. It's a statement of fact. Of course, to tell whether it's
> > true or not, you have to go look at Rover.
>
> Suppose Rover is actually brown, then the statement is true by
> definition, since you defined some animal to be called "Rover". Any
> properties of the-thing-labeled-Rover follow from the properties of
> the-animal and the fact that you defined Rover to be the name of the
> animal.
>
> > In regard to "there is no highest prime number", that isn't a matter
> > of definition. You can work out a proof of that fact.
>
> Doesn't the statement follow from the definition of prime number? Once
> you've defined a prime number, the fact that there is no largest follows
> from, is implicit in, this definition.
>
No, not at all. How do you figure that? I define a prime number as a
positive whole number greater than 1, divisible only by itself and 1.
Then I tell you that I'm pretty sure that
957983459439538958854858484584794589437 is the largest prime number.
How are you going to refute that? With Euclid's proof, you can show
with pencil and paper that there is no largest prime number.
James Buddenhagen
> In article <1g5lvrt.txro7d1vsinejN%see...@for.addy>,
> see...@for.addy (Victor Eijkhout) wrote:
>
> > Dale Worley <wor...@dragon.ariadne.com> wrote:
> > Doesn't the statement follow from the definition of prime number? Once
> > you've defined a prime number, the fact that there is no largest follows
> > from, is implicit in, this definition.
> >
>
> No, not at all. How do you figure that? I define a prime number as a
> positive whole number greater than 1, divisible only by itself and 1.
> Then I tell you that I'm pretty sure that
> 957983459439538958854858484584794589437 is the largest prime number.
> How are you going to refute that? With Euclid's proof, you can show
> with pencil and paper that there is no largest prime number.
One doesn't need Euclid to see that 957983459439538958854858484584794589437
is divisible by 3 and hence not prime. So the largest prime must be some
other number.
Jim Buddenhagen
--
To reply copy jbud...@REMOVEtexas.net to address bar and edit out REMOVE
Dik T. Winter
> Jim Burns wrote:
> > There is no highest prime, not by definition (directly) but rather
> > by a clear chain of reasoning from definitions. It's not a hard proof
> > to understand: assume there are a finite number of primes; multiply
> > them all together and add one; no prime divides this new number, so
> > it is a new prime: contradiction, thus there are an infinite number
> > of primes.
>
> None of the primes *you already know about* divide this number. Either
> it is a new prime, or it is composite and divisible by a new prime.
No. The proof was complete. It was not "you know about" that was
mentioned. When you assume finitely many primes, and multiply *all*
those primes together you did not leave any one out. So the product
with 1 added to is is not divisible by *any* existing prime.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Dik T. Winter
> Dale Worley <wor...@dragon.ariadne.com> wrote:
...
> > In regard to "there is no highest prime number", that isn't a matter
> > of definition. You can work out a proof of that fact.
>
> Doesn't the statement follow from the definition of prime number? Once
> you've defined a prime number, the fact that there is no largest follows
> from, is implicit in, this definition.
That is false. Not all contexts where the definition of prime number
could make sense do have infinitely many prime numbers. So the
"infinitely many" can be shown in some contexts and not in other, hence
it is not the definition alone that leads to infinitely many primes.
Starting with the basic (but slightly wrong) definition of primes that
is best-known (and always cited by newspapers):
a prime is a number that is only divisible by 1 and itself
there are obvious contexts where this definition leads to no primes
at all. Real numbers for instance. But also *all* integers. The
above definition gives only infinitely many primes in the positive
integers. It fails for all integers, because 2 is divisible by 1,
-1, 2 and -2, and so is not prime. A better definition is:
a prime is a non-unit number that is only divisible by units and
conjugates of itself. (A unit is a number that is a divisor of 1,
a conjugate of a number you will get by multiplying the number by
a unit.)
This solves the problem with all integers (2 and -2 are both prime;
they are conjugates). Also this solves the problem in other contexts
(quadratic fields for instance), But when you use it with integers mod 6,
you will find that the only primes are 3, and the conjugate pair (2, 4).
[ 5 is a unit, and 2*5 = 4 and 4*5 = 2.]
The whole proof of the infinitude of primes depends on two things.
The first assumption is that there is at least one prime.
The second assumption is that the arithmetic rules for integers
apply, but they do *not* apply with the integers mod 6: 2*3 = 0.
So it is *not* the definition of primes that lead to an infinitude,
you need context for that.
Jesse F. Hughes
> Dale Worley <wor...@dragon.ariadne.com> wrote:
>
>> On the other hand, suppose my dog is named Rover and I say "Rover is
>> brown." That's not a definition, since the word "Rover" already has a
>> meaning. It's a statement of fact. Of course, to tell whether it's
>> true or not, you have to go look at Rover.
>
> Suppose Rover is actually brown, then the statement is true by
> definition, since you defined some animal to be called "Rover". Any
> properties of the-thing-labeled-Rover follow from the properties of
> the-animal and the fact that you defined Rover to be the name of the
> animal.
This is the weakest form of "true by definition" I've ever seen.
By this reasoning, any true sentence in which a proper name
(essentially[1]) occurs is true-by-definition. I've never seen anyone
that cares to use this term so loosely and trivially. Every statement
involving a proper noun is true by definition, regardless of whether
it is a contingent, possibly temporary, truth? Odd.
Once, my dog Mikhi was young. Evidently, he was young "by
definition". Today he is very old, again "by definition"?
Moreover, he may not be using "Rover" as a proper noun here,
appearances notwithstanding. Rover may be a defined term, meaning
"Dale's dog". In this case, do you still want to say that Rover is
brown "by definition"? Nothing in the definition entails that Rover
is brown, but only accidental features of the world as it is at this
instant make the sentence true.
Footnotes:
[1] Where "essentially" loosely means that the proper name occurs in
the sentence in such a way that its usage contributes to the truth of
the sentence -- so that there are other proper names which, if
substituted, would make the sentence false. Even this is probably a
smaller set than the set of sentences which you've just made
"true-by-definition".
--
"But he himself was not to blame for his vices. They grew out of a personal
defect in his mother. She did her best in the way of flogging him while an
infant... but, poor woman! she had the misfortune to be left-handed, and a
child flogged left-handedly had better be left unflogged." -- E.A. Poe
Eli
> Huxley supports evidence before belief in the physical world, but
> what about the mathematical world? If (physical) evidence is requred
> there, then should one believe *anything* mathematical?
I don't know about the entire mathematical world but the natural number in
particular, ARE based on physical evidence: the experience of counting
concrete objects. Amu definiiton that contradicts this experience would be
unacceptable.
Have a tolerable existence. Eli
Mark Atherton
> In article <6keca1-...@hudson.theathertons> Mark Atherton <n_z_w_n...@lnubb.pb.hx> writes:
> > Jim Burns wrote:
> > > There is no highest prime, not by definition (directly) but rather
> > > by a clear chain of reasoning from definitions. It's not a hard proof
> > > to understand: assume there are a finite number of primes; multiply
> > > them all together and add one; no prime divides this new number, so
> > > it is a new prime: contradiction, thus there are an infinite number
> > > of primes.
> >
> > None of the primes *you already know about* divide this number. Either
> > it is a new prime, or it is composite and divisible by a new prime.
>
> No. The proof was complete. It was not "you know about" that was
> mentioned. When you assume finitely many primes, and multiply *all*
> those primes together you did not leave any one out. So the product
> with 1 added to is is not divisible by *any* existing prime.
Agreed, but why must it be true that the resulting number is itself prime?
For example, assuming that the only primes are the first seven leads to:
2*3*5*7*11*13*17+1 = 510510+1 = 510511 = 17*26869
Here 17 is the prime not in the original list, and contradicts the
assumption that the original list of primes is complete. The possibility
that the resulting number is composite is included in the proof in
Silverman (A Friendly Introduction To Number Theory).
Mark Atherton
Daniel W. Johnson
> Agreed, but why must it be true that the resulting number is itself prime?
A contradiction leads to all manner of conclusions, both true and false.
If you hang on to the assumption that the original list of primes is
complete, it is not possible for 19*97*277 to be a prime factorization
of 510511.
--
Daniel W. Johnson
pano...@iquest.net
http://members.iquest.net/~panoptes/
039 53 36 N / 086 11 55 W
Mark Atherton
> Mark Atherton <n_z_w_n...@lnubb.pb.hx> wrote:
>
>
>>Agreed, but why must it be true that the resulting number is itself prime?
>
>
> A contradiction leads to all manner of conclusions, both true and false.
I am not sure what this means. Surely a contradiction (as in "proof by
contradiction") leads only to the conclusion that at least one of our
assumptions was incorrect.
> If you hang on to the assumption that the original list of primes is
> complete, it is not possible for 19*97*277 to be a prime factorization
> of 510511.
Again, agreed.
But Jim's post stated that if we multiply all of our finite list of
primes together and add one we get another prime. I don't understand why
that has to be true. My list of primes was an counterexample to this: a
finite list of primes whose product plus one is not prime.
Also, the proofs in elementary texts all (as far as I recall) include
the possibility that the product plus one is composite, with prime
factors not in our original finite list.
I appreciate that I am probably missing some subtle point here so please
enlighten me! :-)
Mark Atherton
James Buddenhagen
[snip]
> Agreed, but why must it be true that the resulting number is itself prime?
>
> For example, assuming that the only primes are the first seven leads to:
>
> 2*3*5*7*11*13*17+1 = 510510+1 = 510511 = 17*26869
510511 = 19*97*277
> Here 17 is the prime not in the original list, and contradicts the
> assumption that the original list of primes is complete. The possibility
> that the resulting number is composite is included in the proof in
> Silverman (A Friendly Introduction To Number Theory).
>
> Mark Atherton
Jim Buddenhagen
Virgil
Eli <eco...@mathstat.umass.edu> wrote:
Our actual experiences with counting in the physical world are
restricted to use of an infinitesimally small part of the set of
natural numbers, so most of what we say about the system of natural
numbers by analogy, not by experience. For example, we have no
compelling reason to believe that there are infinitely many "things"
in the physical universe, but we insist on infinitely many things in
our descriptions of vaarious numerical universes, and even
infinities sof different sizes.
Joona I Palaste
I don't understand this proof. Are you saying that if p is prime, then
p! + 1 must also be prime? That can't be what you are saying, because 5
is prime, but 5! + 1 = 120 + 1 = 121 is not prime, it's 11^2.
But it seems like you are trying to get a contradiction from the
assumption that p is prime and p! + 1 is composite. Please explain in
more detail so that stupid undergraduates like me can understand.
Thanks.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"B-but Angus! You're a dragon!"
- Mickey Mouse
Arturo Magidin
Joona I Palaste <pal...@cc.helsinki.fi> wrote:
>José Carlos Santos <jcsa...@fc.up.pt> scribbled the following:
>> George Dance wrote:
>>> <quote>
>>>
>>>>By that standard you could insist that anybody who says there's
>>>>no highest prime number can't be an agnostic. All of math is based
>>>>on persuasive definition, not evidence.
>>>
>>> </quote>
>>>
>>> Not being a mathematician, I don't know the best way to respond to
>>> this; so I was hoping that someone with more knowledge of the subject
>>> could address it.
>
>> It is *false* that the statement "there is no highest prime" is true
>> by definition. If some number p was the highest prime, then p! + 1 would
>> not be prime, since it would be greater. But, not being prime, it can
>> be written has a product of several prime numbers. If p' is one such
>> prime number, then p! + 1 is a multiple of p'. But then so is p! and
>> therefore 1 is a multiple of p', which is not possible, since every
>> prime number is greater than 1.
>
>I don't understand this proof. Are you saying that if p is prime, then
>p! + 1 must also be prime?
Not at all. He is saying that there is no prime p such that every
number strictly larger than p is composite.
Since the existence of a "highest prime" would imply the existence of
a prime p such that every number larger than p is not a prime (hence
composite), it follows that there is no "highest prime."
The argument is that if p were a prime with the property that for all
n, if n>p then n is composite, then we would have that p!+1 is
composite (by being larger than p), and so must be divisible by some
prime q. Since q>p implies q composite, we must have q<=p, and
therefore, q|(p!); since q also divides p!+1, you deduce that q
divides 1, which is impossible. The contradiction arose form assuming
that there existed a prime p such that every number strictly larger
than p is a composite.
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Christian Bau
Joona I Palaste <pal...@cc.helsinki.fi> wrote:
> José Carlos Santos <jcsa...@fc.up.pt> scribbled the following:
> > It is *false* that the statement "there is no highest prime" is true
> > by definition. If some number p was the highest prime, then p! + 1 would
> > not be prime, since it would be greater. But, not being prime, it can
> > be written has a product of several prime numbers. If p' is one such
> > prime number, then p! + 1 is a multiple of p'.
To make it slightly clearer: p' is a prime number, and p was assumed to
be the largest prime number. Therefore p >= p'. p! is the product of all
integers up to p, one of those integers is p', therefore p! is a
multiple of p'.
> > But then so is p!
which means that both p! and p! + 1 are multiples of p'
Dave Seaman
> Daniel W. Johnson wrote:
>> Mark Atherton <n_z_w_n...@lnubb.pb.hx> wrote:
>>>Agreed, but why must it be true that the resulting number is itself prime?
>> A contradiction leads to all manner of conclusions, both true and false.
> I am not sure what this means. Surely a contradiction (as in "proof by
> contradiction") leads only to the conclusion that at least one of our
> assumptions was incorrect.
>> If you hang on to the assumption that the original list of primes is
>> complete, it is not possible for 19*97*277 to be a prime factorization
>> of 510511.
> Again, agreed.
> But Jim's post stated that if we multiply all of our finite list of
> primes together and add one we get another prime. I don't understand why
> that has to be true. My list of primes was an counterexample to this: a
> finite list of primes whose product plus one is not prime.
No, it's not a counterexample, because your list was not a complete list
of primes. The conclusion that the new number is prime is derived from
that assumption.
Another way of putting it is that the new number is obviously composite
(because it is greater than 1 and is not prime, by hypothesis) but yet it
is not divisible by any prime (again, by hypothesis). That's just a
different way of getting a contradiction from the given assumptions.
From a contradictory set of assumptions there are lots of different ways
to derive contradictory statements.
> Also, the proofs in elementary texts all (as far as I recall) include
> the possibility that the product plus one is composite, with prime
> factors not in our original finite list.
Probably because it's easier to give that explanation than it is to head
off objections such as yours. That doesn't mean the objections are
well-founded.
> I appreciate that I am probably missing some subtle point here so please
> enlighten me! :-)
--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
Bill Dubuque
>Jim Burns wrote:
>> by a clear chain of reasoning from definitions. It's not a hard proof
>> to understand: assume there are a finite number of primes; multiply
>> them all together and add one; no prime divides this new number,
>
> None of the primes *you already know about* divide this number. Either
> it is a new prime, or it is composite and divisible by a new prime.
Jim's proof is in fact correct (but not as clear as it could be).
Your criticism applies only to an alternative presentation of
Euclid's proof, namely: given a finite set S of "known" primes
there exists a prime not in S, i.e. a "new" prime.
However Jim's proof, being by contradiction, merely needs to
deduce a contradiction from the hypothesis that there are only
finitely many primes. The simplest way to do such is Euclid's:
show that there exists an integer N > 1 with no prime factor,
which contradicts: every integer N > 1 has a prime factor,
a theorem already known (its trivial proof follows immediately
by induction and the definition of prime). Jim's proof deduces
a contradiction to a minor variation of this theorem, namely:
every integer N > 1 with no _proper_ prime factor is prime.
Now since we've shown N has no prime factors, it certainly
has no _proper_ prime factors, so N is prime by the theorem.
But any prime has itself as a prime factor, a contradiction
[alternatively note that the prime N isn't equal to any of
the given primes since it is not divisible by any of them].
This variation is not as clear as Euclid's. Indeed, above
we see how its extra subtlety led to your misinterpretation.
Of course, by their very nature, proofs by contradiction may
be confusing at first glance - especially when negating the
conclusion easily yields statements contradicting hardwired
intuitions about a fundamental structure like the integers.
Finally, in another post, after noting that sequences of
integers generated by Euclid's proof needn't all be prime,
e.g. 1 + 2 3 5 7 11 13 = 30031 = 59 509
you ask why this is not a counterexample to Jim's proof.
That's because Jim's proof, by contradiction, assumes as
hypothesis that there are only a finite number of primes
(e.g. 2,3,5,7,11,13 above). Since this doesn't hold true
for the integers, neither need any consequences of such.
Thus although Jim's proof does conclude that 30031 is
prime in the hypothetical structure "the integers with
only 2,3,5,7,11,13 as primes", it does not reach the
same conclusion for the integers alone, since the extra
hypothesis is quite crucial to the success of the proof.
There are countless minor variations of Euclid's proof.
For example, instead of deducing N prime, Jim's proof
could just as well have deduced N = 1, since one is
the only positive integer without any prime factors.
Since we know the integers so intimately, we've many
well-known theorems as targets for a contradiction.
Again, such is the nature of proofs by contradiction.
By the way, Euclid's original proof may be found online at
http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html
-Bill Dubuque
Dik T. Winter
> Dik T. Winter wrote:
...
> > No. The proof was complete. It was not "you know about" that was
> > mentioned. When you assume finitely many primes, and multiply *all*
> > those primes together you did not leave any one out. So the product
> > with 1 added to is is not divisible by *any* existing prime.
>
> Agreed, but why must it be true that the resulting number is itself prime?
By definition of the term prime. (*)
> For example, assuming that the only primes are the first seven leads to:
>
> 2*3*5*7*11*13*17+1 = 510510+1 = 510511 = 17*26869
>
> Here 17 is the prime not in the original list, and contradicts the
> assumption that the original list of primes is complete.
But the conclusion that 510511 is a prime is already a contradiction;
it is not on the original list. Why factor?
(*) Let's assume the following definitions and conclusions in the positive
integers:
1. A number is prime when it is only divisible by 1 or the number itself.
2. When a number is not prime, it is either 1 or divisible by a prime.
3. Let the list of all primes be [2,3,5,7,11,13,17].
4. Multiply the primes and add 1 to get n (= 510511).
5. This number can not be divided by any of the primes given in [3], so
by [2] it is a prime.
6. Contradiction...
So there is a false assumption, and it must be [3].
Mark Atherton
Okay, I see what you mean.
What's more, I think I see why proofs in most texts include the
possibility that the number obtained is composite. Silverman (since
that's what I've got in front of me) only starts with a *finite* list of
primes, not the assumption that the list is *complete*. He then goes on
to show that any finite list can have another prime added to it.
Similarly http://mathworld.wolfram.com/EuclidsTheorems.html assumes a
finite list of consecutive primes, again not assumed to be complete.
Thanks, Dik.
Mark Atherton
Mark Atherton
> Mark Atherton <n_z_w_n...@lnubb.pb.hx> wrote:
>
>>Jim Burns wrote:
>>
>>>There is no largest prime, not by definition (directly) but rather
>>>by a clear chain of reasoning from definitions. It's not a hard proof
>>>to understand: assume there are a finite number of primes; multiply
>>>them all together and add one; no prime divides this new number,
>>>so it's a new prime: contradiction
>>
>>None of the primes *you already know about* divide this number. Either
>>it is a new prime, or it is composite and divisible by a new prime.
>
>
> Jim's proof is in fact correct (but not as clear as it could be).
> Your criticism applies only to an alternative presentation of
> Euclid's proof, namely: given a finite set S of "known" primes
> there exists a prime not in S, i.e. a "new" prime.
snip
> By the way, Euclid's original proof may be found online at
> http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html
>
> -Bill Dubuque
Thanks, Bill, I think I understand now. :-)
Mark Atherton
Joona I Palaste
> In article <br2sms$o7q$1...@oravannahka.helsinki.fi>,
> Joona I Palaste <pal...@cc.helsinki.fi> wrote:
>>José Carlos Santos <jcsa...@fc.up.pt> scribbled the following:
>>> George Dance wrote:
>>>> <quote>
>>>>
>>>>>By that standard you could insist that anybody who says there's
>>>>>no highest prime number can't be an agnostic. All of math is based
>>>>>on persuasive definition, not evidence.
>>>>
>>>> </quote>
>>>>
>>>> Not being a mathematician, I don't know the best way to respond to
>>>> this; so I was hoping that someone with more knowledge of the subject
>>>> could address it.
>>
>>> It is *false* that the statement "there is no highest prime" is true
>>> by definition. If some number p was the highest prime, then p! + 1 would
>>> not be prime, since it would be greater. But, not being prime, it can
>>> be written has a product of several prime numbers. If p' is one such
>>> prime number, then p! + 1 is a multiple of p'. But then so is p! and
>>> therefore 1 is a multiple of p', which is not possible, since every
>>> prime number is greater than 1.
>>
>>I don't understand this proof. Are you saying that if p is prime, then
>>p! + 1 must also be prime?
> Not at all. He is saying that there is no prime p such that every
> number strictly larger than p is composite.
I thought that must not have been what he was saying. (I.e. that if p
was prime, so was p! + 1.)
> Since the existence of a "highest prime" would imply the existence of
> a prime p such that every number larger than p is not a prime (hence
> composite), it follows that there is no "highest prime."
> The argument is that if p were a prime with the property that for all
> n, if n>p then n is composite, then we would have that p!+1 is
> composite (by being larger than p), and so must be divisible by some
> prime q. Since q>p implies q composite, we must have q<=p, and
> therefore, q|(p!); since q also divides p!+1, you deduce that q
> divides 1, which is impossible. The contradiction arose form assuming
> that there existed a prime p such that every number strictly larger
> than p is a composite.
OK... q divides p!+1 because we just said so (it's how we chose q), and
q divided p!, because it's a prime number bigger than 1 and smaller
than p, so it's bound to appear as a factor of p! (every such number,
prime or composite, does). But how do you get the conclusion that q
should divide 1? This is the only thing I'm still not understanding.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"I am lying."
- Anon
Toni Lassila
<n_z_w_n...@lnubb.pb.hx> wrote:
>What's more, I think I see why proofs in most texts include the
>possibility that the number obtained is composite. Silverman (since
>that's what I've got in front of me) only starts with a *finite* list of
>primes, not the assumption that the list is *complete*.
Wasn't this exact same topic covered a few weeks earlier, with exactly
the same arguments? One side thinks the proof must be written as X and
the other side that it must be written as Y and both sides agree the
other side should go back to freshman algebra class.
Christian Bau
q divides p! and q divides p! + 1. Therefore it divides the difference
(p! + 1) - p! = 1.
Mark Atherton
> On Tue, 09 Dec 2003 06:53:13 +0000, Mark Atherton
> <n_z_w_n...@lnubb.pb.hx> wrote:
>
>
>>What's more, I think I see why proofs in most texts include the
>>possibility that the number obtained is composite. Silverman (since
>>that's what I've got in front of me) only starts with a *finite* list of
>>primes, not the assumption that the list is *complete*.
>
>
> Wasn't this exact same topic covered a few weeks earlier, with exactly
> the same arguments?
Don't recall it. Can't find it on Google.
> One side thinks the proof must be written as X and
> the other side that it must be written as Y and both sides agree the
> other side should go back to freshman algebra class.
I'm not so stupid as to suggest that Dik T. Winter go back to basic
algebra (shouldn't that be number theory?) - I'll leave that to JSH. To
quote myself:
> I appreciate that I am probably missing some subtle point here so please enlighten me!
>
> Mark Atherton
Mark Atherton
Fred Galvin
> (*) Let's assume the following definitions and conclusions in the positive
> integers:
>
> 1. A number is prime when it is only divisible by 1 or the number itself.
> 2. When a number is not prime, it is either 1 or divisible by a prime.
> 3. Let the list of all primes be [2,3,5,7,11,13,17].
> 4. Multiply the primes and add 1 to get n (= 510511).
> 5. This number can not be divided by any of the primes given in [3], so
> by [2] it is a prime.
> 6. Contradiction...
> So there is a false assumption, and it must be [3].
Yes, but why did you include the clause "When a number is not prime"
in [2]? If you omit that, you get a simpler proof:
1. A number is prime when it is only divisible by 1 or the number itself.
2. Every number is either 1 or divisible by a prime.
3. Let the list of all primes be [2,3,5,7,11,13,17].
4. Multiply the primes and add 1 to get n (= 510511).
5. This number can not be divided by any of the primes given in [3],
and it is not 1.
6. Contradiction...
The question, whether 510511 is prime or composite, does not arise.
Joona I Palaste
OK, *now* I understand. Thanks for the explanation.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"To doo bee doo bee doo."
- Frank Sinatra
Toni Lassila
<n_z_w_n...@lnubb.pb.hx> wrote:
>Toni Lassila wrote:
>> On Tue, 09 Dec 2003 06:53:13 +0000, Mark Atherton
>> <n_z_w_n...@lnubb.pb.hx> wrote:
>>
>>>What's more, I think I see why proofs in most texts include the
>>>possibility that the number obtained is composite. Silverman (since
>>>that's what I've got in front of me) only starts with a *finite* list of
>>>primes, not the assumption that the list is *complete*.
>>
>> Wasn't this exact same topic covered a few weeks earlier, with exactly
>> the same arguments?
>
>Don't recall it. Can't find it on Google.
<http://groups.google.com/groups?selm=87llqfktp5.fsf%40nonospaz.fatphil.org>
I've heard of long-running Usenet threads but this particular argument
must have been going on since Euclid himself so it must be some kind
of record.
>> I appreciate that I am probably missing some subtle point here so please enlighten me!
The problem often is that even the simplest proof has one person state
it "elegantly" but so that the reader cannot understand it or
misunderstands it, then somebody corrects the elegant proof to be more
illustrative at which point a third person corrects the second person
but makes a mistake so a fourth person then corrects the third person
and so on...
The definition of rigorous mathematics is, when given a solution to a
problem one understands the solution but no longer understands the
problem.
Dik T. Winter
> On Tue, 9 Dec 2003, Dik T. Winter wrote:
>
> > (*) Let's assume the following definitions and conclusions in the positive
> > integers:
> >
> > 1. A number is prime when it is only divisible by 1 or the number itself.
> > 2. When a number is not prime, it is either 1 or divisible by a prime.
> > 3. Let the list of all primes be [2,3,5,7,11,13,17].
> > 4. Multiply the primes and add 1 to get n (= 510511).
> > 5. This number can not be divided by any of the primes given in [3], so
> > by [2] it is a prime.
> > 6. Contradiction...
> > So there is a false assumption, and it must be [3].
>
> Yes, but why did you include the clause "When a number is not prime"
> in [2]? If you omit that, you get a simpler proof:
But my goal was not the simplest proof. Only a proof where
"510511 is a prime" is an immediately valid conclusion.
Jose Carlos Santos
> I thought that must not have been what he was saying. (I.e. that if p
> was prime, so was p! + 1.)
I just cannot understand how can you possibly have thought that I was
saying that.
> OK... q divides p!+1 because we just said so (it's how we chose q), and
> q divided p!, because it's a prime number bigger than 1 and smaller
> than p, so it's bound to appear as a factor of p! (every such number,
> prime or composite, does). But how do you get the conclusion that q
> should divide 1? This is the only thing I'm still not understanding.
Since q divides p! + 1, you can write p! + 1 as q.m for some integer m and
since q divides p! you can write p! as q.n for some integer n. Therefore
1 = (p! + 1) - p! = q.m - q.n = q.(m - n).
QED
Best regards,
Jose Carlos Santos
Damien
For starters, it's not true that p! + 1 is prime if p is prime, since
this can be blatantly shown to be false for p = 5. (p!+1) = 121 = 11 *
11
The original claim was for the product of all PRIMEs between 1 and p
[which I'll call f(p)]. And remember in the following that p is the
largest prime, so there can be no prime greater that p.
So the statement is that f(p)+1 must be a prime. The counterexample is
that if f(p)+1 is composite, it must have a prime factor q.
Now, this prime factor must have been included in the f(p) function,
so we have the following being true:
q divides f(p) from the definition of f(p)
q divides f(p)+1 from our assertion that q exists
if q divides f(p) and f(p)+1 then it must divide (f(p)+1) - f(p).
Which means that q must divide 1. There's our contradiction. So f(p)+1
cannot have any prime factors.
Joona I Palaste
> Joona I Palaste <pal...@cc.helsinki.fi> wrote in message news:<br3u17$bqa$2...@oravannahka.helsinki.fi>...
>> I thought that must not have been what he was saying. (I.e. that if p
>> was prime, so was p! + 1.)
> I just cannot understand how can you possibly have thought that I was
> saying that.
I misread your proof. You said that if p is the largest prime, then all
numbers >p are composite, which would mean that all the prime factors
of p! + 1 are <=p. I misread that as claiming that if p is prime, then
so is p! + 1.
>> OK... q divides p!+1 because we just said so (it's how we chose q), and
>> q divided p!, because it's a prime number bigger than 1 and smaller
>> than p, so it's bound to appear as a factor of p! (every such number,
>> prime or composite, does). But how do you get the conclusion that q
>> should divide 1? This is the only thing I'm still not understanding.
> Since q divides p! + 1, you can write p! + 1 as q.m for some integer m and
> since q divides p! you can write p! as q.n for some integer n. Therefore
> 1 = (p! + 1) - p! = q.m - q.n = q.(m - n).
Does the . mean multiplication? This is quite a nice answer. Thanks.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"'It can be easily shown that' means 'I saw a proof of this once (which I didn't
understand) which I can no longer remember'."
- A maths teacher
Virgil
Toni Lassila <to...@nukespam.org> wrote:
The original Euclid proof was, I believe, of the form that any
(finite) list of primes is incomplete, and did not involve proof by
contradiction.
Both the "incompleteness" proof and the contradiction proof are
valid, but as a matter of style, many prefer to avoid proofs by
contradiction when it is as easy to do as in this case.
A similar situation (and a similar argument over which proof is
best) arises in Cantor's "diagonal" proof that there is no
surjection from the integers to the reals. Cantor's original version
shows only that any list (image of the naturals) of reals is
incomplete, but many people recast the proof to state it as a proof
by contradiction.
Now there probably do exist proofs by contradiction for which no
equally simple direct proof is known, so proof by contradiction
remains a viable technique, but, as a matter of style, shouldn't it
be avoded when it is so easy to do so?
Toni Lassila
>The original Euclid proof was, I believe, of the form that any
>(finite) list of primes is incomplete, and did not involve proof by
>contradiction.
>
>Both the "incompleteness" proof and the contradiction proof are
>valid, but as a matter of style, many prefer to avoid proofs by
>contradiction when it is as easy to do as in this case.
It seems many proofs can be stated as pairs of of incompleteness-
contradiction proofs - in effect it's the exactly same construction.
For another example Google for the recent discussion over the proof
that any infinite set of reals that sums to a finite value must have
at most countably many non-zero elements.
>A similar situation (and a similar argument over which proof is
>best) arises in Cantor's "diagonal" proof that there is no
>surjection from the integers to the reals. Cantor's original version
>shows only that any list (image of the naturals) of reals is
>incomplete, but many people recast the proof to state it as a proof
>by contradiction.
And some people recast it as evidence of a massive conspiracy by
mathematicians, but the less spoken about that the better.
>Now there probably do exist proofs by contradiction for which no
>equally simple direct proof is known
I tried looking for a simple proof that involved proof by
contradiction and about the first thing I could find involved proving
that 0 < 1:
Since we can prove 0 =/= 1 based on the axioms of reals and 1 < 0
leads to a contradiction because of (again by the axioms of reals):
1 < 0 = > 1 + (-1) < 0 + (-1) => 0 < -1 => 0 < (-1)(-1) => 0 < 1
we conclude that the only option is 0 < 1. Maybe this doesn't count as
a true proof by contradiction but rather as "exhausting all other
options"? Still, it relies on a contradiction to prove a certain case
impossible.
Jose Carlos Santos
> > 1 = (p! + 1) - p! = q.m - q.n = q.(m - n).
>
> Does the . mean multiplication? This is quite a nice answer. Thanks.
Yes, . means multiplication. I thought that that was a kind of universal
notation.
Joona I Palaste
Coming from a programming background, I am more used to reading * as
multiplication.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"No, Maggie, not Aztec, Olmec! Ol-mec!"
- Lisa Simpson
Jonathan Miller
news:184bc135.03121...@posting.google.com...
> Yes, . means multiplication. I thought that that was a kind of universal
> notation.
The only universal is that there are no universals.
Jon Miller
John Savard
wrote, in part:
>Yes, . means multiplication. I thought that that was a kind of universal
>notation.
No, because the . is too small and too low. A higher, bigger dot means
multiplication.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
Jose Carlos Santos
> >Yes, . means multiplication. I thought that that was a kind of universal
> >notation.
>
> No, because the . is too small and too low. A higher, bigger dot means
> multiplication.
Yes, but AFAIK that cannot be obtained in ASCII. The closest thing there is
is ".".
Phil Carmody
> On 10 Dec 2003 01:01:23 -0800, jcsa...@fc.up.pt (Jose Carlos Santos)
> wrote, in part:
>
> >Yes, . means multiplication. I thought that that was a kind of universal
> >notation.
>
> No, because the . is too small and too low. A higher, bigger dot means
> multiplication.
Not universally. English typographical preference used to be for
representing the decimal separator by such a raised dot.
Phil
--
Unpatched IE vulnerability: DNSError folder disclosure
Description: Gaining access to local security zones
Reference: http://msgs.securepoint.com/cgi-bin/get/bugtraq0306/52.html
Virgil
So many computer languages use "*", that it has almost become the
newsgroup defacto standard for multiplications. It is certainly less
liable to be misinterpreted than ".".
Jose Carlos Santos
> So many computer languages use "*", that it has almost become the
> newsgroup defacto standard for multiplications. It is certainly less
> liable to be misinterpreted than ".".
OK, I think that I'll use it from now on.