Needlessly indirect proofs
Aatu Koskensilta
For some reason many people seem to have a peculiar fondness for
pointlessly indirect proofs. A more-or-less canonical example is
Euclid's proof that there are infinitely many primes. We often see this
proof presented starting with a "Suppose there are only finitely many
primes." and concluding with a triumphant "A contradiction!". Of course,
no actual use is made in the proof of the assumption that there are only
finitely many primes. Is there some explanation for this curious
phenomenon, that people should prefer proofs that are, from a logical
and mathematical point of view, simply needlessly convoluted?
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Marshall
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> finitely many primes. Is there some explanation for this curious
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
It is not a preference so much as the default behavior. Simplicity is
a very advanced virtue; it takes a long time for an individual to
get there in his or her field.
Indeed, we are so used to this state of affairs that sometimes
simpler approaches aren't even investigated merely because
of the presumption that the solution will be difficult, complicated,
whatever.
Marshall
Aatu Koskensilta
> It is not a preference so much as the default behavior. Simplicity is
> a very advanced virtue; it takes a long time for an individual to
> get there in his or her field.
Well, we're not talking about inelegant proofs versus elegant proofs or
any such subtle distinction. I once presented a proof, during exercise
session, of the theorem that every computable function is computed by
infinitely many different register machine programs. A student asked,
"Yes, but shouldn't we start by assuming there aren't infinitely many
programs for every function?" What is one to say? Why on earth would
anyone think every proof must be an indirect proof? We can imagine any
number of pointless validity preserving transformations on proofs but
this seems to be the only one many find irresistible.
PS. Another direct proof people just love to make indirect is that of
Cantor's theorem.
Jan Burse
> Marshall<marshal...@gmail.com> writes:
>
>> It is not a preference so much as the default behavior. Simplicity is
>> a very advanced virtue; it takes a long time for an individual to
>> get there in his or her field.
>
> Well, we're not talking about inelegant proofs versus elegant proofs or
> any such subtle distinction. I once presented a proof, during exercise
> session, of the theorem that every computable function is computed by
> infinitely many different register machine programs. A student asked,
> "Yes, but shouldn't we start by assuming there aren't infinitely many
> programs for every function?" What is one to say? Why on earth would
> anyone think every proof must be an indirect proof? We can imagine any
> number of pointless validity preserving transformations on proofs but
> this seems to be the only one many find irresistible.
>
> PS. Another direct proof people just love to make indirect is that of
> Cantor's theorem.
>
Well it is the virtue of such proofs, that everything we know and
want to know lands on the left hand side of our deductive cognitive
system. And all we have to is reduce this to nothing, i.e. to false,
eh voila we are done. So the pattern is that we proof:
G, ~A |- f
And conclude from this:
G |- A
The conclusion is only valid in classical logic, in intuitionistic
logic, we would only have ended with proving G |- ~~A. But lets
put aside this distinctions, and take a closer look at the virtue
of this kind of "indirect" proofs, or refutation based proofs, as
they are also called.
Well when we have done this we have seeded our thinking soup. And
we might then go to work and stir the soup. Someone clever once saw
that when G, ~A can be brought to clausal form, then only one
combination rule is enough, the resolution step. So the soup will
start boiling and the premisses will recombine to generate new premisses
until at one point the f will be generated. And then we
will have shown:
G, ~A |- B1
G, ~A, B1 |- B2
G, ~A, B1, B2 |- B3
...
G, ~A, B1, .., Bn |- f
Which can be reduced to (for example by applying a form of cut rule):
G, ~A |- f
It can be shown that resultion step and clausal form is not
necessary, the soup can also work with other rules. Also answer
extraction would be an issue. But the attraction here is that the
goal is reached by reducing it to false. So the hope is that
the final B1, ..., Bn, f form a chain which give us the impression
of reducing the problem more and more. Given that f is the
ultimate reduction, we would assign the weight zero to it.
With some weighting in mind and the meta hypothesis of the
decreasing chain we go to work, and circle out intermediate
results that do not fit this schema. So when a resolvent pops
up, that looks too heavy, we put it on a waiting list and first
consider the resolvents where the weight has been reduced. So
our search is like a gradient search, following the hill down
to the valley.
Of course sometime we are disappointed because we land in the
wrong valley...
Bye
Chris Menzel
<aatu.kos...@uta.fi> said:
> Marshall <marshal...@gmail.com> writes:
>
>> It is not a preference so much as the default behavior. Simplicity is
>> a very advanced virtue; it takes a long time for an individual to
>> get there in his or her field.
>
> Well, we're not talking about inelegant proofs versus elegant proofs
> or any such subtle distinction. I once presented a proof, during
> exercise session, of the theorem that every computable function is
> computed by infinitely many different register machine programs. A
> student asked, "Yes, but shouldn't we start by assuming there aren't
> infinitely many programs for every function?" What is one to say? Why
> on earth would anyone think every proof must be an indirect proof? We
> can imagine any number of pointless validity preserving
> transformations on proofs but this seems to be the only one many find
> irresistible.
>
> PS. Another direct proof people just love to make indirect is that of
> Cantor's theorem.
The parallels with the usual proof of Russell's paradox can be
instructive, or at least sorta interesting to observe, in this case.
Aatu Koskensilta
In a general sort of way, sure -- Russell arrived at his paradox by
applying Cantor's construction to the identity mapping on the universal
set. These days the paradox is usually presented as a proof that there's
no universal set and since this is a negative result a direct proof
necessarily proceeds by way of deriving a contradiction. I'm unsure
whether you think this has any bearing on the question why people seem
naturally inclined to prefer pointlessly indirect proofs.
MoeBlee
> we're not talking about inelegant proofs versus elegant proofs or
> any such subtle distinction.
I wonder though whether you agree that it's okay to present an
indirect proof that is just basically modus tollens. For example:
Suppose we want to prove some P -> Q.
We assume P. Then we say, "toward a contradiction, suppose ~Q". Then
we get a contradiction, and we infer P -> Q (or even just day "done",
or just end, or whatever, upon getting the contradiction). (Same thing
mutatis mutandis for showing P -> ~Q.)
That seems okay to me and not ostentatious.
(The alternative would be to say you're proving ~Q -> ~P then taking
the contrapositive (maybe even by then assuming P, toward a
contradiction!), which is not much less longwinded than saying
"Suppose P and suppose ~Q" and getting a contradiction.)
I think people like to throw in the negation at the start because it
immediately gives them an extra premise.If I'm in a hurry and I just
want to verify something, I'll throw in the negation so that I have
plenty of ammo to get the job done (my set of premises being an
embarrassment of riches, as it were). Then, later, I might rewrite the
argument, if I didn't really need to use the negation assumption.
One regret I have is that before I started my project of a notebook
that systematically proves each theorem starting from the axioms, I
wish I had kept in mind to prove constructively where a constructive
proof is available and not too difficult to come up with at that point
in the sequence of theorems. As a matter of taste (if not more) I've
come to prefer having a constructive proof when available.
MoeBlee
Chris Menzel
<aatu.kos...@uta.fi> said:
> Chris Menzel <cme...@remove-this.tamu.edu> writes:
>
>> On Mon, 23 Aug 2010 18:49:31 +0300, Aatu Koskensilta
>> <aatu.kos...@uta.fi> said:
>>
>>> PS. Another direct proof people just love to make indirect is that of
>>> Cantor's theorem.
>>
>> The parallels with the usual proof of Russell's paradox can be
>> instructive, or at least sorta interesting to observe, in this case.
>
> In a general sort of way, sure -- Russell arrived at his paradox by
> applying Cantor's construction to the identity mapping on the universal
> set. These days the paradox is usually presented as a proof that there's
> no universal set and since this is a negative result a direct proof
> necessarily proceeds by way of deriving a contradiction. I'm unsure
> whether you think this has any bearing on the question why people seem
> naturally inclined to prefer pointlessly indirect proofs.
None that I can see. My comment was meant only to suggest that there
can be pedagogically sound reasons for proving Cantor's Theorem
indirectly and, hence, that the indirect approach in this case (and
perhaps others, for parallel reasons) persists at least to some extent
for reasons other than the "natural inclination" in question.
quasi
wrote:
>Aatu Koskensilta schrieb:
>> Marshall<marshal...@gmail.com> writes:
>>
>>> It is not a preference so much as the default behavior. Simplicity is
>>> a very advanced virtue; it takes a long time for an individual to
>>> get there in his or her field.
>>
>> Well, we're not talking about inelegant proofs versus elegant proofs or
>> any such subtle distinction. I once presented a proof, during exercise
>> session, of the theorem that every computable function is computed by
>> infinitely many different register machine programs. A student asked,
>> "Yes, but shouldn't we start by assuming there aren't infinitely many
>> programs for every function?" What is one to say? Why on earth would
>> anyone think every proof must be an indirect proof? We can imagine any
>> number of pointless validity preserving transformations on proofs but
>> this seems to be the only one many find irresistible.
>>
>> PS. Another direct proof people just love to make indirect is that of
>> Cantor's theorem.
>>
>
>Well it is the virtue of such proofs, that everything we know and
>want to know lands on the left hand side of our deductive cognitive
>system. And all we have to is reduce this to nothing, i.e. to false,
>eh voila we are done. So the pattern is that we proof:
>
> G, ~A |- f
>
>And conclude from this:
>
> G |- A
The above gets to the heart of the matter.
The indirect method allows a _stronger_ hypothesis -- not just G but
rather, G _and_ ~A, as well as more flexibility for the target, in
that we no longer have to prove A, but rather _any_ contradiction (of
which A would be only one possibility).
Hence, when it's difficult to see a direct proof of "G implies A",
most of us, at least in discovery mode, will switch to the indirect
approach. Of course, once the contradiction is obtained, it's often
easy to restructure it as a direct proof, and I agree that a direct
proof is preferable, provided it's at least as clear and elegant as
the indirect proof.
However, in the case of the proof that there are infinitely many
primes, I feel the usual proof by contradiction is both clearer and
more elegant.
I think it _is_ true that novice students, once they get a taste of
proof by contradiction, tend to overuse it. For one thing, it's
psychologically more fun to prove something is impossible than just to
prove something. Also, students are lazy -- once they get a
contradiction, they're done. They don't want to spend the time, even
if only a few minutes, to restructure it as a direct proof. But most
higher level students and professionals know better, and will usually
try to make the most natural choice.
quasi
Aatu Koskensilta
> However, in the case of the proof that there are infinitely many
> primes, I feel the usual proof by contradiction is both clearer and
> more elegant.
Why is that? How is it more clear or elegant to take a direct proof of
P, prefix it with "Suppose not P" and finish with a triumphant "A
contradiction!", instead of just giving the direct proof?
> But most higher level students and professionals know better, and will
> usually try to make the most natural choice.
Many high level students and professionals who should know better still
peddle pointlessly indirect proofs for no good reason whatever. For
some, an indirect proof is the natural choice. I'm wondering why.
Aatu Koskensilta
> My comment was meant only to suggest that there can be pedagogically
> sound reasons for proving Cantor's Theorem indirectly and, hence, that
> the indirect approach in this case (and perhaps others, for parallel
> reasons) persists at least to some extent for reasons other than the
> "natural inclination" in question.
I'm afraid you'll have to spell out this suggestion. Why should we prove
Cantor's theorem indirectly? If all we care about is demonstrating the
usefulness of indirect proof we have many stock examples at hand,
e.g. the irrationality of the square root of two. In the indirect proof
of Cantor's theorem we assume given a function of specific sort and
derive a contradiction. This is not, on the face of it, analogous in
logical structure to Russell's paradox.
quasi
<aatu.kos...@uta.fi> wrote:
>quasi <qu...@null.set> writes:
>
>> However, in the case of the proof that there are infinitely many
>> primes, I feel the usual proof by contradiction is both clearer and
>> more elegant.
>
>Why is that?
This is art, not science. But in this case, I really do prefer the
proof by contradiction. I see it as elegant. A direct proof in this
case feels forced and artificial.
>How is it more clear or elegant to take a direct proof of
>P, prefix it with "Suppose not P" and finish with a triumphant "A
>contradiction!", instead of just giving the direct proof?
In a way, the direct proof hides (or actually defers) the
contradiction. In the direct proof, one doesn't assume that the list
of primes is finite. One starts with an arbitrary finite nonempty set
of primes and shows that there must exist a new prime not in the set.
Which means any finite set of primes can always be extended to a
strictly larger finite set of primes. But now tell me why that means
there must be infinitely many primes, without using the word
"contradiction"? You probably can find a way, appealing to some axiom
or other, but that assumes the audience is aware of and accepts that
axiom, and understands its use.
quasi
Arturo Magidin
> On Mon, 23 Aug 2010 20:48:53 +0300, Aatu Koskensilta
>
> >quasi <qu...@null.set> writes:
>
> >> However, in the case of the proof that there are infinitely many
> >> primes, I feel the usual proof by contradiction is both clearer and
> >> more elegant.
>
> >Why is that?
>
> This is art, not science. But in this case, I really do prefer the
> proof by contradiction. I see it as elegant. A direct proof in this
> case feels forced and artificial.
But it's the same argument! The only difference is that in the "proof
by contradiction" you add a line at the beginning and add a line at
the end.
> >How is it more clear or elegant to take a direct proof of
> >P, prefix it with "Suppose not P" and finish with a triumphant "A
> >contradiction!", instead of just giving the direct proof?
>
> In a way, the direct proof hides (or actually defers) the
> contradiction.
How so?
> In the direct proof, one doesn't assume that the list
> of primes is finite. One starts with an arbitrary finite nonempty set
> of primes and shows that there must exist a new prime not in the set.
... and in the "indirect proof" one does exactly the same, except that
one sticks a big neon yellow sticker on the set that says "THIS IS THE
SET OF ALL PRIMES".
> Which means any finite set of primes can always be extended to a
> strictly larger finite set of primes. But now tell me why that means
> there must be infinitely many primes, without using the word
> "contradiction"?
Because there are more primes than any given finite number; that's the
definition of "there are infinitely many primes".
> You probably can find a way, appealing to some axiom
> or other, but that assumes the audience is aware of and accepts that
> axiom, and understands its use.
I can see you arguing that the "indirect proof" is easier to digest
for some students. What mystifies me (and presumably Aatu) is the
assertion that it is "more elegant"; the reason it mystifies me is
that it is *exactly the same proof*, with a line added at the
beginning and a line added at the end. The "assumption" that the list/
set contains all primes is not used untill the "last line", which is
also added.
But perhaps, as with the meaning of the word "conjecture", we just
have different understandings of the word "elegance".
--
Arturo Magidin
Jan Burse
> Why is that? How is it more clear or elegant to take a direct proof of
> P, prefix it with "Suppose not P" and finish with a triumphant "A
> contradiction!", instead of just giving the direct proof?
An indirect proof is not a direct proof prefixed with the
negation of the goal, leading to a contradiction. Look what
you say, its impossible:
The direct proof would be:
G |- P
Prefix with suppose not P, well this could eventually be:
G, ~P |- P
But finish with a contradiction, I cannot make no head nor
tail what you mean by this. Replace the conclusion? Are
your steps to be taken as proof transformations? If yes, how?
In an indirect proof, the G means the background theory,
for example arithmetic. So an indirect proof, according
to my definition, is a proof:
G, ~P |- f
A direct proof would be, again G should denote the given
background theory:
G |- P
The shape of both proofs can or cannot have something in
common.
But we would need to clarify more what a direct proof
would mean. What is a "proper" direct proof? An intuitionistic
direct proof?
Bye
P.S.: Lets consider direct proofs that are not necessarely
proper. For every indirect proof there exists a direct
proof. And for every direct proof there exists an indirect
proof.
Proof:
=> Given G, ~P |- f, then we can derive G |- P,
we can use ex falso quodlibet and clavius law:
G, ~P |- f
---------- (Ex falso quodlibet)
G, ~P |- P
---------- (Clavius law)
G |- P
<= Given G |- P, then we can derive G, ~P |- f,
we can use identity and modus ponens:
---------------- (Id)
G |- P P -> f |- P -> f
------------------------------------- (MP)
G, P -> f |- f
Intuitionism does not have Clavius law, only Ex falso
quodlibet. So the path (=>) as I showed it would not be
accepted by an Intuitionist in general. Classical logic
has Clavius law and Ex falso quodlibet.
Jan Burse
>
>
> Intuitionism does not have Clavius law, only Ex falso
> quodlibet. So the path (=>) as I showed it would not be
> accepted by an Intuitionist in general. Classical logic
> has Clavius law and Ex falso quodlibet.
On the other hand the path (<=) would be accepted by
an intuitionist, provided the original direct proof is
alreay intuitionist. Then the indirect proof would be
also intuitionist, since its construction is based on
an intuitionist proof by way of using and identity and
applying modus ponens.
But some hardcore intuitionists might object that identity
works only for predicates and that the following
identity is not viable:
---------------- (id)
P -> f |- P -> f
Well no problem this identity is also derivable:
------ (Id) ------ (Id)
P |- P f |- f
-------------------- (Left ->)
P -> f, P |- f
---------------- (Right ->)
Aatu Koskensilta
> Aatu Koskensilta schrieb:
>> Why is that? How is it more clear or elegant to take a direct proof of
>> P, prefix it with "Suppose not P" and finish with a triumphant "A
>> contradiction!", instead of just giving the direct proof?
>
> An indirect proof is not a direct proof prefixed with the
> negation of the goal, leading to a contradiction.
Why do you think I think an indirect proof is a direct proof prefixed
with the negation of the goal, leading to a contradiction? In classical
mathematics there are many indirect proofs that are not of this form.
> But we would need to clarify more what a direct proof
> would mean. What is a "proper" direct proof? An intuitionistic
> direct proof?
Do you perhaps think there are intuitionistic indirect proofs?
Aatu Koskensilta
> But some hardcore intuitionists might object that identity works only
> for predicates and that the following identity is not viable:
>
> ---------------- (id)
> P -> f |- P -> f
Are these the same hardcore intuitionists who object to dental floss?
Arturo Magidin
> Aatu Koskensilta schrieb:
>
> > Why is that? How is it more clear or elegant to take a direct proof of
> > P, prefix it with "Suppose not P" and finish with a triumphant "A
> > contradiction!", instead of just giving the direct proof?
>
> An indirect proof is not a direct proof prefixed with the
> negation of the goal, leading to a contradiction. Look what
> you say, its impossible:
>
> The direct proof would be:
>
> G |- P
>
> Prefix with suppose not P, well this could eventually be:
>
> G, ~P |- P
>
> But finish with a contradiction, I cannot make no head nor
> tail what you mean by this. Replace the conclusion? Are
> your steps to be taken as proof transformations? If yes, how?
Suppose you have a proof of G|-P. It will look like
S1
S2
S3
...
Sn
where each Si is either a tautology, an axiom, a sentence from G, or a
consequence of previous lines using a valid rule of inference (usually
modus ponens), and Sn is P.
One can always take such a proof and create a "proof by contradiction"
as follows:
~P
S1
S2
S3
...
Sn [remember, this equals P]
P/\~P
This gives a proof of G,~P |- (A /\ ~A), where A is P. That is, a
proof of G|-P by contradiction.
We obtain the last line by considering the first line, the (n+1)st
line, and using the valid rule of inference that says that from P and
from Q we can deduce P/\Q.
This is a proof by contradiction that is "obtained" from the previous
proof by adding a line at the beginning and a line at the end.
More informally, the phenomenon Aatu is refering to is that in which
you have a direct (but informal) proof of P. You then begin by saying
"Assume ~P". Then you give the direct proof of P. Then you note "But
the conclusion P contradicts the assumption ~P", and conclude "~P".
Take the direct proof that no finite collection of primes is complete:
Let S={p_1,...,p_n} be a finite collection of primes.
Define N=p_1*...*p_n + 1. Then N is a natural number. The remainder of
dividing N by any p_i in S is 1, so N is not divisible by any p_i in
S. If N is prime, then N is a prime not in S. If N is not prime, then
there is a prime q that divides N, and q is not in S (because we know
that x in S --> x does not divide N). Thus, q is a prime not in S.
Therefore, there are primes that are not in S.
Now consider the usual "proof by contradiction." It normally runs like
this (statements between "*" are added to the above):
Let S={p_1,...,p_n} be a finite collection of primes *and assume that
S contains all primes*.
Define N=p_1*...*p_n + 1. Then N is a natural number. The remainder of
dividing N by any p_i in S is 1, so N is not divisible by any p_i in
S. If N is prime, then N is a prime not in S. If N is not prime, then
there is a prime q that divides N, and q is not in S (because we know
that x in S --> x does not divide N). Thus, q is a prime not in S.
Therefore, there are primes that are not in S. *This contradicts the
assumption that S contains all primes.*
In a very reasonable sense, we can say that this proof is obtained
from the direct proof above by "adding a line at the beginning and a
line at the end". Note that the assumption "S contains all primes" is
not used at all until the very last line, where we take the direct
conclusion we have obtains, "there are primes that are not in S", and
juxtapose it with our added assumption "S contains all primes" to
obtain a contradiction.
Now, not *every* indirect proof is of this form; but it is very often
the case that one encounters indirect proofs like this: they are
"really" direct proofs with an added "assume the conclusion is false"
at the beginning, and an added "but the fact that the conclusion holds
contradicts our assumption that the conclusion is false". Again: not
every indirect proof is like this, but a lot of people produce
"indirect proofs" like this.
--
Arturo Magidin
Daryl McCullough
>
>On Aug 23, 2:20=A0pm, quasi <qu...@null.set> wrote:
>> In the direct proof, one doesn't assume that the list
>> of primes is finite. One starts with an arbitrary finite nonempty set
>> of primes and shows that there must exist a new prime not in the set.
>
>... and in the "indirect proof" one does exactly the same, except that
>one sticks a big neon yellow sticker on the set that says "THIS IS THE
>SET OF ALL PRIMES".
I think there is a sense in which the indirect proof is more direct
than the direct proof.
Indirect proof: Assume that p_1, ..., p_n is an enumeration of all
the prime numbers. Let p = p_1 * p_2 * ... * p_n + 1. Then p is a
new prime number that is not on the list. Contradiction!
Direct proof: Let p_1, ..., p_n be any finite collection of primes.
Let p = p_1 * p_2 * ... * p_n + 1. Let p' be any prime factor of p.
Then p' is not on the original list.
The direct proof requires an extra fact (that every number can be
written as a product of primes) that is not necessary in the indirect
proof. Also, the new prime that is constructed in the indirect proof is
defined explicitly, while the new prime that is constructed in the direct
proof is only given indirectly.
--
Daryl McCullough
Ithaca, NY
quasi
But that's the issue. Does the audience fully accept that definition?
Doesn't it need to be discussed first as a prerequisite, so that it
doesn't jar when it's used as the final step?
I think it's much easier for the audience to instantly accept, without
requiring an explicit definition, that if the set of all primes is a
finite set, then it can be represented as a list p_1, p_2, ... , p_n.
The contradiction obtained later doesn't require the definition of
"infinitely many". Instead, it appeals to the immediately intuitive
notion that if a finite set has exactly n elements, then it can't have
n+1 elements.
>> You probably can find a way, appealing to some axiom
>> or other, but that assumes the audience is aware of and accepts that
>> axiom, and understands its use.
>
>I can see you arguing that the "indirect proof" is easier to digest
>for some students. What mystifies me (and presumably Aatu) is the
>assertion that it is "more elegant"; the reason it mystifies me is
>that it is *exactly the same proof*, with a line added at the
>beginning and a line added at the end. The "assumption" that the list/
>set contains all primes is not used untill the "last line", which is
>also added.
>
>But perhaps, as with the meaning of the word "conjecture", we just
>have different understandings of the word "elegance".
If you consider the set of math textbooks containing a proof that
there are infinitely many primes, you will find the overwhelming
majority favor the indirect proof. Perhaps that the majority of
authors also have a different understanding of the word elegance than
you and Aatu?
quasi
Arturo Magidin
wrote:
> Arturo Magidin says...
>
>
>
> >On Aug 23, 2:20=A0pm, quasi <qu...@null.set> wrote:
> >> In the direct proof, one doesn't assume that the list
> >> of primes is finite. One starts with an arbitrary finite nonempty set
> >> of primes and shows that there must exist a new prime not in the set.
>
> >... and in the "indirect proof" one does exactly the same, except that
> >one sticks a big neon yellow sticker on the set that says "THIS IS THE
> >SET OF ALL PRIMES".
>
> I think there is a sense in which the indirect proof is more direct
> than the direct proof.
>
> Indirect proof: Assume that p_1, ..., p_n is an enumeration of all
> the prime numbers. Let p = p_1 * p_2 * ... * p_n + 1. Then p is a
> new prime number that is not on the list. Contradiction!
Well, except of course that this is incorrect.(-; You have no warrant
for asserting that p itself must be a prime.
> Direct proof: Let p_1, ..., p_n be any finite collection of primes.
> Let p = p_1 * p_2 * ... * p_n + 1. Let p' be any prime factor of p.
> Then p' is not on the original list.
>
> The direct proof requires an extra fact (that every number can be
> written as a product of primes) that is not necessary in the indirect
> proof.
Ehr... yes it is. Otherwise, your "direct proof" is wrong. On what
grounds, pray tell, do you conclude that p is prime?
> Also, the new prime that is constructed in the indirect proof is
> defined explicitly, while the new prime that is constructed in the direct
> proof is only given indirectly.
I do not see how you conclude that the number constructed in your
"indirect proof" is a prime. Could you tell me how you justify that?
--
Arturo Magidin
Daryl McCullough
What I said was stupid. The indirect proof *also* requires the same
fact, that every number can be written as a product of primes. Otherwise,
knowing that p is not divisible by any other prime does not prove that it is
prime.
Arturo Magidin
Without a definition of "infinite", the "indirect proof" is no better!
So, again, I have to wonder what is this elusive elegance that you
believe the indirect proof acquires by adding an (unnecessary)
hypothesis and an extra line at the end. In the "indirect proof" you
*also* need the audience to have a clear and well-defined notion of
"finite"/"infinite".
Perhaps the issue is that you have a *particular* meaning of
"infinite" in mind, one that does not lend itself easily to the direct
proof? That could certainly be the case; but keep in mind that this
requirement you bring up here is just as applicable to the indirect
proof.
> I think it's much easier for the audience to instantly accept, without
> requiring an explicit definition, that if the set of all primes is a
> finite set, then it can be represented as a list p_1, p_2, ... , p_n.
I think that it is a bit disingenuous to give the audience all the
credit you believe is necessary for one proof, and deny that same
audience any credit whatsoever for the other proof.
> The contradiction obtained later doesn't require the definition of
> "infinitely many". Instead, it appeals to the immediately intuitive
> notion that if a finite set has exactly n elements, then it can't have
> n+1 elements.
>
> >> You probably can find a way, appealing to some axiom
> >> or other, but that assumes the audience is aware of and accepts that
> >> axiom, and understands its use.
>
> >I can see you arguing that the "indirect proof" is easier to digest
> >for some students. What mystifies me (and presumably Aatu) is the
> >assertion that it is "more elegant"; the reason it mystifies me is
> >that it is *exactly the same proof*, with a line added at the
> >beginning and a line added at the end. The "assumption" that the list/
> >set contains all primes is not used untill the "last line", which is
> >also added.
>
> >But perhaps, as with the meaning of the word "conjecture", we just
> >have different understandings of the word "elegance".
>
> If you consider the set of math textbooks containing a proof that
> there are infinitely many primes, you will find the overwhelming
> majority favor the indirect proof.
Are we going back to what seems to be your favorite fallacy, the
Argumentum ad populum?
> Perhaps that the majority of
> authors also have a different understanding of the word elegance than
> you and Aatu?
Perhaps your assumption that all authors always put the proof they
find most elegant in their books is flawed? Not to mention, of course,
that the Argumentum ad populum is a *fallacy*.
--
Arturo Magidin
Aatu Koskensilta
> Indirect proof: Assume that p_1, ..., p_n is an enumeration of all
> the prime numbers. Let p = p_1 * p_2 * ... * p_n + 1. Then p is a
> new prime number that is not on the list. Contradiction!
How do you know that p is a prime?
> Direct proof: Let p_1, ..., p_n be any finite collection of primes.
> Let p = p_1 * p_2 * ... * p_n + 1. Let p' be any prime factor of p.
> Then p' is not on the original list.
How do you know this? Filling in the details we find there's no relevant
difference between these two proofs.
Jan Burse
> One can always take such a proof and create a "proof by contradiction"
> as follows:
> ~P
> S1
> S2
> S3
> ...
> Sn [remember, this equals P]
> P/\~P
Yes this is more or less the same as (what I have posted):
---------------- (Id)
G |- P P -> f |- P -> f
------------------------------------- (MP)
G, P -> f |- f
Note P->f can be viewed as ~P.
The only difference is that you have listed the proof
of G |- P as steps S1 .. Sn. But you also do not discard
~P. And somehow you are shy to use f in the final
conclusion. This would probably need some additional
steps to arrive at.
Bye
Frederick Williams
>
> [...] Is there some explanation for this curious
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
Proofs are intended to convince the audience of the truth of something.
A student doing an exercise is his own audience. "A logical and
mathematical" point of view has nothing to do with it, what counts is
the psychological point of view: is the student convinced of the
validity of what he is doing?
--
Needle, nardle, noo.
Aatu Koskensilta
Putting such matters to one side, I still wonder why pointlessly
indirect proofs are so popular. Is there perhaps some psychological
mechanism at work? Are elementary texts somehow especially misleading in
this regard? Is this a recent phenomenon or something that's been with
us since the dawn of time?
Arturo Magidin
The point, I think, is the distinction between "you can take a direct
proof and create a 'proof by contradiction' by adding a line at the
beginning and a/some line(s) at the end" and "every proof by
contradiction is a direct proof with an added line at the beginning
and a/some line(s) at the end".
Aatu is talking about the specific situations in which we encounter
the former situation. Your reply seemed to interpret this as an
assertion of the latter. I think it is clear that Aatu did not suggest
or imply that the latter was the case; he is wondering about the
fondness of people for the former ("pointelessly indirect proofs").
--
Arturo Magidin
Jan Burse
> Arturo Magidin schrieb:
>> One can always take such a proof and create a "proof by contradiction"
>> as follows:
>> ~P
>> S1
>> S2
>> S3
>> ...
>> Sn [remember, this equals P]
>> P/\~P
>
> Yes this is more or less the same as (what I have posted):
Actually yours is only:
G |- P ~P |- ~P
--------------------- (Right &)
G, ~P |- P & ~P
So its simply right fusion (conjunction) introduction.
Best Regards
Arturo Magidin
> Arturo Magidin <magi...@member.ams.org> writes:
> > On Aug 23, 2:54 pm, quasi <qu...@null.set> wrote:
>
> >> If you consider the set of math textbooks containing a proof that
> >> there are infinitely many primes, you will find the overwhelming
> >> majority favor the indirect proof.
>
> > Are we going back to what seems to be your favorite fallacy, the
> > Argumentum ad populum?
>
> Putting such matters to one side, I still wonder why pointlessly
> indirect proofs are so popular. Is there perhaps some psychological
> mechanism at work? Are elementary texts somehow especially misleading in
> this regard? Is this a recent phenomenon or something that's been with
> us since the dawn of time?
For some proofs, it tends to be inherited; if you get one early or
popular book that uses a particular argument, it tends to propagate.
Keep also in mind that the multitude of books is a fairly recent
phenomenon. It's not been with us "since the dawn of time", given that
Euclid uses the direct argument (then again, Euclid did not have a
good notion of "infinite" that he could rely on, so that may be the
source of the issue).
As I intimated to quasi, I can see an argument that for some students
the "pointlessly indirect proof" may be easier to digest; in a sense,
it performs a bit of extra chewing for them before feeding it to them.
It also seems to arise a lot when students work on problems for which
they do not see a direct proof; throwing extra hypothesis often helps,
as has been pointed out, psychologically. And then they develop the
unconscious habit of throwing in the extra hypothesis first, before
they start thinking about the problem. That kind of mental habit can
be hard to break.
--
Arturo Magidin
Aatu Koskensilta
> Proofs are intended to convince the audience of the truth of
> something. A student doing an exercise is his own audience. "A
> logical and mathematical" point of view has nothing to do with it,
> what counts is the psychological point of view: is the student
> convinced of the validity of what he is doing?
Sure. But is there some explanation for this curious phenomenon, that
many people seem naturally inclined to prefer pointlessly indirect
proofs? Since indirect proof is more powerful than direct proof -- that
is, there are theorems for which we can give indirect proofs but which
have no direct proof -- it is, as MoeBlee and Jan have suggested, only
natural that when searching for a proof we might try and derive a
contradiction from the negation of the statement we're trying to
prove. But this does not explain why many many people prefer indirect
formulations of patently direct proofs.
quasi
<mag...@member.ams.org> wrote:
>> If you consider the set of math textbooks containing a proof that
>> there are infinitely many primes, you will find the overwhelming
>> majority favor the indirect proof.
>
>Are we going back to what seems to be your favorite fallacy, the
>Argumentum ad populum?
In mathematics, it's less of a fallacy.
Throughout history, and especially since the late 1800's the
international community of mathematicians has tried very hard to
improve the notation, the terminology, the logical structure, and the
exposition of mathematics. It's very definitely a consensus approach,
but also partly hierarchical, following the styles of various
respected leaders. Moreover, while not perfect, I feel it has largely
succeeded. At this point, there are very few places in mathematics
where the majority of authors have made a clearly wrong stylistic
choice, but in those cases, it's usually because fixing it would
create more problems than it solves.
quasi
Jan Burse
> Frederick Williams<frederick...@tesco.net> writes:
>
>> Proofs are intended to convince the audience of the truth of
>> something. A student doing an exercise is his own audience. "A
>> logical and mathematical" point of view has nothing to do with it,
>> what counts is the psychological point of view: is the student
>> convinced of the validity of what he is doing?
>
> Sure. But is there some explanation for this curious phenomenon, that
> many people seem naturally inclined to prefer pointlessly indirect
> proofs? Since indirect proof is more powerful than direct proof -- that
> is, there are theorems for which we can give indirect proofs but which
> have no direct proof -- it is, as MoeBlee and Jan have suggested, only
> natural that when searching for a proof we might try and derive a
> contradiction from the negation of the statement we're trying to
> prove. But this does not explain why many many people prefer indirect
> formulations of patently direct proofs.
>
I have no clear definition of you what "pointless" means,
and you cannot give evidence that indirect proofs are "common",
how would you measure it?
So I share the common behaviour to judge your inquiry as
pointless and do not further elaborate on it.
Bye
Daryl McCullough
>stevend...@yahoo.com (Daryl McCullough) writes:
>
>> Indirect proof: Assume that p_1, ..., p_n is an enumeration of all
>> the prime numbers. Let p = p_1 * p_2 * ... * p_n + 1. Then p is a
>> new prime number that is not on the list. Contradiction!
>
>How do you know that p is a prime?
>
>> Direct proof: Let p_1, ..., p_n be any finite collection of primes.
>> Let p = p_1 * p_2 * ... * p_n + 1. Let p' be any prime factor of p.
>> Then p' is not on the original list.
>
>How do you know this? Filling in the details we find there's no relevant
>difference between these two proofs.
You're right. In both cases, you need the fact that every natural
other than 1 can be expressed as a product of primes. The indirect
proof though has an explicit representation of the new prime: namely
p, while the direct proof only has the shadowy, vague, p', whose only
specification is "some prime factor of p". I think the indirect proof
is more vivid.
Arturo Magidin
> On Mon, 23 Aug 2010 12:04:04 -0700 (PDT), Arturo Magidin
>
> >> If you consider the set of math textbooks containing a proof that
> >> there are infinitely many primes, you will find the overwhelming
> >> majority favor the indirect proof.
>
> >Are we going back to what seems to be your favorite fallacy, the
> >Argumentum ad populum?
>
> In mathematics, it's less of a fallacy.
In mathematics, it's still a fallacy; certainly, it cannot be used in
any mathematical proof. Your argument here, however, is not
mathematical and not a proof, so the insinuation that it is
mathematical is likewise a fallacy.
Really, it's okay to say "I'll go with the crowd", but except in very
selected fields (e.g., the field of language *usage*) not okay to say
"it's correct *because* it's what most people do".
> Throughout history, and especially since the late 1800's the
> international community of mathematicians has tried very hard to
> improve the notation, the terminology, the logical structure, and the
> exposition of mathematics. It's very definitely a consensus approach,
> but also partly hierarchical, following the styles of various
> respected leaders. Moreover, while not perfect, I feel it has largely
> succeeded. At this point, there are very few places in mathematics
> where the majority of authors have made a clearly wrong stylistic
> choice, but in those cases, it's usually because fixing it would
> create more problems than it solves.
None of which makes "most people do it, therefore it must be correct"
a valid argument.
I'm sure it does make one feel a bit better about doing it oneself in
particular instances, but then I can only quote the old Spanish adage:
"Mal de muchos, consuelo de tontos."
--
Arturo Magidin
Arturo Magidin
wrote:
> Aatu Koskensilta says...
>
> >stevendaryl3...@yahoo.com (Daryl McCullough) writes:
>
> >> Indirect proof: Assume that p_1, ..., p_n is an enumeration of all
> >> the prime numbers. Let p = p_1 * p_2 * ... * p_n + 1. Then p is a
> >> new prime number that is not on the list. Contradiction!
>
> >How do you know that p is a prime?
>
> >> Direct proof: Let p_1, ..., p_n be any finite collection of primes.
> >> Let p = p_1 * p_2 * ... * p_n + 1. Let p' be any prime factor of p.
> >> Then p' is not on the original list.
>
> >How do you know this? Filling in the details we find there's no relevant
> >difference between these two proofs.
>
> You're right. In both cases, you need the fact that every natural
> other than 1 can be expressed as a product of primes. The indirect
> proof though has an explicit representation of the new prime: namely
> p,
Again, *no*. In the "indirect proof" you know that *either* p is a
prime, or else it is divisible by *some* prime p'. You cannot conclude
that p is a prime, so you cannot conclude that you have "an explicit
representation of the new prime". As in the direct argument,
*sometimes* you have explicitly produced the "new prime", sometimes
you can only show that there must be *some* p' with the desired
properties without specifying it.
--
Arturo Magidin
Aatu Koskensilta
> You're right. In both cases, you need the fact that every natural
> other than 1 can be expressed as a product of primes. The indirect
> proof though has an explicit representation of the new prime: namely
> p, while the direct proof only has the shadowy, vague, p', whose only
> specification is "some prime factor of p". I think the indirect proof
> is more vivid.
How so? Filling in all the details the indirect proof is just a
pointlessly dressed up version of the direct proof. Both are as explicit
as to the identity of the prime not included in the list.
Jesse F. Hughes
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> finitely many primes. Is there some explanation for this curious
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
How about the simple fact that assuming the negation of your
conclusion adds to the number of justified formulas you can use? It
does no harm and it gives one an additional premise for proof rules,
so it seems like a reasonable heuristic to begin proof search by
trying to go indirect.
That said, I agree that the final proof should not be presented as
indirect if it's not essential to the argument, but at least I can
also see why people look at indirect proofs when searching for a
proof.
--
"And that's what we do. We put in more troops to get to a position
where we can be in some other place. The question is, who ought to
make that decision? The Congress or the commanders? And as you know,
my position is clear. I'm the commander guy." --- George W. Bush
quasi
<mag...@member.ams.org> wrote:
>On Aug 23, 3:21 pm, quasi <qu...@null.set> wrote:
>> On Mon, 23 Aug 2010 12:04:04 -0700 (PDT), Arturo Magidin
>>
>> <magi...@member.ams.org> wrote:
>> >> If you consider the set of math textbooks containing a proof that
>> >> there are infinitely many primes, you will find the overwhelming
>> >> majority favor the indirect proof.
>>
>> >Are we going back to what seems to be your favorite fallacy, the
>> >Argumentum ad populum?
>>
>> In mathematics, it's less of a fallacy.
>
>In mathematics, it's still a fallacy; certainly, it cannot be used in
>any mathematical proof.
You misinterpreted my meaning.
>Your argument here, however, is not mathematical and not a proof,
Agreed, but neither is your claim of "fallacy" proved in any way.
>so the insinuation that it is mathematical is likewise a fallacy.
Again you misinterpreted. I wasn't making a mathematical argument. I
was discussing the extent to which the notion of elegance, for the
purposes of mathematical exposition to an intended audience, could
legitimately be regarded as a consensus view.
>Really, it's okay to say "I'll go with the crowd", but except in very
>selected fields (e.g., the field of language *usage*) not okay to say
>"it's correct *because* it's what most people do".
Style of mathematical exposition is like language usage.
>> Throughout history, and especially since the late 1800's the
>> international community of mathematicians has tried very hard to
>> improve the notation, the terminology, the logical structure, and the
>> exposition of mathematics. It's very definitely a consensus approach,
>> but also partly hierarchical, following the styles of various
>> respected leaders. Moreover, while not perfect, I feel it has largely
>> succeeded. At this point, there are very few places in mathematics
>> where the majority of authors have made a clearly wrong stylistic
>> choice, but in those cases, it's usually because fixing it would
>> create more problems than it solves.
>
>None of which makes "most people do it, therefore it must be correct"
>a valid argument.
We are talking art here -- so as I pointed out above, it very
definitely _is_ like language usage. When there is a choice of
logically correct proofs, they are all correct in a mathematical
sense, but stylistically, certain proofs are commonly viewed as more
elegant than others. Of course, authors are free to make non-standard
or less standard choices, and sometimes their approach is then
followed by others. It's an evolutionary process.
It's clear that the last 150 years have seen a rapid evolution in the
style of mathematical exposition, but my sense is that, since about
1960, the evolution has slowed, and in fact, at this point, I feel it
has mostly stabilized.
quasi
Frederick Williams
>
> Suppose you have a proof of G|-P. It will look like
>
> S1
> S2
> S3
> ...
> Sn
>
> where each Si is either a tautology, an axiom, a sentence from G, or a
> consequence of previous lines using a valid rule of inference (usually
> modus ponens), and Sn is P.
>
> One can always take such a proof and create a "proof by contradiction"
> as follows:
> ~P
> S1
> S2
> S3
> ...
> Sn [remember, this equals P]
> P/\~P
>
> This gives a proof of G,~P |- (A /\ ~A), where A is P. That is, a
> proof of G|-P by contradiction.
Given a formal system of proof for classical FOL, is there a primitive
recursive transformation that will turn any proof by contradiction (in
that formal system) into a proof of the same conclusion that does not
use "~P ... Q&~Q / P" or "P ... Q&~Q / ~P" (or whatever "proof by
contradiction" might mean in the formal system)?
I have a vague idea that Quine proved that there is.
Not that it has anything to do with Aatu's question.
--
Needle, nardle, noo.
MoeBlee
> How about the simple fact that assuming the negation of your
> conclusion adds to the number of justified formulas you can use? It
> does no harm and it gives one an additional premise for proof rules,
> so it seems like a reasonable heuristic to begin proof search by
> trying to go indirect.
>
> That said, I agree that the final proof should not be presented as
> indirect if it's not essential to the argument, but at least I can
> also see why people look at indirect proofs when searching for a
> proof.
Whadda am I, chopped liver? The above is pretty much what I wrote way
back at post #7. But nobody paid any never mind. Whadda I have to do
around here to get a little love and attention? I'm so left out. I
think I'll go have a deep season of despair now...
MoeBlee
Aatu Koskensilta
> That said, I agree that the final proof should not be presented as
> indirect if it's not essential to the argument, but at least I can
> also see why people look at indirect proofs when searching for a
> proof.
Sure. Perhaps I was not explicit enough. I was wondering why people seem
to prefer indirect renditions of patently direct proofs.
Arturo Magidin
> On Mon, 23 Aug 2010 12:30:34 -0700 (PDT), Arturo Magidin
>
>
>
> <magi...@member.ams.org> wrote:
> >On Aug 23, 3:21 pm, quasi <qu...@null.set> wrote:
> >> On Mon, 23 Aug 2010 12:04:04 -0700 (PDT), Arturo Magidin
>
> >> <magi...@member.ams.org> wrote:
> >> >> If you consider the set of math textbooks containing a proof that
> >> >> there are infinitely many primes, you will find the overwhelming
> >> >> majority favor the indirect proof.
>
> >> >Are we going back to what seems to be your favorite fallacy, the
> >> >Argumentum ad populum?
>
> >> In mathematics, it's less of a fallacy.
>
> >In mathematics, it's still a fallacy; certainly, it cannot be used in
> >any mathematical proof.
>
> You misinterpreted my meaning.
>
> >Your argument here, however, is not mathematical and not a proof,
>
> Agreed, but neither is your claim of "fallacy" proved in any way.
My claim is that the appeal to the crowd (Argumentum ad populum) is a
fallacy; my observation is that you invoked that argument ("just look
at the vast majority of books"). I'm not sure what kind of "proof" you
were looking for, but simple observation shows that you've invoked
this argument at least twice over the past two days (here, to claim
that because most most do something a certain way then it follows that
it is more elegant, or that more people consider it elegant; and
yesterday to claim that because many people called something "Lehmer's
Conjecture" then it follows that your use of conjecture is necessarily
valid).
>
> >so the insinuation that it is mathematical is likewise a fallacy.
>
> Again you misinterpreted. I wasn't making a mathematical argument.
Then I fail to see why you bring up the non-sequitur of "in
mathematics, [the argumentum ad populum] is less of a fallacy".
> I
> was discussing the extent to which the notion of elegance, for the
> purposes of mathematical exposition to an intended audience, could
> legitimately be regarded as a consensus view.
Then you have, forgive me for saying so, a pretty confusing way of
expressing yourself. You said *in mathematics*, not "in matters of
deciding what is mathematically elegant".
> >Really, it's okay to say "I'll go with the crowd", but except in very
> >selected fields (e.g., the field of language *usage*) not okay to say
> >"it's correct *because* it's what most people do".
>
> Style of mathematical exposition is like language usage.
>
> >> Throughout history, and especially since the late 1800's the
> >> international community of mathematicians has tried very hard to
> >> improve the notation, the terminology, the logical structure, and the
> >> exposition of mathematics. It's very definitely a consensus approach,
> >> but also partly hierarchical, following the styles of various
> >> respected leaders. Moreover, while not perfect, I feel it has largely
> >> succeeded. At this point, there are very few places in mathematics
> >> where the majority of authors have made a clearly wrong stylistic
> >> choice, but in those cases, it's usually because fixing it would
> >> create more problems than it solves.
>
> >None of which makes "most people do it, therefore it must be correct"
> >a valid argument.
>
> We are talking art here -- so as I pointed out above, it very
> definitely _is_ like language usage. When there is a choice of
> logically correct proofs, they are all correct in a mathematical
> sense, but stylistically, certain proofs are commonly viewed as more
> elegant than others. Of course, authors are free to make non-standard
> or less standard choices, and sometimes their approach is then
> followed by others. It's an evolutionary process.
Your error here lies in your unspoken assumption that textbook authors
select among competing proofs by their perception of their "elegance".
This is hardly the case. At best, you could argue that it is *likely*
that they select among competing proof by their perception of their
pedagogical utility. Your deduction about "elegance" suggests either a
completely nonstandard notion of "elegance", a strange view of the
objective of a textbook, or some similar idea.
You claimed that your notion of elegance must be close to the standard
one based on what you believe to be the case about textbooks. That
simply does not follow, even assuming that you are accurate about your
perceptions on mathematical exposition.
--
Arturo Magidin
Jan Burse
> Whadda am I, chopped liver? The above is pretty much what I wrote way
> back at post #7. But nobody paid any never mind. Whadda I have to do
> around here to get a little love and attention? I'm so left out. I
> think I'll go have a deep season of despair now...
>
> MoeBlee
LoL
C'mon don't feel bad. Anyway nobody is listening to
anybody in this newsgroup. So why despair?
Bye
Aatu Koskensilta
> Whadda am I, chopped liver?
Marshall will soon be here to inform you the term du jour is "potted
plant".
> The above is pretty much what I wrote way back at post #7. But nobody
> paid any never mind. Whadda I have to do around here to get a little
> love and attention? I'm so left out. I think I'll go have a deep
> season of despair now...
Well, I paid some never mind, and did in fact mention your post in a
reply to Arturo. I was, truth be told, going to write you a reply but
got distracted. This was mainly owing to my unfortunately running out of
cigarettes, thus losing all ability to produce idiomatic English.
quasi
Well, I've made my points.
quasi
Chris Menzel
<aatu.kos...@uta.fi> said:
> Chris Menzel <cme...@remove-this.tamu.edu> writes:
>
>> My comment was meant only to suggest that there can be pedagogically
>> sound reasons for proving Cantor's Theorem indirectly and, hence, that
>> the indirect approach in this case (and perhaps others, for parallel
>> reasons) persists at least to some extent for reasons other than the
>> "natural inclination" in question.
>
> I'm afraid you'll have to spell out this suggestion. Why should we prove
> Cantor's theorem indirectly?
Who said "should"? I only suggested that students seem to find it
illuminating to see parallels with Russell's Paradox.
> If all we care about is demonstrating the usefulness of indirect proof
> we have many stock examples at hand, e.g. the irrationality of the
> square root of two. In the indirect proof of Cantor's theorem we
> assume given a function of specific sort and derive a contradiction.
> This is not, on the face of it, analogous in logical structure to
> Russell's paradox.
Seems to me quite otherwise. In RP we assume that a set of a specific
sort exists and derive a contradiction, using an argument very similar
to the argument in the proof of Cantor's theorem.
Ken Pledger
stevend...@yahoo.com (Daryl McCullough) wrote:
> >....
> >The direct proof requires an extra fact (that every number can be
> >written as a product of primes) that is not necessary in the indirect
> >proof. Also, the new prime that is constructed in the indirect proof is
> >defined explicitly, while the new prime that is constructed in the direct
> >proof is only given indirectly.
>
> What I said was stupid. The indirect proof *also* requires the same
> fact, that every number can be written as a product of primes. Otherwise,
> knowing that p is not divisible by any other prime does not prove that it is
> prime....
My defence of Euclid will probably be lost in the background noise
of this thread; but I'll try.
(1) Daryl is mistaken above. Some people have tried to unearth the
prime factorization theorem from Euclid, but it requires a vivid
imagination. The relevant step in IX.20 is (in Heath's translation):
"Next, let EF not be prime; therefore it is measured by some prime
number." Heath adds the reference [VII.31].
The statement of VII.31 is "Any composite number is measured by
some prime number", and indeed the proof of IX.20 requires only at least
one prime factor.
(2) The common misunderstanding of Euclid IX.20 is due to the modern
restatement "There are infinitely many primes". Infinite sets were not
explicitly part of mathematics until the 19th century. The Greeks were
very cagey about the actual infinite, and Euclid's claim is much more
cautious: given any "multitude" (finite list) of primes, you can find
another one.
Of course it follows that (in modern terms) the set of all prime
numbers is infinite. But it's *this* *extra* *step* which needs an
indirect proof.
Nobody will read this, but my conscience is eased. ;-(
Ken Pledger.
Aatu Koskensilta
> Of course it follows that (in modern terms) the set of all prime
> numbers is infinite. But it's *this* *extra* *step* which needs an
> indirect proof.
No it doesn't.
Transfer Principle
> On Aug 23, 2:28 pm, stevendaryl3...@yahoo.com (Daryl McCullough)
> wrote:
> > You're right. In both cases, you need the fact that every natural
> > other than 1 can be expressed as a product of primes. The indirect
> > proof though has an explicit representation of the new prime: namely
> > p,
Once again, another rapidly growing thread has drawn my attention.
> Again, *no*. In the "indirect proof" you know that *either* p is a
> prime, or else it is divisible by *some* prime p'. You cannot conclude
> that p is a prime, so you cannot conclude that you have "an explicit
> representation of the new prime". As in the direct argument,
> *sometimes* you have explicitly produced the "new prime", sometimes
> you can only show that there must be *some* p' with the desired
> properties without specifying it.
Interestingly, the debate in this subthread between McCullough (and
possibly quasi) on one side and Aatu and Magidin on the other, echoes
a similar debate between Archimedes Plutonium and Iain Davidson in
several other threads.
In particular, both McCullough and AP give an indirect proof of the
infinitude of primes, and state that in this indirect proof, p, one
plus the product of all primes is itself prime. Aatu, Magidin, and
Davidson all disagree and state that one can't conclude that p must
necessarily be prime.
The natural number 13#+1 = 30031, i.e., one more than the primorial
of 13, often appears in these debates. If one assumes that 13 were
the largest prime, then one notices that 13#+1 isn't a prime, since
30031 is the product of 59 and 509. But then AP points out that:
"If 13 is the largest prime, then 59x509 is not a factorization of
30031."
And this is indeed a theorem of PA! Likewise:
"If 13 is the largest prime, then 30031 is necessarily prime."
is also a theorem of PA! Of course since 30031 > 13, we conclude
that 13 _isn't_ the largest prime. But still, the two statements
above are theorems of PA, and so AP is _not_ wrong.
I assume that McCullough is also familiar with 13#+1 = 59*509, but
nonetheless he _correctly_ states that if p is one more than the
product of all the primes, then p is prime in the indirect proof.
Of course, Aatu and Magidin are correct about the direct proof, so
neither side is wrong. Note that the computer proof site Metamath
gives direct proofs for all of its theorems, including the big 3
(card(primes) = aleph_0, card(R) > aleph_0, ~sqrt(2)eQ).
Notice that quasi is accused of Argumentum ad Populum in his
defense of the indirect proof. Ironically, AP considers this to
be a minority position. Indeed, he believes that only _three_
people are aware of the correct indirect proof.
It's possible that AP might credit McCullough as the fourth
person with the correct indirect proof. I think I'll head on over
to the recent AP thread and ask him whether McCullough should be
so credited.
Daryl McCullough
>
>In article <i4ugl...@drn.newsguy.com>,
> stevend...@yahoo.com (Daryl McCullough) wrote:
>
>> >....
>> >The direct proof requires an extra fact (that every number can be
>> >written as a product of primes) that is not necessary in the indirect
>> >proof. Also, the new prime that is constructed in the indirect proof is
>> >defined explicitly, while the new prime that is constructed in the direct
>> >proof is only given indirectly.
>>
>> What I said was stupid. The indirect proof *also* requires the same
>> fact, that every number can be written as a product of primes. Otherwise,
>> knowing that p is not divisible by any other prime does not prove that it is
>> prime....
>
>
> My defence of Euclid will probably be lost in the background noise
>of this thread; but I'll try.
>
>(1) Daryl is mistaken above. Some people have tried to unearth the
>prime factorization theorem from Euclid, but it requires a vivid
>imagination.
Right. I should not have implied that prime factorization is needed.
Something much weaker suffices:
"If x is any natural number greater than 1, then there are naturals y
and z such that y is prime, and x = y*z".
>The relevant step in IX.20 is (in Heath's translation):
>"Next, let EF not be prime; therefore it is measured by some prime
>number." Heath adds the reference [VII.31].
>
> The statement of VII.31 is "Any composite number is measured by
>some prime number", and indeed the proof of IX.20 requires only at least
>one prime factor.
Right.
Jesse F. Hughes
Well, now, someone paid attention to your post, though I don't recall
who. Right after posting, I saw someone mention your post.
I didn't read your post, of course, because you're in my killfile. Or
something.
--
"These mathematicians are worse than communists, as how do you explain
their behavior? I *am* the American Dream, fighting for what should be
mine, having to get past weak-minded academics who are fighting to
block my success. But I shall prevail!!!" -- James S. Harris
Frederick Williams
> (2) The common misunderstanding of Euclid IX.20 is due to the modern
> restatement "There are infinitely many primes". Infinite sets were not
> explicitly part of mathematics until the 19th century. The Greeks were
> very cagey about the actual infinite, and Euclid's claim is much more
> cautious: given any "multitude" (finite list) of primes, you can find
> another one.
>
> Of course it follows that (in modern terms) the set of all prime
> numbers is infinite. But it's *this* *extra* *step* which needs an
> indirect proof.
Really? "There are infinitely many primes" does not imply "There is an
infinite set of primes". In FOPA one can prove that for any prime P
there is a prime larger than P, but one cannot prove that there is an
infinite set of primes (not least because in FOPA one cannot talk about
sets of any kind).
--
Needle, nardle, noo.
Jan Burse
> stevend...@yahoo.com (Daryl McCullough) writes:
>
>> You're right. In both cases, you need the fact that every natural
>> other than 1 can be expressed as a product of primes. The indirect
>> proof though has an explicit representation of the new prime: namely
>> p, while the direct proof only has the shadowy, vague, p', whose only
>> specification is "some prime factor of p". I think the indirect proof
>> is more vivid.
>
> How so? Filling in all the details the indirect proof is just a
> pointlessly dressed up version of the direct proof. Both are as explicit
> as to the identity of the prime not included in the list.
>
Actually there are proof systems where the indirect proof and
the direct proof can have exactly the same proof. For more
details see here:
Basic proof theory (1990)
by S S Wainer, L A Wallen
Proof Theory: A Selection of Papers
from the Leeds Proof Theory Programme
The idea is to use a one sided sequent proof system. So this
proof system will not be based on two sided sequents like
G |- D found in Gentzen, or G |- [A] as in natural deduction style
where the right side is a single formula or empty. It will be
just based on multi sets G.
An introduction to the same rules can also be found here (*).
If we want to prove a sequent B1,..,Bn |- A, we prove:
-B1,..,-Bn,A
And if we want to prove a sequent B1,..,Bm |-, we prove:
-B1,..,-Bn
We get for a direct proof G |- P, the need to prove:
-G, P
And since -(~A)=A, we get for an indirect proof G, ~P |-, the need to prove:
-G, P
So structurally in this system there will be no difference in
proofs. When we find a direct proof with shape S in this system,
this shape S will also denote a indirect proof in this system.
This might also hint how to turn a indirect proof into a direct
proof and vice versa in one of the other systems. But I did not
try this out. It would be an alternative approach to what I have
shown previously in this thread, since this proof transformation
would not add proof lines. Instead it would rearrange inside
the sequents, and most probably trade (left)-rules for
(right)-rules and vice versa.
As far as I can see right now, the thing only works in classical
logic, since we have double negation elimination there. So bottom
line is most likely that indirect/direct proofs only matter
when considering non-classical logic. For intuitionist direct
proofs there are realizablity theorems, which are not available
for indirect proofs in general.
Actually I think that the whole matter is not so important
anymore nowadays. Somehow we could give also a constructive
reading to non-intuitionistic rules in an appropriate type
theory and for example avoid russels paradox. And we can also
go higher order without harm. Brave new world (**).
Don't worry, be happy!
Bye
(*)
http://www.xlog.ch/papers/calculi93/calculi93.pdf
(**)
http://www.jekejeke.ch/idatab/blog/en/docs/jan/099_2010/100_logic/cheat_sheet.pdf
Daryl McCullough
>
>stevend...@yahoo.com (Daryl McCullough) writes:
>
>> You're right. In both cases, you need the fact that every natural
>> other than 1 can be expressed as a product of primes. The indirect
>> proof though has an explicit representation of the new prime: namely
>> p, while the direct proof only has the shadowy, vague, p', whose only
>> specification is "some prime factor of p". I think the indirect proof
>> is more vivid.
>
>How so? Filling in all the details the indirect proof is just a
>pointlessly dressed up version of the direct proof. Both are as explicit
>as to the identity of the prime not included in the list.
Hmm. Not in my proof. Maybe it depends on what you assume has already
been established about primes.
Lemma: If x is any natural number greater than 1, and x has no
prime factors less than x, then x is prime.
If we assume that this has already been proved, then the indirect
proof works as follows:
Theorem: There are infinitely many primes.
Proof: Assume to the contrary that p_1, p_2, ..., p_n is the
complete list of primes. Let p = p_1 * p_2 * ... * p_n + 1.
Clearly, p has no prime factors among p_1, p_2, ..., p_n. So
by the lemma, p is prime. Contradiction!
The direct proof works as follows:
Theorem: For every list p_1, p_2, ..., p_n of primes, there is
another prime not on the list.
Proof: Let p = p_1 * p_2 * ... * p_n + 1.
Clearly, p has no prime factors among p_1, p_2, ..., p_n. So
by the lemma, either p is prime, or there is a prime p' less
than p that is a factor of p. In the first case, p is a prime
not on the list. In the second case, p' is a prime not on the
list.
In this proof, we don't get that p is prime, we only get that
either p is prime, or it has a prime factor that is not on
the list.
If instead, we assume a slightly different lemma, then the
two proofs becomes essentially the same:
Lemma: If x is any natural number greater than 1, then
it has a prime factor p'.
With this lemma, the direct and indirect proofs are the same,
in both cases, the prime we construct that is not on the list
is that p' that is a factor of p.
Daryl McCullough
>
>On Aug 23, 2:28=A0pm, stevendaryl3...@yahoo.com (Daryl McCullough)
>wrote:
>> Aatu Koskensilta says...
>>
>> >stevendaryl3...@yahoo.com (Daryl McCullough) writes:
>>
>> >> Indirect proof: Assume that p_1, ..., p_n is an enumeration of all
>> >> new prime number that is not on the list. Contradiction!
>>
>> >How do you know that p is a prime?
>>
>> >> Direct proof: Let p_1, ..., p_n be any finite collection of primes.
>> >> Then p' is not on the original list.
>>
>> >How do you know this? Filling in the details we find there's no relevant
>> >difference between these two proofs.
>>
>> You're right. In both cases, you need the fact that every natural
>> other than 1 can be expressed as a product of primes. The indirect
>> proof though has an explicit representation of the new prime: namely
>> p,
>
>Again, *no*. In the "indirect proof" you know that *either* p is a
>prime, or else it is divisible by *some* prime p'.
If you appeal to the lemma: If x is any natural number greater than 1,
and x has no prime factors less than x, then x is prime, then you
get that p is prime.
Marshall
> MoeBlee <jazzm...@hotmail.com> writes:
> > Whadda am I, chopped liver?
>
> Marshall will soon be here to inform you the term du jour is "potted
> plant".
"Chopped liver" as an expression for something being ignored dates
back at least as far as the 1940s.
"Potted plant" dates from the Oliver North trial; it is over 20 years
old
by now, and has lost any "du jour" status it once held. Nonetheless
despite racking my brains I am unable to come up with a winning
neologism as a replacement.
A fifth wheel? Tits on a bishop? Dunsel? A hat full of busted
assholes?
None of these is quite right.
Marshall
Tim Little
> This is art, not science. But in this case, I really do prefer the
> proof by contradiction. I see it as elegant. A direct proof in this
> case feels forced and artificial.
The direct proof is almost identical to the direct proof, only a few
steps shorter.
> One starts with an arbitrary finite nonempty set of primes and shows
> that there must exist a new prime not in the set. Which means any
> finite set of primes can always be extended to a strictly larger
> finite set of primes.
Extension is irrelevant, as there is no need to form successive finite
sets. Using the definition of "infinite" as "exceeding every given
bound", the direct proof shows exactly that for every given bound,
there is a prime exceeding it. How much more direct do you want?
> You probably can find a way, appealing to some axiom or other, but
> that assumes the audience is aware of and accepts that axiom, and
> understands its use.
Only the definition of "infinite". For a proof of infinitude, I would
hope that the audience understands that much.
- Tim
Arturo Magidin
wrote:
Then I would say that the indirect proof is actively misleading,
leading to the impression that multiplying all primes up to a given
bound and adding one will necessarily yield a prime. This is of course
false, and as such I would call this a proof that is pedagogically not
a good idea.
In any case, this lemma requires the result that any positive integer
greater than 1 is divisible by a prime; this result is already
sufficient to finish the proof when you look at p; you are just piling
new conclusions on top of the P/\~P you already have. You can also
conclude that p is half of an odd prime at this point.
--
Arturo Magidin
quasi
wrote:
>On 2010-08-23, quasi <qu...@null.set> wrote:
>> This is art, not science. But in this case, I really do prefer the
>> proof by contradiction. I see it as elegant. A direct proof in this
>> case feels forced and artificial.
>
>The direct proof is almost identical to the direct proof, only a few
>steps shorter.
Based on what you wrote above, shorter is impossible
(but I know what you probably meant to say)
>> One starts with an arbitrary finite nonempty set of primes and shows
>> that there must exist a new prime not in the set. Which means any
>> finite set of primes can always be extended to a strictly larger
>> finite set of primes.
>
>Extension is irrelevant, as there is no need to form successive finite
>sets. Using the definition of "infinite" as "exceeding every given
>bound", the direct proof shows exactly that for every given bound,
>there is a prime exceeding it. How much more direct do you want?
>
>> You probably can find a way, appealing to some axiom or other, but
>> that assumes the audience is aware of and accepts that axiom, and
>> understands its use.
>
>Only the definition of "infinite". For a proof of infinitude, I would
>hope that the audience understands that much.
It depends on the audience.
In any case, I like the usual indirect proof better. It is a matter of
taste, after all.
The indirect proof doesn't depend on requiring the audience to know
the definition of "infinite", but instead relies on the more intuitive
notion of "finite" (with no logical negation needed). And I think the
contradiction, when it happens, is satisfyingly final.
quasi
William Elliot
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> finitely many primes.
It's used to construct the product of all primes.
herbzet
A floppy disk?
--
hz
Rupert
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
>
> Aatu Koskensilta (aatu.koskensi...@uta.fi)
>
> "Wovon man nicht sprechen kann, darüber muss man schweigen"
> - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
You seem to be suggesting that the statement "There are infinitely
many primes" can be proved more elegantly by using some method other
than proof by contradiction. Would you be able to get more specific
about what you have in mind?
Tim Little
> On 24 Aug 2010 01:44:38 GMT, Tim Little <t...@little-possums.net>
>>steps shorter.
>
> Based on what you wrote above, shorter is impossible
True indeed.
>>Only the definition of "infinite". For a proof of infinitude, I would
>>hope that the audience understands that much.
>
> It depends on the audience.
>
> In any case, I like the usual indirect proof better. It is a matter of
> taste, after all.
De gustibus non est disputandum, and all that.
> The indirect proof doesn't depend on requiring the audience to know
> the definition of "infinite", but instead relies on the more
> intuitive notion of "finite" (with no logical negation needed).
If by that you mean "there is no finite set of all primes" is not
quite logically equivalent to "the set of all primes is infinite", I
agree.
- Tim
Tim Little
> Is there some explanation for this curious phenomenon, that people
> should prefer proofs that are, from a logical and mathematical point
> of view, simply needlessly convoluted?
Perhaps in cases like the indirect form of Euclid's proof, it might be
because the indirect proof is more propositional and so logically
"lighter" than the predicate calculus required of the direct proof?
After all, the indirect proof uses a proposition "the set of all
primes is finite" to derive a contradiction and so conclude its
negation. I don't think it need use quantifiers anywhere.
The direct proof seems "heavier" in quantification: at the very least
it goes through "for every finite set of primes, that set is
incomplete" and its predicate transformation to "there does not exist
a finite set of all primes".
So I can see some justification for preferring the indirect proof.
- Tim
Han de Bruijn
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> finitely many primes. Is there some explanation for this curious
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
>
> --
> Aatu Koskensilta (aatu.koskensi...@uta.fi)
>
> "Wovon man nicht sprechen kann, darüber muss man schweigen"
> - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Experienced such a surprise when reading a proof in the book "Complex
made Simple" by David C. Ullrich. Take a look at Theorem 2.2 (Cauchy-
Goursat: Cauchy's Theorem for triangles). Ullrich's Proof on page 23
starts with "Suppose not.", thus suggesting a proof by contradiction.
But the proof is actually a straightforward one, i.e. a direct proof.
As is clear from the following reference:
http://facweb.stvincent.edu/academics/mathematics/CIT/CIT.htm
Han de Bruijn
William Elliot
> On Aug 24, 12:55 am, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:
>> For some reason many people seem to have a peculiar fondness for
>> pointlessly indirect proofs. A more-or-less canonical example is
>> Euclid's proof that there are infinitely many primes. We often see this
>> proof presented starting with a "Suppose there are only finitely many
>> primes." and concluding with a triumphant "A contradiction!". Of course,
>> no actual use is made in the proof of the assumption that there are only
>> finitely many primes. Is there some explanation for this curious
>> phenomenon, that people should prefer proofs that are, from a logical
>> and mathematical point of view, simply needlessly convoluted?
>>
> You seem to be suggesting that the statement "There are infinitely
> many primes" can be proved more elegantly by using some method other
> than proof by contradiction. Would you be able to get more specific
> about what you have in mind?
>
Basically the same proof.
Let p be any prime. Since for all prime q <= p,
not p | 1 + prod{ r prime | r <= p },
there's some prime p1 > p. Subsequently, by induction,
construct a strictly increasing sequence of primes.
Peter Webb
As an example of a direct vs indirect proof, this example is piss-poor.
The only difference between the two proofs is semantic. Both prove that the
primes are infinite by proving they are not finite. Both are *indirect*
proofs.
A direct proof of this theorem would for example establish a bijection
between the primes and N. It could be argued that the Prime Number Thereom
provides a *direct* proof, albeit in a very round about way.
Herman Jurjus
>
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> finitely many primes. Is there some explanation for this curious
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
Imho, the explanation lies in the contrast between mathematical
reasoning and everyday life reasoning.
In everyday life, arguments don't lead to certainty - you can argue for
anything you like and tomorrow someone may find a stronger
counter-argument.
Apparently, even mathematicians are so familiar with everyday life
reasoning, that when they meet an argument in mathematics, they feel the
need for some indication or reminder that this is not just 'an
argument', but more absolute.
So, they're not interested in anything that sounds like a positive
argument, but want to hear something of the form 'there can't possibly
exist a counterexample'.
--
Cheers,
Herman Jurjus
Daryl McCullough
>
>On Aug 23, 7:17=A0pm, stevendaryl3...@yahoo.com (Daryl McCullough)
>wrote:
>> If you appeal to the lemma: If x is any natural number greater than 1,
>> and x has no prime factors less than x, then x is prime, then you
>> get that p is prime.
>
>Then I would say that the indirect proof is actively misleading,
>leading to the impression that multiplying all primes up to a given
>bound and adding one will necessarily yield a prime.
Well, that assumption was not used in the proof I sketched.
Daryl McCullough
>
>> If you appeal to the lemma: If x is any natural number greater than 1,
>> and x has no prime factors less than x, then x is prime, then you
>> get that p is prime.
>
>Then I would say that the indirect proof is actively misleading,
>leading to the impression that multiplying all primes up to a given
>bound and adding one will necessarily yield a prime.
I don't think that's bad. You just have to turn it from an "impression"
to a "conjecture", and then the student can be asked to see if he can
adapt the proof of the infinitude of primes to a proof that for any n,
p_1 * p_2 * ... * p_n + 1 is prime (where p_j means the jth prime).
It seems to work for the first few primes:
2+1 = 3
2*3 + 1 = 7
2*3*5 + 1 = 31
2*3*5*7 + 1 = 211
2*3*5*7*11 + 1 = 2311
...
So it's a really good conjecture that the pattern continues.
But then when you try to construct a proof, you see that the
proof doesn't go through.
I don't think that such an investigation is bad at all, from a pedagogical
point of view.
Frederick Williams
>
> Using the definition of "infinite" as "exceeding every given
> bound", the direct proof shows exactly that for every given bound,
> there is a prime exceeding it.
Pardon?
--
Needle, nardle, noo.
Rupert
>
> - Show quoted text -
Well, we can agree that the proof shows that given any integer there
exists a prime larger than that integer. Aatu seems to be objecting to
inferring from there that there are infinitely many primes by means of
a proof by contradiction. But is there a better way to infer that?
Perhaps Aatu feels one should just treat it as obvious?
Arturo Magidin
> Well, we can agree that the proof shows that given any integer there
> exists a prime larger than that integer. Aatu seems to be objecting to
> inferring from there that there are infinitely many primes by means of
> a proof by contradiction. But is there a better way to infer that?
I *think* that Aatu is not objecting to much, but rather wondering
*why* people seem to very often prefer to take a proof of P->Q (in
this case, if you have a finite set of primes, then there is a prime
not on the set), and present it as a proof by contradiction by saying
"assume ~Q", then doing a proof of P->Q, and then at the end saying
"but then Q and ~Q, contradiction; therefore Q". One example of this
is the proof that the set of primes is not finite, taking Euclid's
proof, pre-pending "assume the list contains all primes", and then
adding at the end "therefore the list does *not* contain all primes,
contrary to our hypothesis, contradiction."
--
Arturo Magidin
Rupert
Yes, fair enough, but the issue is muddied a bit because when we say
"There are infintiely many primes" we are asserting the negation of
the statement "There are finitely many primes", so proving it by
contradiction seems pretty reasonable. But of course Euclid would not
have put it that way.
I should probably check whether Euclid did it by contradiction. Does
anyone know?
Arturo Magidin
> On Aug 25, 10:59 am, Arturo Magidin <magi...@member.ams.org> wrote:
>
>
>
> > On Aug 24, 7:54 pm, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > > Well, we can agree that the proof shows that given any integer there
> > > exists a prime larger than that integer. Aatu seems to be objecting to
> > > inferring from there that there are infinitely many primes by means of
> > > a proof by contradiction. But is there a better way to infer that?
>
> > I *think* that Aatu is not objecting to much, but rather wondering
> > *why* people seem to very often prefer to take a proof of P->Q (in
> > this case, if you have a finite set of primes, then there is a prime
> > not on the set), and present it as a proof by contradiction by saying
> > "assume ~Q", then doing a proof of P->Q, and then at the end saying
> > "but then Q and ~Q, contradiction; therefore Q". One example of this
> > is the proof that the set of primes is not finite, taking Euclid's
> > proof, pre-pending "assume the list contains all primes", and then
> > adding at the end "therefore the list does *not* contain all primes,
> > contrary to our hypothesis, contradiction."
> Yes, fair enough, but the issue is muddied a bit because when we say
> "There are infintiely many primes" we are asserting the negation of
> the statement "There are finitely many primes", so proving it by
> contradiction seems pretty reasonable. But of course Euclid would not
> have put it that way.
>
> I should probably check whether Euclid did it by contradiction. Does
> anyone know?
No, and yes. Euclid did not do the whole argument by contradiction,
but there is a step that he does do by contradiction. Among other
things, Euclid does not talk about "infinite" (the idea of infinite
sets was very difficult for the greeks; cf. Zeno). Euclid states his
theorem as "Prime numbers are more than any assigned quantity" (well,
okay, he said it in ancient Greek). Book IX, Proposition 20. See:
http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html
He assumes you have three given primes, A, B, and C; takes their least
common multiple E, and adds 1. If the result is prime, it is not A, B,
or C because it is more than A, B, and C. If the result is not prime,
then it is divisible (measured) by some prime.
Here is the step where Euclid uses an argument by contradiction: he
argues that if P is that prime, and P is one of A, B, and C, then P
divides E, and also divides E+1, therefore divides the unit, which is
impossible. So P is not A, not B, and not C.
So either way there is a prime that is none of the original three.
He stops there, but concludes that prime numbers are more than any
assigned quantity because the argument easily generalizes.
--
Arturo Magidin
Nam Nguyen
>
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> finitely many primes. Is there some explanation for this curious
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
I actually don't think such an indirect proof is entirely needless
because mathematical reasoning is _supposed to be_ contradiction-
free and hence any conclusion that is a contradiction does seem
to serve a purpose: weeding out some incorrect assumption(s).
As for the "why" I think that somehow mortal beings like us
find intuition more appealing than rational reasoning, at least when
"indirect" proofs are involved. (Indirect proof usually means
"proof" outside the stringent rigid formal proof).
For instance, suppose we happen to live in the time of the Church,
Copernicus and all that, then we "certainly" would have the "proof"
that the Sun circles around the Earth: it rises in the East, climbs
above our heads at noon, and it sinks below the Earth in the West
bringing darkness after which. If one (e.g. Copernicus) doesn't
believe that then we could "rationally convince" the person:
Suppose the Earth circles around the Sun then we'd _always_ see
sunlight and no darkness would fall upon us: but see that's a
_contradiction_ !
Imho, that's the power and appealing of "indirect" proof: short,
sweet, intuitive and doesn't seem require a lot of reasoning to
convince!
Sometimes the mind does seem to fall in love with disguised
misconceptions, doesn't it!
--
-----------------------------------------------------------
I'm not a crank; I'm only just as difficult to reason with.
NN
-----------------------------------------------------------
spudnik
of contradiction, there's a simple proof
of the isomorphism of direct & indirect proof,
about 2 and a half pages that even *I* could comprehend,
including a formula to interconvert.
okay, so, I never tried to use it!
> So either way there is a prime that is none of the original three.
--les ducs d'oil!
http://tarpley.net
--Light, A History!
http://wlym.com
Gerry Myerson
Aatu Koskensilta <aatu.kos...@uta.fi> wrote:
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> finitely many primes. Is there some explanation for this curious
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
Hardy gives the indirect proof on pages 93-94 of A Mathematician's
Apology, and writes,
"The proof is by reductio ad absurdum, and reductio ad absurdum,
which Euclid loved so much, is one of a mathematician's finest weapons.
It is a far finer gambit than any chess gambit: a chess player may offer
the sacrifice of a pawn or even a piece, but a mathematician offers
THE GAME (emphasis in the original)."
Perhaps you can find the psychological attraction of indirect proofs,
even pointlessly indirect proofs, in Hardy's words.
I should add that Hardy writes in a footnote,
"The proof can be arranged so as to avoid a reductio, and logicians
of some schools would prefer that it should be."
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
William Elliot
>>> You seem to be suggesting that the statement "There are infinitely
>>> many primes" can be proved more elegantly by using some method other
>>> than proof by contradiction. Would you be able to get more specific
>>> about what you have in mind?
>>
>> Basically the same proof.
>> Let p be any prime. Since for all prime q <= p,
>> there's some prime p1 > p. Subsequently, by induction,
>> construct a strictly increasing sequence of primes.- Hide quoted text -
>>
>> - Show quoted text -
> Well, we can agree that the proof shows that given any integer there
> exists a prime larger than that integer. Aatu seems to be objecting to
> inferring from there that there are infinitely many primes by means of
> a proof by contradiction. But is there a better way to infer that?
> Perhaps Aatu feels one should just treat it as obvious?
>
For the rest of the proof: let p1 be a prime; p2 be a prime > p1,
and for all n, let p_(n+1) be a prime > p_n. The show the map
f:N -> primes, n -> p_n is an injection. Thus |N| <= |primes|,
which is one definition of infinite. This is a constructive proof.
For non-constructionist, the proof by negation is acceptable, and
as you can see by now, simpler.
Peter Webb
"William Elliot" <ma...@rdrop.remove.com> wrote in message
news:2010082421...@agora.rdrop.com...
Why not explicitly biject the primes with N, using the same construction?
Let the first n elements p(n) on the list correspond to n different primes.
Construct p(n+1) as the lowest prime factor of p(1)*p(2)*p(3)..*p(n) + 1.
This is clearly an injection, and slightly less obviously a bijection
between primes and N.
You can't get much more direct than that.
quasi
If P is the set of primes, then yes, the function p: N -> P is clearly
injective.
>and slightly less obviously a bijection between primes and N.
How do you show that p is surjective?
quasi
Marshall
A proposition 65 sign.*
This is the best fit semantically I've come up with so far,
but it lacks any punch, and is California-specific.
Marshall
Thomas Nordhaus
I think, this has not been proven yet. See
http://www.research.att.com/~njas/sequences/A000945
--
Thomas Nordhaus
Frederick Williams
>
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs.
Here's a situation in which proofs of tautologies must be indirect.
The rules
A, B A & B A & B [A] [~A]
----- ----- ----- : :
A & B A B B & ~B B & ~B
------ ------
~A A
are complete for PC in & and ~. Any proof of a tautology must use one
or both of the indirect proof rules.
--
Needle, nardle, noo.
sttsc...@tesco.net
Yes, but you don't need to "find an extra prime"
For the proof to go through, you are implicitly
assuming unique factorization or at least the
fact that every n >1 has a prime divisor.
Assume the primes are finite in number.
Let L be the LCM of all these primes
GCD(L,L+1) = 1 => no prime divides L+1, a contradiction
quasi
Short, sweet, elegant.
quasi
Peter Webb
"Thomas Nordhaus" <thnor...@yahoo.de> wrote in message
news:i53c93$b94$02$1...@news.t-online.com...
Let me amend my statement "slightly less obviously a bijection" to "its not
at all obvious whether this is a bijection".
I thought I had a simple sieve argument ... I don't.
Arturo Magidin
wrote:
The latter; this is *explicit* in Euclid, not implicit.
> Assume the primes are finite in number.
> Let L be the LCM of all these primes
> GCD(L,L+1) = 1 => no prime divides L+1, a contradiction
Again, this is Euclid's proof cast as a proof by contradiction instead
of a direct proof of "there are more primes than any given number of
primes." The assumption "the primes are finite in number is not
needed", because what you are really concluding is that none of
*these* primes divides L+1. That's all that is needed.
--
Arturo Magidin
Arturo Magidin
> On Wed, 25 Aug 2010 13:52:41 -0700 (PDT), "sttscitr...@tesco.net"
And Euclid's, made into a proof by contradiction by adding an
assumption at the beginning and a hidden step at the end.
--
Arturo Magidin
Bill Dubuque
>>>>
>>>> In the direct proof, one doesn't assume that the list
>>>> of primes is finite. One starts with an arbitrary finite nonempty set
>>>> of primes and shows that there must exist a new prime not in the set.
>>
>>>... and in the "indirect proof" one does exactly the same, except that
>>>one sticks a big neon yellow sticker on the set that says "THIS IS THE
>>>SET OF ALL PRIMES".
>>
>> I think there is a sense in which the indirect proof is more direct
>> than the direct proof.
>>
>> Indirect proof: Assume that p_1, ..., p_n is an enumeration of all
>> the prime numbers. Let p = p_1 * p_2 * ... * p_n + 1. Then p is a
>> new prime number that is not on the list. Contradiction!
>
> Well, except of course that this is incorrect.(-;
> You have no warrant for asserting that p itself must be a prime.
Not true. One *can* infer that p is prime since p>1 and it has
no smaller prime factor. Alternatively one can infer that p = 1
since it is a natural with no prime factors. One can infer all
sorts of nonsense in proofs by contradictions. That's the point.
Here, because we have such strong intuitions about the naturals,
it is sometimes difficlut to focus on one particular contradiction
because there are so many obvious well known theorems about N
that are easy targets for contradictions.
I've emphasized this in the many prior discussions on such, e.g. [1].
--Bill Dubuque
[1] http://google.com/groups?selm=y8zprabvm1a.fsf%40nestle.csail.mit.edu
Bill Dubuque
> For some reason many people seem to have a peculiar fondness for
> pointlessly indirect proofs. A more-or-less canonical example is
> Euclid's proof that there are infinitely many primes. We often see this
> proof presented starting with a "Suppose there are only finitely many
> primes." and concluding with a triumphant "A contradiction!". Of course,
> no actual use is made in the proof of the assumption that there are only
> finitely many primes. Is there some explanation for this curious
> phenomenon, that people should prefer proofs that are, from a logical
> and mathematical point of view, simply needlessly convoluted?
See [1] for references to over 100 butchers of Euclid's proof.
Perhaps you may glean some insight from the discussion there.
For a much less trivial variant you may find it interesting to
consider my ideal-theoretic generalization of Euclid's proof to
arbitrary infinite rings with fewer units than elements. Here the
usual proof [3] is a nonconstructive proof by contradiction, and it
seems to be little-known that it can in fact be made constructive in
a way very analogous to Euclid's proof [4]. To my great surprise, it
took a lot of explanation [5] to convince one number-theorist that my
constructive version is in fact different from the nonconstructive form.
This may give some hint as to just how ingrained the nonconstructive
viewpoint is currently. I'm an exception to the rule since I started out
very constructively at an early age - having been one of the developers
of the Macsyma computer algebra system when I was an MIT student.
Note: as I mentioned here before [2], one can in fact give a variant
of Euclid's proof that *does* depend on the finiteness assumption.
Namely if there were only a finite number of primes then, following
Fermat, this easily yields a contradiction by infinite descent, viz.
given any prime P there exists a prime < P, namely,
any prime factor of: 1 + product {all primes >= P}
--Bill Dubuque
[1] Michael Hardy; Catherine Woodgold. Prime Simplicity.
Math. Intelligencer, v.31, 4, Dec. 2009, 44-52
http://dx.doi.org/10.1007/s00283-009-9064-8
[2] sci.math, 05 Apr 2005, G.H.Hardy gave an invalid proof
of Infinitude of Primes in "AMathematician's Apology"
http://google.com/group/sci.math/msg/5db8ba109b42f7ab
http://google.com/groups?selm=y8zbr8swzaf.fsf%40nestle.csail.mit.edu
[3] http://at.yorku.ca/cgi-bin/bbqa?forum=ask_an_algebraist_2008;task=show_msg;msg=1844.0002
[4] http://www.artofproblemsolving.com/Forum/viewtopic.php?f=61&t=217448&p=1209616
[5] http://at.yorku.ca/cgi-bin/bbqa?forum=ask_an_algebraist_2008;task=show_msg;msg=2069.0001.0001.0002.0001.0001.0001.0001.0001
Archimedes Plutonium
Bill Dubuque wrote:
> Arturo Magidin <mag...@member.ams.org> wrote:
> > tevendaryl3...@yahoo.com (Daryl McCullough)> wrote:
> >> Arturo Magidin says...
> >>>On Aug 23, 2:20=A0pm, quasi <qu...@null.set> wrote:
> >>>>
> >>>> In the direct proof, one doesn't assume that the list
> >>>> of primes is finite. One starts with an arbitrary finite nonempty set
> >>>> of primes and shows that there must exist a new prime not in the set.
> >>
> >>>... and in the "indirect proof" one does exactly the same, except that
> >>>one sticks a big neon yellow sticker on the set that says "THIS IS THE
> >>>SET OF ALL PRIMES".
> >>
> >> I think there is a sense in which the indirect proof is more direct
> >> than the direct proof.
> >>
> >> Indirect proof: Assume that p_1, ..., p_n is an enumeration of all
> >> the prime numbers. Let p = p_1 * p_2 * ... * p_n + 1. Then p is a
> >> new prime number that is not on the list. Contradiction!
> >
Daryl should have said "step one: definition of what prime is", then
the rest
all follows, and the unique prime factorization theorem comes in both
the
direct and indirect proof.
> > Well, except of course that this is incorrect.(-;
> > You have no warrant for asserting that p itself must be a prime.
>
> Not true. One *can* infer that p is prime since p>1 and it has
> no smaller prime factor. Alternatively one can infer that p = 1
> since it is a natural with no prime factors. One can infer all
> sorts of nonsense in proofs by contradictions. That's the point.
No, sorry, Bill, you made a mistake. And the reason you made the
mistake
is that you never bothered to write out a full proof but rather like
most
people take all these paragraph proofs with shortcut the logic.
Bill, if you had written out the proof to some extent and having the
definition of
prime in the first step, so you and every reader knows what a prime
number is
during and throughout the proof, then that would eliminate you
complaint
BD>Alternatively one can infer that p = 1
BD> since it is a natural with no prime factors. One can infer all
BD> sorts of nonsense in proofs by contradictions. That's the point.
One of the problems of the Indirect method is that so many
mathematicians have built
up these fakery myths about the method. You mention one of those
absurd myths
that "all sorts of nonsense in proofs by contradiction"
I dare you to show any alternative to the Euclid IP indirect. I say
there are absolutely no
alternatives. There can be longer proofs with excess baggage, but all
of them that are valid
end up with P being necessarily prime and thus dissolving assumption.
Now there can be a
different starting definition of prime, as what Dik Winter gave many
years ago back, but even
his alternative definition ended up with P necessarily prime.
So you made a mistake Bill, and probably because you are familar with
alternative different proofs of the Infinitude of Primes and is thus
mixing in those different proofs.
But you are simply wrong above and I can prove you are wrong because
if you can do a valid
Euclid IP Indirect, you should be able to do a Infinitude of Twin
Primes. And with your comment above, you cannot do Twin Primes.
>
> Here, because we have such strong intuitions about the naturals,
> it is sometimes difficlut to focus on one particular contradiction
> because there are so many obvious well known theorems about N
> that are easy targets for contradictions.
>
I challenge you to clarify that myth belief of yours-- "indirect
methods
have a menu of contradictions to chose from" I do not buy that idea,
and
I believe you are wrong on this idea and thus you are spreading false
myths.
I believe all of mathematics is so tightly wound, that the indirect
method proof,
all of them have a unique contradiction given starting elements.
> I've emphasized this in the many prior discussions on such, e.g. [1].
>
> --Bill Dubuque
>
> [1] http://google.com/groups?selm=y8zprabvm1a.fsf%40nestle.csail.mit.edu
You have emphasized, Bill, but really are you not just sloppy in your
proof methods
and fallen into a false conclusion that Indirect has a menu of
contradictions to chose from.
I suspect you never studied Symbolic Logic, because, again, math is so
tight that given
a set of starting elements (a) definition of prime (b) assume finite
(c) form Euclid's number,
that given those three elements, the contradiction is unique to those
three elements.
Please, do not bother to respond and behave like Chandler Davis and
Julia F. Knight, and
run away and hide, rather than concede that AP is correct and you are
wrong. Because most
people in math behave like Davis and Knight, -- run away and hide when
found wrong.
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
Bill Dubuque
Would you also consider the proof below equivalent? At some point
you will be foreced to define "equivalent" - which is difficult
if not impossible.
Note: as I mentioned here before [1], one can in fact give a variant
of Euclid's proof that *does* depend on the finiteness assumption.
Namely if there were only a finite number of primes then, following
Fermat, this easily yields a contradiction by infinite descent, viz.
given any prime P there exists a prime < P, namely,
any prime factor of: 1 + product {all primes >= P}
--Bill Dubuque
[1] sci.math, 05 Apr 2005, G.H.Hardy gave an invalid proof
Archimedes Plutonium
you going to run away
and hide like Chandler Davis or Julia Knight?
Bill Dubuque wrote:
(snipped)
>
> Would you also consider the proof below equivalent? At some point
> you will be foreced to define "equivalent" - which is difficult
> if not impossible.
>
> Note: as I mentioned here before [1], one can in fact give a variant
> of Euclid's proof that *does* depend on the finiteness assumption.
> Namely if there were only a finite number of primes then, following
> Fermat, this easily yields a contradiction by infinite descent, viz.
>
> given any prime P there exists a prime < P, namely,
> any prime factor of: 1 + product {all primes >= P}
>
> --Bill Dubuque
>
> [1] sci.math, 05 Apr 2005, G.H.Hardy gave an invalid proof
> of Infinitude of Primes in "AMathematician's Apology"
> http://google.com/group/sci.math/msg/5db8ba109b42f7ab
> http://google.com/groups?selm=y8zbr8swzaf.fsf%40nestle.csail.mit.edu
First off, thanks for the reference to one of my old threads.
Now I must admit, Bill, that I never really dug into your Infinite
Descent of Infinitude of Primes.
I am the undisputable expert, master of Euclid's IP, direct and
indirect. But I have no
claim to any expertise of Infinite Descent on Euclid's IP, so I am
rusty of the starting block
in using Fermat's Infinite Descent.
But seeing that you are rather, sloppy with forgetting the definition
of prime
in Indirect Euclid IP and thence making mistakes, that I suspect your
claims of Fermat's Infinite Descent is likely to have holes in it
also.
So are you up to the challenge Mr. Bill Dubuque?
If my Euclid IP, Indirect is correct, then it yields a proof of the
Infinitude of Twin Primes as
given below:
AP's INDIRECT Infinitude of Regular Primes proof in short form:
1) Definition of prime
2) Hypothetical assumption, suppose set of primes 2,3,5,7,.. is
finite with P_k the last and final prime
3) Multiply the lot and add 1 (Euclid's number) which I call W+1
4) W+1 is necessarily prime from the definition of prime and the
assumption space
5) contradiction to P_k as the last and largest prime
6) set of primes is infinite.
AP INDIRECT Infinitude of Twin Primes proof, in short form:
(1) Definition of prime
(2) Hypothetical assumption, suppose the set of primes 2,3,5,7,.. is
finite with P_n and P_n+2 as the last and final two primes in
existence
(3) Multiply the lot and add 1 and subtract 1 (Euclid's numbers)
which
I will call W+1 and W-1
(4) W+1 and W-1 are necessarily two new primes from the definition
of
prime
and from the assumption space
(5) Contradiction to P_n+2 being the last and largest prime
(6) This proof is recursive in that once W-1, W+1 is fetched, we
insert them
into a next larger finite set and retrieve a new pair of twin primes
call them
Y-1, Y+1 ad infinitum
(7) Twin primes set is infinite
So, Mr. Dubuque, if your Fermat's Infinite Descent, Indirect on
Euclid's IP is correct,
then why is it unable to deliver a proof of the Infinitude of Twin
Primes? Is it because
there is a hole and gap in your reasoning? I think so, only not able
to place a finger on
the mistake as of yet.
If you have a correct proof, because you use the same elements as I do
(a) definition of
prime (b) assume false (c) form Euclid's Number. You use the same
elements, so you should
be able to deliver Twin Primes.
But maybe the flaw is Bill, that you cannot do a reductio ad absurdum
on Mathematical Induction itself, and that is what you have done. You
can do a reductio ad absurdum with Mathematical Induction in a later
steps but not in the assumption step itself. So maybe, I am
not sure, your mistake is that your Fermat Infinite Descent, since it
cannot deliver infinitude
of Twin Primes is a bogus proof because your hypothetical assumption
incorporates Math
Induction. Which is like saying "suppose hypothetically a axiom of
mathematics is false."
So is that the flaw in your Fermat's Infinite Descent? I think so, but
then again, you never really wrote out your alleged proof in long
form, but always these short, cute paragraphs with
leaps of mistakes in between.
Archimedes Plutonium
Induction into the reductio ad absurdum assumption step.
--- quoting Bill Dubuque's alleged proof ---
SURPRISE One can bypass the lemma, yielding a self-contained
'elementary'
proof, by 'inlining' the lemma into the theorem (in the same way that
the
classic proofs of unique factorization by Klappauf, Lindemann,
Zermelo
inline Euclid's Lemma on the Prime Divisor Property: P|AB => P|A or P|
B).
To do this smoothly we employ an alternative definition of 'prime'
that
is trivially seen to be equivalent to the standard definition, namely
DEFINITION P is prime if P is the least factor>1 of an integer>1
THEOREM There are infinite number of primes.
PROOF Suppose not, i.e. suppose there are only a finite number of
primes.
We proceed by descent: given any integer N>1 we deduce there is a
prime < N.
Let S be the product of all primes >= N (convention: S = 1 if no
primes >= N)
Let P be the least factor>1 of S+1. By definition P is prime. But P is
not
one of the primes >= N since these leave remainder 1 when divided into
S+1.
So P < N. This implies that among the primes there is an infinite
descending
sequence of positive integers, a contradiction. QED
--- end quoting Bill Dubuque's alleged proof ---
One of the reasons I do a "short form" and "long form" is because in
the long form
we see the steps with precision and the reasons. Bill only gives a
short form above
but the mistake and why it is no proof at all is because he is making
a axiom of mathematics
as his hypothetical assumption space.
I write this post not to belittle Bill and not to be pointing out
errors. I write this post because
of the important lesson, that if a proof in mathematics is correct, it
should lead to other new
proofs. Fake proofs are dead enders. Wiles's FLT is a dead ender.
Appel and Haken's 4 color
mapping is a dead ender. Hales's Kepler Packing is a dead ender.
A true proof, leads to a newer true proof. The true Euclid IP,
Indirect leads to the proof of
Infinitude of Twin Primes. If Bill's Fermat Infinite Descent was true,
it should lead to Infinitude of Twin Primes, but it does not, for it
is a fake proof and a dead end.
Bill Taylor
Apologies if I'm repeating some stuff - I haven't caught up yet!
The basic question is a very good one, and thanks be to Aatu for
raising it.
I think there IS a general perception that indirect proofs tend to be
slicker and quicker than constructive ones, (if rather less
enlightening).
I don't know if this perception is justified, but I suspect it's a big
contribution to their populasrity. Another big contribution is, that
Euclid was MADLY keen on reductio, and tended to use it even when
another method was available. This taste lingers on right up to now.
One thing that might help us to muse on the topic is this:-
Can anyone produce an example of a theorem that is provable
both by reductio and by construction, in which the basic proof
ideas are ESSENTIALLY DIFFERENT. This last proviso OC rules
out Aat'u cases where one might tack on a prescript & postscript.
Anyone? I suspect the Fundamental Thm of Algebra might be
a candidate, but are there simpler ones?
Aatu's comment that two of the most commonly (mis-)proved
examples being Prime-Infinitude and Caqntor-Uncountability,
is VERY INTRIGUING. It is intriguing because, in a structural
sense, these two examples are almost the same!
In Euclid, one shows that any finite list of primes can be used
to generate a prime not on the list; and
In Cantor, one shows that any countable list of reals can be used
to generate a real not on the list!
The parallel is really quite striking and cute!
I always made a point of notng this comparison to my 1st-year
students when (having earlier done Euclid) we came to do Cantor.
Oddly, no net-crackpots ever object to the former, whereas the latter
attaract them like flies around rotting meat!
Maybe it's the "uncountable" smell that draws them...
Finally, I would like to observe an irritation that always annoyed me
with the standard presentation of Euclid, and which I was careful
to avoid (yet verbally emphasising) with my students.
The standard approach has G = 2*3*5*...*p + 1
EITHER being a prime
OR having prime factors which must thus not be in the list.
This dichotomy is inelegant and unnecessary!
Provided one has been careful to previously prove (as is required
anyway)
that every plural natural is DIVISIBLE BY some prime, (allowing itself
OC),
then all one needs to do is observe that G above must thus be
divisible
by a prime, and IT CAN'T BE any on the list! Q.E.D.
The previous lemma - always div by a prime, needn't be explicitly
proved beyond observing that, though "obvious" it still NEEDS a proof,
and verbally outlining the trivial proof by (complete) induction.
As I say, I always did it this way, (while observing that there might
be two cases, just for clarity, but keeping it out of their notes);
and I earnestly enjoin anyone else teaching this topic to do the same!
Once again, thanks Aatu for initiating an interesting thread!
-- Beaming Bill
** I don't know about free will, but I certainly believe in free whim!
Archimedes Plutonium
far more
damaging to students learning than simply mistakes of calculation. We
have
big mistakes and small mistakes.
The mistake that Bill makes in the below post is his idea that in the
Indirect
method of math proof, there is a menu of choices of contradiction that
one can
use. That mistake is a myth and it arises not because mathematics is
like that,
but because of sloppy mathematicians who jump into the middle of a
proof
without ever having the full body of steps of the proof. So if you
forget a step,
such as where Bill forgets to define prime in step one, then of
course, Bill would
think there are a hundred variant different proofs all with a
different contradiction.
But in reality, mathematics is so tightly wound, that the elements of
a proof force it
to have only one unique contradiction.
So the myth of Indirect that "any old contradiction will prove it"
arose from sloppy
provers who simply could never assemble all the necessary steps and
who forgot
whole portions.
Bill Dubuque wrote:
(snipped)
>
> Not true. One *can* infer that p is prime since p>1 and it has
> no smaller prime factor. Alternatively one can infer that p = 1
> since it is a natural with no prime factors. One can infer all
> sorts of nonsense in proofs by contradictions. That's the point.
>
When a sloppy author of a proof forgets to put the definition of prime
in step one, then of course, yes, in such a sloppy attempt, hundreds
of contradictions can be chased after. Not because math is like that
but because of a careless and sloppy proof attempt.
When it be known, math has a unique contradiction proof given a set of
facts. So that the Euclid Indirect Infinitude of Primes has only one
unique
contradiction and any others, are simply excess baggage or sloppy and
missed
steps.
> Here, because we have such strong intuitions about the naturals,
> it is sometimes difficlut to focus on one particular contradiction
> because there are so many obvious well known theorems about N
> that are easy targets for contradictions.
>
It is statements like this that do more harm to students than most
any
other harm, because they carry away a huge generalized mistake. They
think
that all Indirect proofs have massive numbers of alternative proofs,
all different
and all valid. When in reality, it is just sloppy mathematicians
leaving out
vital steps that causes this menu of contradictions.
> I've emphasized this in the many prior discussions on such, e.g. [1].
>
> --Bill Dubuque
Bill forgot to have step one as the definition of prime number and
that mistake led him
to think P=1 is a viable alternative.
--- quoting my old Indirect proof in long-form ---
INDIRECT (contradiction) Method, Long-form; Infinitude of Primes
Proof and the numbering is different to show the reductio ad
absurdum
structure as given by Thomason and Fitch in Symbolic Logic book.
(1) Definition of prime as a positive integer divisible
only by itself and 1.
(2) The prime numbers are the numbers 2,3,5,7,11, ..,pn,... of set S
Reason: definition of primes
(3.0) Suppose hypothetically, S is finite, with 2,3,5, ..,p_n as the
complete series set
with p_n the largest prime Reason: this is the supposition step
(3.1) Set S are the only primes that exist Reason: from step (3.0)
(3.2) Form W+1 = (2x3x5x, ..,xpn) + 1. Reason: can always operate and
form a new number
(3.3) Divide W+1 successively by each prime of
2,3,5,7,11,..pn and they all leave a remainder of 1.
Reason: unique prime factorization theorem
(3.4) W+1 is necessarily prime. Reason: definition of prime, step
(1) and (3.3) because the only numbers that divide into W+1 is 1 and
W+1.
(3.5) Contradiction Reason: pn was supposed the largest prime yet we
constructed a new prime, W+1, larger than pn
(3.6) Reverse supposition step. Reason (3.5) coupled with (3.0)
(4) Set of primes are infinite Reason: steps (1) through (3.6)
--- end quoting my old proof in long form ---
Now Bill thinks there are many alternative proofs for Indirect, all
distinct and valid. I say
he is wrong and that if he were not sloppy by missing steps, the proof
is unique
to a unique contradiction.
Now in the above, suppose Bill forgets in the assumptive step to list
the finite set of
primes sequentally and forgets to say that p_n is the last and largest
prime? Then, does not that
sloppiness translate into Bill saying that there are a hundred
variants or alternatives of
proofs by Indirect? Of course so.
So we see in math, that sloppiness becomes channelled into the
education of mathematics as to describe the Indirect Method as a menu
of contradictions when in truth, the Indirect has a
unique proof by a unique contradiction.
And my claim is supported by the idea that the Indirect Method is a
Gambit on the entire subject of mathematics. Such a gambit could not
be a proof method if it had such "looseness
about" where there are thousands of variants all valid.
The entire Indirect method exists because math is so interconnected
and tightly wound
that a proof has a unique line of thought (other than adding on excess
baggage).
In other words, I am using Indirect Method to prove that Bill
Dubuque's concept of the Indirect Method is out of whack.
My claim of a unique contradiction is also supported by a idea that if
a valid proof exists, it is
able to be carried over and prove a new theorem of mathematics such as
Infinitude of Regular Primes, indirect, proving Infinitude of Twin
Primes. Only one unique proof of Euclid IP Indirect
can prove infinitude of Twin Primes. This means that the one unique
proof is the only valid proof and the others have gaps and holes in
them.
So the message of this post or theme is that so much harm is done with
these false
characterizations of the Indirect Method and it causes students to go
astray for years and
decades in math.
Archimedes Plutonium
Archimedes Plutonium wrote:
Bill Dubuque wrote:
Through the years since Bill posted the above monstrosity, he has
never been
willing nor able to expand upon any of it. You ask him any question
about the above
and he says the reader is not understanding, or he avoids or ignores
any questions.
This sentence is perhaps in competition for being the fruitcake
sentence in math
proving literature:
"This implies that among the primes there is an infinite descending
sequence of positive integers, a contradiction."
But it is not that sentence that bothers me as much as these sentences
by
Bill Dubuque:
Bill Dubuque wrote:
> Not true. One *can* infer that p is prime since p>1 and it has
> no smaller prime factor. Alternatively one can infer that p = 1
> since it is a natural with no prime factors. One can infer all
> sorts of nonsense in proofs by contradictions. That's the point.
>
>
> Here, because we have such strong intuitions about the naturals,
> it is sometimes difficlut to focus on one particular contradiction
> because there are so many obvious well known theorems about N
> that are easy targets for contradictions.
It is those sentences by Bill that paint a total false picture of the
Indirect
Method as some sort of cafe menu of a selection of choices for your
proof by contradiction, that is anti-educational. When you know
mathematics well
enough, you begin to realize that the Indirect Method works only
because math
is so tightly wound up of its interrelated truths and facts, that it
cannot possibly
have a spectrum of choices for a contradiction.
The only spectrum of choices for a contradiction is when Bill forgets
half a dozen needed
steps in the proof and is sloppy all along the argument. When you are
sloppy, then you
boast about options of contradictions.
So, pray tell, Bill, why have you never expanded your alleged Infinite
Descent into a long form
argument showing reasons and steps? Is it because, you have no proof
but just a cascade
of obnoxious mistakes? Tell me, is there a single other person at MIT
or even one of your students at MIT that buys your contraption?
If math were art, and art meant good portrait paintings as accurate as
a photograph, then
Bill Dubuque's Fermat's Infinite Descent of Euclid Infinitude of
Primes is a deKonig abstract
painting in a gallery filled with excellent portrait paintings. As Red
Green of the Red Green
possum lodge tv show said "if I can paint it, it is not art."
So what is this sentence, Bill :
>This implies that among the primes there is an infinite
> descending sequence of positive integers, a contradiction.
Is it a joke that never caught laughing traction? Is it MIT's attempt
at humour
in mathematics that is otherwise glib and grim? Or maybe you are
trying to
impress Barbara Knox? Barbara, are you impressed with that sentence?
OwlHoot
> In article <i4ugl00...@drn.newsguy.com>,
> stevendaryl3...@yahoo.com (Daryl McCullough) wrote:
>
> > >....
> > >The direct proof requires an extra fact (that every number can be
> > >written as a product of primes) that is not necessary in the indirect
> > >proof. Also, the new prime that is constructed in the indirect proof is
> > >defined explicitly, while the new prime that is constructed in the direct
> > >proof is only given indirectly.
>
> > What I said was stupid. The indirect proof *also* requires the same
> > fact, that every number can be written as a product of primes. Otherwise,
> > knowing that p is not divisible by any other prime does not prove that it is
> > prime....
>
> My defence of Euclid will probably be lost in the background noise
> of this thread; but I'll try.
>
> (1) Daryl is mistaken above. Some people have tried to unearth the
> prime factorization theorem from Euclid, but it requires a vivid
> imagination. The relevant step in IX.20 is (in Heath's translation):
> "Next, let EF not be prime; therefore it is measured by some prime
> number." Heath adds the reference [VII.31].
>
> The statement of VII.31 is "Any composite number is measured by
> some prime number", and indeed the proof of IX.20 requires only at least
> one prime factor.
>
> (2) The common misunderstanding of Euclid IX.20 is due to the modern
> restatement "There are infinitely many primes". Infinite sets were not
> explicitly part of mathematics until the 19th century. The Greeks were
> very cagey about the actual infinite, and Euclid's claim is much more
> cautious: given any "multitude" (finite list) of primes, you can find
> another one.
>
> Of course it follows that (in modern terms) the set of all prime
> numbers is infinite. But it's *this* *extra* *step* which needs an
> indirect proof.
>
> Nobody will read this, but my conscience is eased. ;-(
>
> Ken Pledger.
Hmm, that's interesting. I think it's fair to say that most
people today would be rather cagey about maths systems with
an infinite number of axioms.
But the way Euclid expressed his prime number theorem seems
somewhat analogous, or vaguely reminiscent let's say, of
Godel's undecidability proof.
So, who knows, perhaps in another 2000 years people will be
merrily discussing and proving results about systems with
an infinite number of axioms, despite the idea probably
seeming nonsensical to us (me included) today.
Cheers
John Ramsden