A math book on introducing proofs(?)

[Physicist7]

Hey guys… and girls! I was just wondering if anyone knew of any good books that introduce the concepts and reasoning behind mathematical proofs, starting from the beginners level. (In high school my teachers did not emphasize proofs.) I would like this specifically to help me for first year linear algebra, and Calculus. Thanks a lot everyone, take care.

 

[robert Ihnot]

A book that many have recommended that is intended for the individual student that was written by a world-class expert is, What is Mathematics? by Courant. It is an old book and can be had second hand.

 

[matt grime]

Polya's How to Prove It.

 

[robert Ihnot]

matt grime: Polya's How to Prove it.

Excellent suggestion, and a relatively easy book to read.

 

[matt grime]

And the best way to learn how to prove something is to read proofs and mimic them, work out the reasons involved in the deductions. There is a book with the same name as Polya's that appears to think explaining what truth tables are is the best way to teach people how to prove things, which is just utter nonsense.

 

[mathwonk]

you might be right. i wonder though whether polyas book dates from a time when it was assumed that many people knew how to understand and read a sentence, formulate a negation, a contrapositive, and a converse.

now when euclidean geometry is no longer taught as it was, it may be that many students need to learn even what it means for a statement to be true or false. this is what truth tables are used for now, not to make a proof but simply to understand one.

i believe polya assumed that his reader understood that to prove that not every number solved a given equation, it sufficed to find one that did not.

but maybe we worry to much about such things, and should go back to the substance of proofs, which is simplifying the problem, finding analogies, then trying to use one good idea in a new problem, etc...

i once gave copies of polya as a present to my graduates of a calculus class for teachers. I wonder if i could get away with using it as a text?

I know of the book you are talking about of the same name. I was about to adopt it sight unseen, from highly favorable student reviews, when I found from a review that it taught "two column" proofs, and instantly jettisoned it from my list of candidates.

according to some reviews however the book does encourage the student to reformulate equivalent versions of a problem and look at them for possible inspiration.

teaching proofs is really hard, even trivial matters such as induction.

there is a thread on here somewhere in which an endless and depressing discussion is going on and on, over the difference between assuming P and assuming that P implies Q.


Students are so puzzled by such things that it gets totally in the way of using induction to prove things.

I was never able to teach my proofs class to understand the logical structure of induction.

there are also some subtleties that puzzle even some professors, such as the relation with well ordering.

e.g. it is often claimed that well ordering is equivalent to induction, but it is false for example that a subset of a well ordered set equals the whole set if it contains the least element and the successor of every element it contains.

e.g. think of the integers re - well ordered so that the even integers are greater than all the odd ones. then an "inductive subset" contains only the odd integers.

notice that "proofs" of the equivalence assume the special property of the positive integers that there is also a "predecessor" of every element, which is not true in arbitrary well ordered sets.

 

[matt grime]

I think my issue with these attempts to teach proofs by truth tables are that the students get good at showing some logical rules but don't know that in order to prove "not every..." it suffices ot find one counter example, so the whole first 4 weeks of their course are completely wasted. They can prove that if A implies B and B implies C then A implies C but can't then use it to actually prove anything, and no amount of explaining "A if and only if B" seems to get through despite the fact they know the truth table of it is different from A implies B. It might be alright to try and teach a course like this but I think that there needs to be far more examples in it, of a far more complicated nature. But then we're into chicken and egg territory.

 

[The Rev]

Polya's How to Prove It.

I went looking for this book, but all I found was "How to SOLVE it" as a title. Is "How to Prove It" out of print, or are these two, in fact, one in the same?



The Rev

 

[CrankFan]

I went looking for this book, but all I found was "How to SOLVE it" as a title. Is "How to Prove It" out of print, or are these two, in fact, one in the same?



The Rev

Polya's book is . It's a well known classic.

How To Prove it is probably the book that Matt was referring to when he warned about a book with a similar sounding title that taught how to do proofs with truth tables. That book appears to be an ordinary logic book and not the same category of book as those that introduce students to basic concepts of mathematics.

There is another book which is said to have been written (by the author himself in the introduction!) in the same spirit as Polya's book, and that book is

I'm not sure how this one is, I've only flipped through it at a local bookstore, but thought it was worth mentioning.

 

[mathwonk]

in the reviews on amazon, some people liked it, and some think it is pretty simple minded.

i am worried that "what is mathematics" may be going out of print, as it is available on sale at $15 from amazon or barnes noble, but is out of stock at the publishers.

 

[matt grime]

My mistake, How to Solve it is. The important thing is it's Polya's book.

 

[mathwonk]

One of the more popular books today on proofs, costing over 100 dollars, is by Bond and Keane, so I picked it up again yesterday to see if I might be willing to impose it on my students.

The first thing i saw was this: in the chapter on real numbers, they defined "upper bounds" and "lower bounds". Then they gave without comment, as an example of a subset of the reals which is unbounded above, the natural numbers. The said this as if it were obvious.

THEN they defined a "least upper bound", gave examples, and introduced the least upper bound axiom for reals. Then they proved the important "Archimedean property" for reals using the lub axiom.

At no time did they ever observe that the property that the natural numbers are unbounded above, is actually equivalent to the Archimedean property. I.e. that the "example" they had given earlier needed the least upper bound property for its verification, and if it were known, then the Archimedean property needed no additional proof!

This kind of stupidity sends me up the wall. It suggests to me the possibility the authors do not even understand what they are writing about, and I refuse to use such a book, especially when it is priced at 8 times the price of courant and robbins, and roughly the same factor of polya.

How do we expect students to think intelligently about the material when the authors themselves write in a repetitive, mindless way, merely aping the other standard books on the topic?

the point of the course is not to memorize the definition of least upper bounds, it is to learn to think logically. the book itself should offer an example of this.

 

[bifodus]

"How to Prove It: A Structured Approach" by Daniel J. Velleman is brilliant. It starts off with sentential and quantificational logic, which are absolutely necessary in really understanding how to write a proof, and then it gets into building blocks of analysis with relations, and functions. Then it concludes with an in-depth look at mathematical induction and infinite sets. You may think that these topics sound extraneous, but in addition to really understanding the logic behind proofs, you'll get a foot-in on the first topics that you'll find yourself really actually proving while an undergrad. I nearly shed a tear as I recommend this book.

Polya's book, on the other hand, is really not recommended for what you're looking for, and I believe you'll find it disappointing. It's definitely mandatory reading, but much more from a heuristic point of view than a proof-writing point of view.

 

[matt grime]

Hmm, Vellemna? No it's not good. I didn't wish to name names, but Velleman's book is absolutely completely and utterly ******* ****, insert your own preferred terms. It is perhaps the worst book I have ever read, and certainly the worst book about mathematics that has ever been written, that it has been my unfortunate experience to see.

Velleman's book is only required in the sense of " read a book that is totally pointless..." but then I've got a degree in maths so, plus many more qualifications, so what would I know?

 

[mathwonk]

I also find it frustrating that many students seem to like Velleman (from the amazon website reviews), whereas I agree with Matt that it apparently gives the opposite impression of proof writing from the one I want to teach. "2 column" proofs do not make the point I want to make. Proving is not that mechanical, unless the result is tautological.

On the other hand maybe we underestimate the total lack of familiarity students today have with these tautological mechanics??

Here is an example of the kind of thing my students find difficult, or nearly impossible:

Challenge: complete the following definition:

"A real valued function f defined on the interval I, is said to be 'bounded'
if and only if..."

Less than 10% of my students could complete the previous sentence correctly.

Many of them simply parroted (incorrectly) a theorem which guarantees that a function is bounded.

So many of my students do not know the difference between a definition and a theorem, and many could not make a correct statement of a simple concept that we had studied at nearly ridiculous length. (It is not an exaggeration to say that 40 years ago it was considered more than adequate to give this trivial definition once, in a few lines, and expect it to be understood and remembered accurately after that.)

Perhaps, it is for such students that books like Velleman are intended. But I fear these books still fail to provide the grasp of creative logical reasoning we actually want students to acquire.

Polya's book is directed at developing a way of thinking that enables the reader to discover proofs. Velleman's is apparently devoted to teaching to the reader what to expect when I say "If I see another such worthless book, I shall scream", and the reader then presents me with a copy of Velleman, or Solow, or Wolf, or Bond and Keane. (And these are among the best of their ilk!)

 

[bifodus]

I would possibly agree that Velleman takes a very pragmatic, and seemingly mechanical approach. But it just gives you a way to think about getting started, and how to understand the form of proofs. But seriously..."How to Solve it"? As I recall, that book has nearly nothing relating to the form of proofs. The biggest hurdle isn't in understanding what makes something true or in seeing why something might be true, it's in actually putting it on paper in a way that's rigorous, precise, and clean. People that have already gone passed any hurdle always tend to look back and dismiss the elementary and maybe even slightly dumbed down approaches that got them over that hurdle in the first place. Velleman's book isn't a book one would want to reread many times, as Polya's "might" be, but it's beyond a good book for the original poster who is just looking for a way to get started.

On a related note..."How to Prove it" using truth tables to prove theorems? That, it does not. I'm wondering if we're referring to different books or if you, matt grime, perhaps only glanced at it? The book begins with sentential logic, and truth tables are for the purposes of understanding logical connectors, not a way to think about proofs. It never once mentions using truth tables as devices in actually writing real proofs.

Perhaps I misunderstood, but didn't you, mathwonk, say that you read that the book teaches "two column" proofs and that you instantly "jettisoned" it? Does this imply that you haven't read it? If you haven't, I just want to point out that he uses this "two column" proof method as a way to reformulate equivalent versions of a problem, which in your next paragraph you stated was a good thing.

Let me give a little description of what this "two column" thing is all about. First of all, it's nothing more than a way to organize thoughts, and the only times it's mechanical are when things are trivial. On the left side you put your assumptions, and on the right side you put what you want to prove. Under these you update your givens and your goals using tautologies and/or whatever insights you may have. You do this until you can see how your assumptions lead to your goal. This is something we all do in our heads, and this just gives us a way to keep track of what we're doing. This isn't something he insists that we use forever, it's just an excellent way to visualize progress in your proof, since the average mind can't comprehend a complex proof at one time. You can put your updates into english once you are finished and what you end up with is often a nice proof.

 

[mathwonk]

yes i have not read it as i cannot get hold of a copy. i have tried unsuccessfully, but have been forced to go by descriptions on websites.

The searchable aprt of it on the amazon website only included a few pages and not even a table of contents as i recall. it looked pretty good to me until someone mentioned the dreaded "2 column proof" phrase.

This has been used by so many people who do not know anything about math that it has a bad connotation for me. thank you for giving me a little more to go on.


teachers today are forced to pick books often without seeing them since some publishers do not want to send out freebies anymore unless you indicate a preference for their book, and have a large class, etc etc.

also deadlines make trouble as i have only 4 weeks and some publishers want 6 weeks to send out a book.

I also went to our science library but they did not have a copy of velleman. I am not willing to spend $35 for a book i will never have any interest in myself.

OK I just revisited the amazon website and tried to search the book.

This is a little scary: if mathematical induction is on page 245, what in heaven's name is in the previous 244 pages? Last time I taught this course I started the first day with mathematical induction, and the discovery and proof of formulas for the sum of the nth powers of the first k natural numbers.

 

[bifodus]

You're welcome. I can see where you're coming from. I think why a lot of students might be seeing the technique as the holy grail of proof-writing (which obviously leads people of higher stature to scoff at the book) is because it makes all the logic they've learned (which often comes far before real proof-writing) into something they can immediately use to prove theorems. Suddenly the students feel enlightened and elementary proofs go from extremely difficult to something that they actually have a feel for. This causes them to have unfounded confidence in this technique when it's in fact nothing more than a way to organize some thoughts.

Edit: To answer your last question, a lot of the stuff that comes before mathematical induction is perhaps a little unnecessary for the aim of the book. Every section from relations and after (up until mathematical induction) are mostly exercises in proof-writing mixed with a very basic introduction to some topics that undergrads will soon encounter.

 

[Kamataat]

"A real valued function f defined on the interval I, is said to be 'bounded'
if and only if..."

Sorry, if it's off topic, but what do you mean by this challenge? Are you saying that you don't want your students to say that "a real valued function $f(x), x \in X$ is bounded on $X_1 \subset X$ if for every $x \in X_1$ there exist $m$ and $M$ such that $m \leq f(x) \leq M$"? I think this theorem(?) doesn't holds only for monotone functions. So how can we define boundedness for all functions?

Would a better way to say this be that "A real valued function $f$, defined on the interval $I$, is said to bounded if and only if there exist $m$ and $M$ such that for every $x \in I_1 \subset I$ we have $m \leq x \leq M$"? EDIT: or maybe not, this sounds a bit circular (and wrong) to me...or is it okay to say that $f$ is bounded iff $I$ is bounded?

Or maybe the easier way would be to say that $f$ is bounded on $I$ iff there exist $f(m)$ and $f(M)$ ($m,M \in I$) such that $f$ is defined only for $x \in [m,M]$? This sounds messy too, but what I mean to say, is that $f$ is bounded on an interval if it is defined in that interval and not defined outside of it.

Don't really know... This may all be wrong, since I'm making this up in my head.

- Kamataat

 

[matt grime]

For Bifodus. I didn't say Velleman uses truth tables to prove anything (other than results in predicate logic). Perhaps you only glanced at my post? I said it pointlessly starts with truth tables (and things that any student of mathematics at university ought to already know). What it intends the students to understand and what the students actually understand from it are not necessarily related, or are you accusing me of lying about the work my students hand in based upon reading this book?


It is a complete waste of money, and is the recommended text for a course I teach, so yes, I have looked at it in order to see what my students are beign told to buy. And what I saw wasn't good mathematics. The best way to learn to write proofs is to read a lot of them and write a lot of them and there is no need to have a special book in order to do that.

 

[mathwonk]

kamataat:

all of your statements are incorrect. did you mean for any of them to be correct? or are yopu just giving sample incorrect answers?

the correct answer is the following:

a real valued function f on a domain D is bounded if there exist numbers m,M such that for every x in D, m ≤ f(x) ≤ M.

this is different from your statement because your quantifiers are placed incorrectly.

a common mistake made by my students is indeed to confuse boundedness of the domain with the (correct) boundedness of the set of values taken over that domain, as some of your later statements do.

 

[quantumdude]

I was never able to teach my proofs class to understand the logical structure of induction.

I had some success in this regard with a course called "Mathematical Structures". It is a terminal course in mathematics for liberal arts students, and it covers induction. Needless to say, I could have strangled my Department Chair for assigning me to it.

Anyway, I explained it by analogy, and the students were able to understand what they were doing, even if they didn't always do it correctly. Here goes.

You have an infinite line of dominoes. You have to prove that they'll all be knocked down after the first one is knocked down.

First, you have to establish that the first one is knocked down. This of course is the analog of proving P(1).

Then, you have to prove that if a domino at some arbitrary point along the line is knocked down, then it will knock down it's neighbor. This of course is the analog of proving P(k)-->P(k+1).

So when all is said and done, you've proven that all the dominoes go down in just two steps. When the first falls, it knocks down the second. When the second falls, it knocks down the third...

You get the idea.

 

[mathwonk]

well that is certainly one of the many analogies i tried using. There is not a great deal of difficulty conveying the general idea, such as "to be able to climb a ladder, first you must get on the bottom rung of the ladder, and then you must be able to climb from any rung to the next rung." and so on.
the problem i had was getting the students to actually be able to write up an induction proof logically correctly.

e.g. here is a statement of the principle of induction:

Principle of (ordinary) induction:
Let P1, P2,...,Pn,... be an infinite sequence of statements, one for each
natural number n.
If we can prove:
1) P1 is true, and
2) for each k>=1, whenever the statement Pk is true, then also Pk+1 is true;

then all the statements P1, P2,...,Pn,... are true for every n.

My class would restate this for instance by saying in step 2, that one begins by assuming Pk for all k.

of course then it is moot to bother proving P(k+1), since it has already been assumed. i.e. they would start by assuming all the dominoes had been knocked down.

this kind of confusion over the precise use of induction. essentially never went away. the contrast between assuming P, and assuming the statement "P implies Q" is very subtle.

 

[mathwonk]

well my research reveals the fact that my view of a book differs from my students' view as follows:

Comparing the book of Bond and Keane say, with that of Robert S. Wolf, I greatly prefer Wolf, but my students may prefer Bond and Keane.

I.e. Wolf writes intelligently, and authoritatively, as if he actually understands the material, whereas Bond and Keane make substantive oversights, and present canned proofs apparently copied without reflection from other sources.

But, although the actual material presented by Wolf is superior, the WAY it is presented is more difficult for stduents to access. E.g. Bond and Keane present a definition, and then immediately follow if by several simple examples, (not always correctly justified, but so what, the student does not know that).

Wolf on the other hand, prattles on verbosely like a college professor with tenure.

Hence I have to choose whether I want my students to have higher level material that they find ahrder to read, or inferior material that is laid out more simply.

Unfortunately the intelligent and knowledgeable author finds it hard to identify with a reader who does not read well. And I admot that even though i think I know how to read, I also have trouble organizing mathematics presented in a discursive style, rather than in simple outline form.

For instance my own graduate algebra book, carefully written though I may think it is, has no index. Hence students find it hardert to use and trefer to quickly, because it is writtten for someone who plans to sit down with it and go through it.

Now writing an index requires no mathematical knowledge at all, but someone willing to make one adds value to his book.

 

[Kamataat]

kamataat:

all of your statements are incorrect. did you mean for any of them to be correct? or are yopu just giving sample incorrect answers?

the correct answer is the following:

a real valued function f on a domain D is bounded if there exist numbers m,M such that for every x in D, m ≤ f(x) ≤ M.

this is different from your statement because your quantifiers are placed incorrectly.

a common mistake made by my students is indeed to confuse boundedness of the domain with the (correct) boundedness of the set of values taken over that domain, as some of your later statements do.

You shouldn't really take note of all those statements... I didn't know what I was doing...

So in my first statement it's wrong to say that "for every $x \in X_1$ there exist $m$ and $M$". Thank you for pointing that out to me.

But what does one do in the case when one has $y=\sin x, X_1 = [\pi; 3\pi]$? The function is bounded on $X_1$, but $m=M=0$. Obviously it's not bounded according to your definition, but nevertheless $y$ is bounded from two sides, in the sense that the function ceases to have any values beyond two points on either end of the line. Is this then not a bounded function, although it looks like that on a picture? Should I stop taking pictures/graphs to literally and concentrate more on the words and symbols presented to me?

- Kamataat

 

[Muzza]

What makes you think m = M = 0? Because those are the values that sin(x) takes at x = pi and x = 3pi? A function defined on a closed and bounded interval doesn't need to assume its maximum or minumum values at the endpoints of the interval. You seem to be confused on what boundedness refers to. It doesn't refer to the domain of the function, it refers to its range (i.e. the image of its domain).

To get back to your example, try m = -1, M = 1. Then, given some x in [pi, 3pi], is m <= sin(x)? Yes. Is sin(x) <= M ? Yes. Hence the function is bounded (using mathwonk's definition).

(Of course, lower/upper bounds are not unique, and there is no need to restrict ourselves to [pi, 3pi] in the case of the sine function).

 

[Kamataat]

What makes you think m = M = 0? Because those are the values that sin(x) takes at x = pi and x = 3pi? A function defined on a closed and bounded interval doesn't need to assume its maximum or minumum values at the endpoints of the interval. You seem to be confused on what boundedness refers to. It doesn't refer to the domain of the function, it refers to its range (i.e. the image of its domain).

To get back to your example, try m = -1, M = 1. Then, given some x in [pi, 3pi], is m <= sin(x)? Yes. Is sin(x) <= M ? Yes. Hence the function is bounded (using mathwonk's definition).

(Of course, lower/upper bounds are not unique, and there is no need to restrict ourselves to [pi, 3pi] in the case of the sine function).

Thank you. I realize I was wrong. I should really learn to read mathematics carefully. For example I wasn't careful enough to notice that the "less than or equal" sign is used and instead I assumed that it's equal only and thus f(x) must equal m and M when all it has to do is to be between m and M.

- Kamataat

 

[bifodus]

Sorry matt, I must be having trouble parsing the sentences "I think my issue with these attempts to teach proofs by truth tables are that the students get good at showing some logical rules but..." and "There is a book with the same name as Polya's that appears to think explaining what truth tables are is the best way to teach people how to prove things, which is just utter nonsense." And I'm not accusing you of lying about something you haven't said.

If it's true from your experience that this book causes people to misunderstand mathematics, then I'll give you the authority on this topic. You undoubtedly have more experience than I have, matt, for I am just an upper division math major. But I am an upper division math major who, while doing elementary calculus in the early years, studied proof-writing with this book in preparation for more rigorous mathematics. These upper division classes have been significantly easier for me than for the rest of the class. Whether or not I can chalk this up to having read this book and having worked out all the problems I don't know. What I do know is that the book doesn't include anything that one should find controversial, and I have found it unique in that it actually includes commentary in the many many proofs it contains.

 

[mathwonk]

well it is entirely possible that Matt does not see anything in the book that he thinks should be useful, and that his students have not performed well after using it, and yet it can still be true that it was useful for you. everyone has their own epiphany experience, where they "get" something for some reason, at a certain time.

that is why it is hard for one person to select a book that will help another. What some of us older heads do try to do, is recommend a book, which may be hard to read, but which, if eventually mastered, will at least promise to contain the insights we think important.

It may still be the case that a student will require some other source to get ready for these books.

you notice a lot of people keep recommending polya, and courant and robbins. there is a reason for this.

 

[matt grime]

Velleman does attempt to get people to start proving things with truth tables. Namely results about truth tables, or simple connective logic. Ie they learn how to prove logical rules, tautologies, whatever, but the way they do this is useless for proving anything else. Ie anything in almost all of mathematics.

I will only recommend books that I think a student will be reading in three years time whether it be for work or pleasure, and Velleman does not fit that criterion. Poya does. It is more important to figure out what the argument is to prove it first, rather than know how to negate a string of quantifiers.

Writing out the proof is then simply writing down the solution to the problem.

I don't find the idea of spending a huge amount of time learning these "methods" in artificial ways helpful for any student. Certainly, I may be thinking that the fact that in order to show an assertion is false for all x, it is sufficient to find an x for which it fails, is obvious, and that is a fault in my view of what students should know: common sense is unique amongst virtues in that everyone possesses it.

Perhaps some students (most?) need to have simple logical rules explained, however it took me three years of students to find a satisfactory way of explaining why the slogan "false implies false" is true that everyone grasps. And afterwards, they come to write "show the sequence 2 - 1/n^2" tends to 2 and they can't because their problem solving skills (Ie ways of finding a proof) are lacking.

I'd rather have students who've never seen connectives and quantifiers but understand that if x has property, and having property P implies having property Q, and having property Q implies having property R, then x has property R, than someone who can write out the truth table of (P=>Q)/\(Q=R) => (P=>Q)

So perhaps it would behove me to differentiate between the skills of solving a problem, and the skill of writing it on paper. I tihnk the former is far more important than the latter, since the latter is a mechanical process, like doing things with truth tables.

I would also point out that students in learning, artificially, the methods of proof then struggle to figure out which one to apply in any given situation. ie for a question that doesn't say "use induction to solve".