How many diff kinds of proof exist?
Jan Stevens
Michael A. Stueben wrote:
>
> I was trying to list the different kinds of proof for my H.S.
> precalculus students. So I gave direct, indirect, math
> induction and proof by contraposition. Fine. But later I
> thought what about this: proof by example (offer am
> illustration of a situation or give directions for a
> construction)? Or proof by verification
> (substitute and complete a calculation). Then proof by cases
> could be a proof made up of a mixture of all types of proof.
You missed proof by intimidation.
--
email: ste...@math.chalmers.se
Matematiska Institutionen
Chalmers Tekniska H"ogskola
SE 412 96 G"oteborg
Sweden
Herman Rubin
In article <E3ov6...@pen.k12.va.us>,
Michael A. Stueben <mstu...@pen.k12.va.us> wrote:
>I was trying to list the different kinds of proof for my H.S.
>precalculus students. So I gave direct, indirect, math
>induction and proof by contraposition. Fine. But later I
>thought what about this: proof by example (offer am
>illustration of a situation or give directions for a
>construction)? Or proof by verification
>(substitute and complete a calculation). Then proof by cases
>could be a proof made up of a mixture of all types of proof.
>as the MAIN methods and the rest as MINOR methods. Are there
>more methods? Is all of this just really hair splitting and
>pedantry? Maybe, but its kinda fun.
> +----------------------------------------------------------+\
> | --From Michael Stueben: high school math/C.S. teacher ||
> | collector of mathematical humor and education theories ||
> | E-mail address: mstu...@pen.k12.va.us ||
> +----------------------------------------------------------||
> \----------------------------------------------------------\|
Instead of this, how about teaching them the complete set of rules
of proof, and how to use them? It is quite common that a proof will
use many of them.
But proof by induction is only a method of proof in the integers, or
if one uses transfinite induction, for ordinals. It is not a general
type of proof.
The entire set of rules for formal proofs form a page or two. Instead
of beating around the bush, just show them a good description of them.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hru...@stat.purdue.edu Phone: (317)494-6054 FAX: (317)494-0558
Michael A. Stueben
I was trying to list the different kinds of proof for my H.S.
precalculus students. So I gave direct, indirect, math
induction and proof by contraposition. Fine. But later I
thought what about this: proof by example (offer am
illustration of a situation or give directions for a
construction)? Or proof by verification
(substitute and complete a calculation). Then proof by cases
could be a proof made up of a mixture of all types of proof.
Well this is getting interesting. I classified the first four
as the MAIN methods and the rest as MINOR methods. Are there
more methods? Is all of this just really hair splitting and
pedantry? Maybe, but its kinda fun.
---
Andrew Thall
In article <32D3A3...@math.chalmers.se>,
Jan Stevens <ste...@math.chalmers.se> wrote:
>Michael A. Stueben wrote:
>>
>> I was trying to list the different kinds of proof for my H.S.
>> precalculus students. So I gave direct, indirect, math
>> induction and proof by contraposition. Fine. But later I
>> thought what about this: proof by example (offer am
>> illustration of a situation or give directions for a
>> construction)? Or proof by verification
>> (substitute and complete a calculation). Then proof by cases
>> could be a proof made up of a mixture of all types of proof.
>
>
>
Also Proof by Least Astonishment.
("I'd be surprised if it weren't true.")
--Andrew.
--
"I shall drink beer and eat bread in the House of Life."
Angelo Vistoli
> Michael A. Stueben wrote:
> >
> > I was trying to list the different kinds of proof for my H.S.
> > precalculus students.
...
How about proof by hallucination? It is a technique I have used a lot.
Angelo
--
Angelo Vistoli
Dipartimento di Matematica Department of Mathematics
Universita` di Bologna Harvard University
Marnix Klooster
In article <E3ov6...@pen.k12.va.us>,
Michael A. Stueben <mstu...@pen.k12.va.us> wrote:
> >I was trying to list the different kinds of proof for my H.S.
hru...@b.stat.purdue.edu (Herman Rubin) wrote:
> Instead of this, how about teaching them the complete set of rules
> of proof, and how to use them? It is quite common that a proof will
> use many of them.
[...]
> The entire set of rules for formal proofs form a page or two. Instead
> of beating around the bush, just show them a good description of them.
May I suggest the book "A Logical Approach to Discrete Math" by
David Gries and Fred B. Schneider (Springer, 1993). It teaches
essentially two things: It gives a method for constructing and
writing proofs, and it applies this method in the area of
discrete mathematics. The former part might be of use to you.
The method of proof is based on calculation.
As an example, let us prove where the functions x|->x^2-2 and
x|->3*x-2 are equal. We calculate for all real x
x^2-2 = 3*x-2
== <subtract 3*x-2 from both sides>
x^2-3*x = 0
== <factor x out>
x*(x-3) = 0
== <property of * and 0>
x=0 \/ x=3
So the functions are equal at x=0 and at x=3. (^ is
to-the-power, == stands for logical equivalence, \/ for logical
or, and <...> are hints.)
For more information on this proof style, and its application in
high school mathematics, see
http://www.cs.cornell.edu/Info/People/gries/Logic/Introduction.html
http://cs.anu.edu.au/~Jim.Grundy/schoolmath/schoolmath.html
If you do use this method in high school, please share your
experiences!
> Herman Rubin
Groetjes,
<><
Marnix
--
Marnix Klooster | If you reply to this post,
mar...@worldonline.nl | please send me an e-mail copy.
Hauke Reddmann
Jan Stevens (ste...@math.chalmers.se) wrote:
: Michael A. Stueben wrote:
: >
: > I was trying to list the different kinds of proof for my H.S.
: > induction and proof by contraposition. Fine. But later I
: > thought what about this: proof by example (offer am
: > illustration of a situation or give directions for a
: > construction)? Or proof by verification
: > (substitute and complete a calculation). Then proof by cases
: > could be a proof made up of a mixture of all types of proof.
:
:
:
: You missed proof by intimidation.
Is this related to proof by inquisition?
"Now do we have to be unkind first?"
--
Hauke Reddmann <:-EX8
fc3...@math.uni-hamburg.de PRIVATE EMAIL
fc3...@rzaixsrv1.rrz.uni-hamburg.de BACKUP
redd...@chemie.uni-hamburg.de SCIENCE ONLY
Michael A. Stueben
Yeah, there is a bunch of joke proof methods listed somewhere:
1. Proof by hearsay: "Prof. Rubin told me it was true."
2. Prove by accident: "Holy Smokes what do we have here."
3. proof by intimidation: "If you can't see that this is true
then you are in the wrong field."
etc.
Herman Rubin
In article <E3r15...@pen.k12.va.us>,
>1. Proof by hearsay: "Prof. Rubin told me it was true."
>2. Prove by accident: "Holy Smokes what do we have here."
>3. proof by intimidation: "If you can't see that this is true
>then you are in the wrong field."
>etc.
> +----------------------------------------------------------+\
> | --From Michael Stueben: high school math/C.S. teacher ||
> | collector of mathematical humor and education theories ||
> | E-mail address: mstu...@pen.k12.va.us ||
> +----------------------------------------------------------||
> \----------------------------------------------------------\|
If a procedure cannot, at least in principle, be expanded to a formal
procedure, which a computer given a simple proof-checking algorithm
could check to be a proof, it is not a proof.
Checking a formal proof is something which requires just an ability
to see that the i's are dotted and the t's are crossed, and simple
things like that, and does not require understanding whu it is of
importance. Finding proofs, and deciding what is worth provin, is
not of this nature.
Herman Rubin
In article <32d4c500...@news.worldonline.nl>,
Marnix Klooster <mar...@worldonline.nl> wrote:
>In article <E3ov6...@pen.k12.va.us>,
>hru...@b.stat.purdue.edu (Herman Rubin) wrote:
This might be in the exercises, but it is using two rules, and
in an overly restrictive manner. The rules are the rules of
equality, and that a product of real numbers is 0 if and only
if one of the factors is 0.
The first of these is a general property, and should be taught in
generality. The second requires the properties of the real numbers.
Which are not general rules.
Meanwhile, the general rules of proof remain even unknown to the
student. Whatever bad intuition the student gets, like assuming
that variables can only be used for numbers, etc., get entrenched
and are hard to remove.
To do a logical approach requires using logic. This is only hard
if one makes it a mystery not suitable for young minds. It then
becomes a mystery for older minds.
Marnix Klooster
vis...@math.harvard.edu (Angelo Vistoli) wrote:
> In article <32D3A3...@math.chalmers.se>, Jan Stevens
> <ste...@math.chalmers.se> wrote:
>
> > Michael A. Stueben wrote:
> > >
> > > I was trying to list the different kinds of proof for my H.S.
> > > precalculus students.
>
> ...
>
> How about proof by hallucination? It is a technique I have used a lot.
That must be a close relative of proof by intimidation, which
I've seen quite often.
> Angelo
Herman Rubin
In article <32da6d4...@news.worldonline.nl>,
Marnix Klooster <mar...@worldonline.nl> wrote:
>hru...@b.stat.purdue.edu (Herman Rubin) wrote:
>> In article <32d4c500...@news.worldonline.nl>,
>> Marnix Klooster <mar...@worldonline.nl> wrote:
>> >May I suggest the book "A Logical Approach to Discrete Math" by
>> >David Gries and Fred B. Schneider (Springer, 1993). It teaches
>> >essentially two things: It gives a method for constructing and
>> >writing proofs, and it applies this method in the area of
>> >discrete mathematics. The former part might be of use to you.
>> >The method of proof is based on calculation.
..................
>What do you mean with the `overly restrictive' bit? Perhaps you
>mean that this proof format seems too rigid to be generally
>useful. But in my experience, and that of others, this isn't so.
>Linear (calculational) derivations are often a very effective to
>express an argument. (Read Gries-Schneider for more and better
>examples.)
>> Meanwhile, the general rules of proof remain even unknown to the
>> student. Whatever bad intuition the student gets, like assuming
>> that variables can only be used for numbers, etc., get entrenched
>> and are hard to remove.
>> To do a logical approach requires using logic. This is only hard
>> if one makes it a mystery not suitable for young minds. It then
>> becomes a mystery for older minds.
>And that is exactly what Gries and Schneider do. They begin by
>teaching the equational logic, as a general tool applicable to
>many fields of mathematics. They try to de-mystify logic, and
>make it practically useful.
"Equational logic" is not even that well defined, unless it is
restricted to particular mathematical structures. There is the
one major rule, which is far more general, and that is the rule
of equality.
But in the understanding of logic, this rule is but one of many,
and it is even possible to dispense with it, although I certainly
would not want to. But the full sentential and predicate calculus
can be taught in elementary school, as has been done by those who
understand it. Equality slides in as just another rule.
Marnix Klooster
hru...@b.stat.purdue.edu (Herman Rubin) wrote:
> In article <32d4c500...@news.worldonline.nl>,
> Marnix Klooster <mar...@worldonline.nl> wrote:
> >May I suggest the book "A Logical Approach to Discrete Math" by
> >David Gries and Fred B. Schneider (Springer, 1993). It teaches
> >essentially two things: It gives a method for constructing and
> >writing proofs, and it applies this method in the area of
> >discrete mathematics. The former part might be of use to you.
> >The method of proof is based on calculation.
[snipped example calculational proof]
> This might be in the exercises, but it is using two rules, and
> in an overly restrictive manner. The rules are the rules of
> equality, and that a product of real numbers is 0 if and only
> if one of the factors is 0.
>
> The first of these is a general property, and should be taught in
> generality. The second requires the properties of the real numbers.
> Which are not general rules.
I agree completely -- perhaps you misunderstood. What I meant
was that the Gries-Schneider book does teach two things, and
teaches them separately: the general principles of proof
construction, and how to apply them in the field of Discrete
Math. I gave the example above to show what a typical proof in
this format looks like.
What do you mean with the `overly restrictive' bit? Perhaps you
mean that this proof format seems too rigid to be generally
useful. But in my experience, and that of others, this isn't so.
Linear (calculational) derivations are often a very effective to
express an argument. (Read Gries-Schneider for more and better
examples.)
> Meanwhile, the general rules of proof remain even unknown to the
> student. Whatever bad intuition the student gets, like assuming
> that variables can only be used for numbers, etc., get entrenched
> and are hard to remove.
>
> To do a logical approach requires using logic. This is only hard
> if one makes it a mystery not suitable for young minds. It then
> becomes a mystery for older minds.
And that is exactly what Gries and Schneider do. They begin by
teaching the equational logic, as a general tool applicable to
many fields of mathematics. They try to de-mystify logic, and
make it practically useful.
> Herman Rubin
Robert E Sawyer
If you just want an outline, the BETA Mathematics Handbook (1990, p13),
summarizes 14 methods of proof on one page.
--
Robert E Sawyer
so...@pacbell.net
Brian Borchers
I've looked through the Griess and Schneider materials, and they look
interesting. However, one thing that seemed to be lacking was discussion
of how to read and write proofs in conventional mathematical English.
Given that students will ultimately have to read and write proofs in
this style, how do you motivate the transition from proofs in this
very formalized style to proofs written in English?
--
Brian Borchers borc...@nmt.edu
Department of Mathematics http://www.nmt.edu/~borchers/
New Mexico Tech Phone: 505-835-5813
Socorro, NM 87801 FAX: 505-835-5366
Marnix Klooster
borc...@nmt.edu (Brian Borchers) wrote:
> I've looked through the Griess and Schneider materials, and they look
> interesting. However, one thing that seemed to be lacking was discussion
> of how to read and write proofs in conventional mathematical English.
> Given that students will ultimately have to read and write proofs in
> this style, how do you motivate the transition from proofs in this
> very formalized style to proofs written in English?
[Disclaimer: I haven't had a chance to look at the Gries-
Schneider book yet :-( But I do know a bit about other work in
this area.]
First off, you call the calculational format a "very
formalized style". What do you mean by that? Is it _too_
formal, or too low-level? Is it non-intuitive? Are proofs
difficult to follow and/or check? Have you tried to write and/or
find proofs? I'm very curious to know how somebody who is new to
calculational proofs looks at them. (And I'll be glad to help
anyone having problems with such proofs.)
I agree that students will have to be able to read
mostly-text proofs (for want of a better term). And the only way
to do this is, of course, by experience. This might for instance
be done by taking a number of mostly-text proofs as examples, and
show the students what they say, and how the same content can be
packaged in the calculational style.
I don't really know whether it is necessary to teach the
writing of mostly-text proofs. I mean, if calculational proofs
are easier to follow and more precise than mostly-text proofs
--and I think they are, in just about any area of mathematics--
why force students to write hard to follow and less precise
proofs?
I think one of the main points of the calculational proof
style is that there is no real need to translate such proofs to
mostly-text proofs. A calculational proof can be as easily
checked as a mostly-text proof -- I'd argue it's even easier.
The only requirement is that the reader is somewhat familiar with
this proof format, and the basic logic laws. I admit this could
be a hurdle, since some practice is needed. But practice is also
needed to be able to follow mostly-text proofs. Also (IME) its
much easier to get lost in them, since the reader often has to
make an effort to understand the structure of the proof, the
properties used, etc. In the calculational format these are
immediately clear.
I sincerely hope that the calculational proof style will get
a larger `user base' over the years, so that it will become an
accepted way of communicating proofs as it deserves to be. (In
fact, in a number of computer science journals today you will
already find many calculational proofs.) It will probably not
replace the mostly-text style, but it is certainly a very
valuable addition.
As an aside, how much reading and writing of proofs is taught
in universities? In my own case, we had a course about various
basic mathematical subject where we had to do most proofs
ourselves. It taught me how to find proofs, but not really how
to communicate them clearly, and even less how to read existing
proofs. All of that I had to find out on my own.
> Brian Borchers
Marnix Klooster
hru...@b.stat.purdue.edu (Herman Rubin) wrote:
> In article <32da6d4...@news.worldonline.nl>,
> "Equational logic" is not even that well defined, unless it is
> restricted to particular mathematical structures. There is the
> one major rule, which is far more general, and that is the rule
> of equality.
>
> But in the understanding of logic, this rule is but one of many,
> and it is even possible to dispense with it, although I certainly
> would not want to. But the full sentential and predicate calculus
> can be taught in elementary school, as has been done by those who
> understand it. Equality slides in as just another rule.
Aha. We have a misunderstanding due to sloppy terminology on my
side. What Gries calls `equational logic' is just (first-order,
classical) predicate logic, but with much emphasis on equivalence
and equality, instead of on implication. This emphasis makes it
possible to consistently write proofs down in a calculational
format, as I've shown in an example. (It also means that
predicate logic becomes easier to understand and use, in my
experience.)
Just a couple of days ago I learned that the term `equational
logic' has another meaning too. Sorry for the confusion.
> Herman Rubin
Jon T. Jacobsen
Michael A. Stueben wrote:
> Yeah, there is a bunch of joke proof methods listed somewhere:
> 1. Proof by hearsay: "Prof. Rubin told me it was true."
> ---
I've heard it said that if one can get three Geometers to
nod their heads at your proof then it is correct.
Herman Rubin
In article <32dc9156...@news.worldonline.nl>,
One can do almost as well by using what is called natural deduction.
As I stated above, one could dispense with the rule of equality.
Most logic texts, in presenting the first-order predicate logic,
only introduce equality after everything else. It is this approach
which I suggest be started in primary school, and be in full extent
by the end of elementary school.
Brian Borchers
My main problem with the Gries and Schneider format is that by
formalizing everything you end up with extremely long proofs that
can't very easily be read by a human. The formalism ends up obscuring
the ideas behind the proof. I agree that it's easier to check proofs
of this sort, but 99.9 times out of a hundred, the reader of a proof
is trying to understand the mathematical ideas and not trying to
carefully check the proof.
For example, how do you take something like the material in section
4.4 of Cormen, Leiserson. and Rivest (a seven or eight page long proof
of the master theorem for divide and conquer recurrences) and put it
in this format? From what I've seen, the result would be a proof of
fifty pages or more and it simply wouldn't be worth reading. I've
picked this example because it's a proof that students are likely to
encounter in a junior level algorithms course.
I think that almost everyone would agree that students need to be able
to read conventional proofs. Writing proofs in English is also
important, if for no other reason than that CS students will have to
do it when they take required courses in mathematics at the
junior/senior level.
I'm somewhat interested in the possibility of proposing the Gries and
Schneider text for our new 100 level discrete math course. However,
I'm very concerned about this issue of how to transition the students
to conventional proofs. I'd like to hear from people who've taught a
discrete math course using the Gries and Schneider materials- how do
you (or do you at all) help the students make the transition to
reading and writing conventional proofs in English?
Herman Rubin
In article <5bmu4q$e...@newshost.nmt.edu>,
Brian Borchers <borc...@nmt.edu> wrote:
>My main problem with the Gries and Schneider format is that by
>formalizing everything you end up with extremely long proofs that
>can't very easily be read by a human. The formalism ends up obscuring
>the ideas behind the proof. I agree that it's easier to check proofs
>of this sort, but 99.9 times out of a hundred, the reader of a proof
>is trying to understand the mathematical ideas and not trying to
>carefully check the proof.
Have you read any of the books using what is called natural deduction?
There are many versions of this. But the proofs are not that long, and
it is possible to add derived rules, quote theorems, and a computer
proof checker could even in many cases be instructed to combine steps.
If the proof checker can follow the instructions, the combination of
steps is valid. If not, there will have to be a refinement for the
checker to carry out the steps.
>For example, how do you take something like the material in section
>4.4 of Cormen, Leiserson. and Rivest (a seven or eight page long proof
>of the master theorem for divide and conquer recurrences) and put it
>in this format? From what I've seen, the result would be a proof of
>fifty pages or more and it simply wouldn't be worth reading. I've
>picked this example because it's a proof that students are likely to
>encounter in a junior level algorithms course.
I would not like to spend the time to expand a proof of this length,
but I doubt that it would come to more than 20 pages, even in the
fully expanced version. The point is that what is being done, while
formal, is "natural". At an early stage, it might be advisable to
use a more detailed explanation, but clarity and similarity to
"English" proofs is still there.
>I think that almost everyone would agree that students need to be able
>to read conventional proofs. Writing proofs in English is also
>important, if for no other reason than that CS students will have to
>do it when they take required courses in mathematics at the
>junior/senior level.
The transition will not be that hard. And natural deduction has been
taught in 5th grade, with what I believe is an unnecessary weakening.
It is less difficult than the old-fashioned high school Euclidean
geometry course.