Teaching undergraduate students to write proofs

In my experience, there are roughly two approaches to teaching (North American) undergraduates to write proofs:

1. Students see proofs in lecture and in the textbooks, and proofs are explained when necessary, for example, the first time the instructor shows a proof by induction to a group of freshman, some additional explanation of this proof method might be given. Also, students are given regular problem sets consisting of genuine mathematical questions - of course not research-level questions, but good honest questions nonetheless - and they get feedback on their proofs. This starts from day one. The general theme here is that all the math these students do is proof-based, and all the proofs they do are for the sake of math, in contrast to:

2. Students spend the majority of their first two years doing computations. Towards the end of this period they take a course whose primary goal is to teach proofs, and so they study proofs for the sake of learning how to do proofs, understanding the math that the proofs are about is a secondary goal. They are taught truth tables, logical connectives, quantifiers, basic set theory (as in unions and complements), proofs by contraposition, contradiction, induction. The remaining two years consist of real math, as in approach 1.

I won't hide the fact that I'm biased to approach 1. For instance, I believe that rather than specifically teaching students about complements and unions, and giving them quizzes on this stuff, it's more effective to expose it to them early and often, and either expect them to pick it up on their own or at least expect them to seek explanation from peers or teachers without anyone telling them it's time to learn about unions and complements. That said, I am genuinely open to hearing techniques along the lines of approach 2 that are effective. So my question is:

What techniques aimed specifically at teaching proof writing have you found in your experience to be effective?

EDIT: In addition to describing a particular technique, please explain in what sense you believe it to be effective, and what experiences of yours actually demonstrate this effectiveness.

Thierry Zell makes a great point, that approach 1 tends to happen when your curriculum separates math students from non-math students, and approach 2 tends to happen math, engineering, and science students are mixed together for the first two years to learn basic computational math. This brings up a strongly related question to my original question:

Can it be effective to have math majors spend some amount of time taking computational, proof-free math courses along with non-math majors? If so, in what sense can it be effective and what experiences of yours demonstrate this effectiveness?

(Question originally asked by Amit Kumar Gupta)

-
Community wiki? – Qiaochu Yuan Jan 13 '11 at 1:41
I believe it is helpful to provide some explicit instruction on how to do deductive logic and, equivalently, use set theory. But I also believe this is best done within the context of a real math subject such as discrete math or elementary abstract algebra or elementary analysis. The last one is where it is usually introduced, but I think this might be a particularly difficult setting, given the heavy use of double quantifiers ("For every epsilon greater than zero, there exists a delta greater than zero such that..."). – Deane Yang Jan 13 '11 at 1:58
+1 Amit for remembering to localize your question to North America. Soft Questions on MO are an endless source of frustration when posters forget to specify where they live, since there are such tremendous regional variations in most such questions. – Thierry Zell Jan 13 '11 at 3:55
The American high school geometry course was supposed to introduce proofs. That was the point of the course, not the vestigial collection of basic plane geometry facts which have remained after people took out the logic which was challenging and hard to test. If we want the general population and prospective mathematics majors to understand logic better, we should fix the high school geometry course, not just the college courses for mathematics majors. – Douglas Zare Jan 13 '11 at 16:37
@Andrea, I don't think your question was naive at all, proofless math courses are common in the US but possibly unique to the US as well, there's no reason why someone outside the US would think they exist. – Amit Kumar Gupta Jan 14 '11 at 13:33

This is a great question. In fact, I hope people won't think it over-dramatic if I call it one of the great math education questions of our time.

At the University of Georgia, we have decided as a department to follow the second approach: we offer a course Math 3200: Introduction to Advanced Mathematics. This is one of our three "transitions" courses, the others being (Math 3000) linear algebra and (Math 3100) sequences and series. But this is not to say that the faculty here are unanimously enthusiastic about approach two: in fact I have heard more dissent than agreement among the (mostly young, as it happens) faculty with whom I have discussed the matter.

I myself taught this Math 3200 course twice in recent years: here is my course webpage (don't get too excited: it only gives a very limited picture of what the course was about). I was somewhat bemused when I taught this course for the first time, since this is not a course I have ever taken. For instance, we spend about three weeks of the course on mathematical induction, a topic which I learned in high school. (More precisely, I learned about it during a self-paced summer Algebra II course I took through the CTY program after my freshman year of high school. It wasn't until years after that I began to understand that -- in that I actually read, did problems on and was tested on the entire Algebra II book -- I actually learned rather more than what takes place in an actual Algebra II course even at my (very good) high school.)

And yes, the course began with a chapter on logic: truth tables, contrapositives, negating statements, and so forth. I was surprised to discover that many of my colleagues found this material to be dry, pointless and difficult to teach. (Some of them even affected not to be able to easily solve some of the logic problems that appeared on later exams. I do think this was an affectation, and a curious one.) But for my part I very much enjoyed teaching the course and most certainly did not find it a waste of time: spending say, two weeks setting up logic is a small price to pay for being able to expect that students will not confuse the converse with the contrapositive for the rest of their careers. And I confess that I did not in fact find it boring: I remember deciding at one point to draw one big table with all $2^{2^2}$ different binary connectives and ask the students to give the simplest description they could for each one. This took most of a class period, but compared to, say, finding the rate of change of the length of some guy's shadow at the instant he is 10 meters away from a lamp post, it was great fun.

I believe this course was very useful for the students: it is nice to have one course where one can spend as much time as one needs concentrating on the processes and methods of proofs themselves, rather than on proving particular theorems. (Which is not to say that we didn't prove anything at all: there was a unit on divisibility and another on modular arithmetic, for instance. When I have taught undergrad number theory, I assume that students have seen this material twice over: in this course, and then again in the required semester of abstract algebra, and I really don't cover it again.) Moreover there was time to concentrate on the students' writing in particular, and may Gauss strike me down if the writing didn't improve from horrible to halfway decent throughout the course of the semester.

This course is certainly not appropriate or helpful for all undergraduate math majors. For instance, we offer one section of Honors Calculus a la Spivak per year (I have the good fortune to be teaching this course next year: a year free of lamp posts!) and I think that students who do well in this course learn everything that we would like them to learn in the Math 3200 transitions course and more. But for a certain level of student -- a level that can be trained to do well as an undergraduate math major -- this course works very well.

Added: after rereading the question, I want to make clear that the above long answer is not an argument for option 2. versus option 1. Option 1. -- i.e., include proofs in all university level math classes, presumably in an increasingly sophisticated way as the classes progress -- which in my understanding is standard in most European university curricula, is not even an option on the table at my (and, I think most) American universities. (I was an undergraduate at the University of Chicago, and that was definitely an exception to the rule. Not only did I have classes which concentrated somewhere between primarily and exclusively on proofs from the very beginning, but in fact all calculus classes there insist on treating some theoretical aspects, including about a month of class time on epsilon-delta proofs.) So my answer takes as a given that there is a transition being made from almost exclusively computational courses to somewhat theoretical courses. Given this, the question is whether this transition should be done in exclusively in the context of content-based courses (e.g. linear algebra with careful definitions and proofs), in the context of an "introduction to proofs" course, or both. At UGA, our answer is "both". What I am saying that in my opinion the "introduction to proofs" course is not a waste of the students' time. Some others feel differently.

-
This is a very nice, long description. However, as someone based in the UK, two facts I'd love to know (and this applies to other answers as well) are: What is the class SIZE? And how much contact TIME did you have? (For comparison, I teach a similar course, with size=150 and time=3 hours a week over 9 weeks). – Matthew Daws Jan 13 '11 at 8:27
“spending say, two weeks setting up logic is a small price to pay for being able to expect that students will not confuse the converse with the contrapositive for the rest of their careers.” I agree whole-heartedly with this, but is it what actually happens? In my experience, unless the audience is quite sophisticated, what actually happens in many cases is that they can fill in truth tables, but attach no meaning to them and so go right back to making the confusion it is intended to avoid. – L Spice Jan 13 '11 at 20:57
I don't claim to have any useful teaching experience related to this, but anyway: I think spending two weeks on truth tables is a really terrible idea. If students don't already intuitively understand basic logic, then they need lots of practice in simple "naive logic" exercises; formal manipulation of (to them) meaningless symbols is not the way to go (surely only logicians and computer scientists actually use that stuff?) (I also think that students who are not intuitively logical are probably hopeless cases, as far as proper mathematics is concerned; but we'd better not go there!) – Zen Harper Jan 14 '11 at 9:22
...to illustrate what I'm talking about: why is it that students have such difficulties solving easy things like, say, $|x+1| + |2x-3| < 4 + |x-2|$ ?? Because they cannot think logically. Almost none of them split it up into different cases for $x$; they try to do horrible stuff with squaring and $|y|^2 = y^2$ and, of course, eventually give up. They're not thinking about what they're doing; they think Mathematics is about meaningless algebraic manipulation. And truth tables and formal logic will only reinforce this, I think. – Zen Harper Jan 14 '11 at 9:45
@Zen: there is more to the chapter on logic than just truth tables. But this is part of what is done, and it is (I have found) a useful part. For instance, we want students to understand the notion of vacuously true implication. Part of this is to show them the definition of $A \implies B$: in particular, that it is true except when $A$ is true and $B$ is false. Certainly most of the exercises in the chapter on logic do not involve "meaningless algebraic manipulation". – Pete L. Clark Jan 14 '11 at 10:39

I have tried teaching proofs for years, and I have had a lot of trouble, both in "proof" courses, and in ordinary courses. The hard part for me was getting the student to think about what the statements meant, and why the statements implied each other, rather than just memorizing a sequence of steps. Often we mathematicians do not notice that we are leaving out remarks that are logically essential, because we know how to fill them in.

Students "learn" much more easily to repeat even lengthy proofs that do not reveal any reasoning, than to give even short arguments that require it. E.g. most students can easily learn the sequence of steps that claim to prove the product rule in calculus. But a quick examination of even many of the best books will show that the logic of the proof is not made clear even by the author.

E.g. the proof usually starts out with the difference quotient of the product, and the word "limit" in front of it, and then manipulates the difference quotient until it becomes separated into the appropriate two separate limits. No mention is made of the fact that the limit which is being taken for granted in the first part of the discussion is not known to exist until the end. Hence the proof should correctly be done only with the difference quotient and not the limit of it, or else it should be stated that the word "limit" is not justified until the end of the argument, by reading backwards. This logical gap occurs even in the magnificent book of Spivak, (but not in that of Apostol).

I.e. the students can learn to derive the formula, but do not appreciate even the need to show the derivative of the product actually exists.

Similarly algebra students "learn" to give the proof of the rational roots theorem, by simply multiplying out the denominators, but at the least step, where some words need to be used to justify a divisibility statement, (powers of relatively prime numbers are still relatively prime), they slough over it. They have much more trouble with irrationality of a square root, because more justification is needed. I have had students in number theory learn the elementary proof that sqrt(2) is irrational, by showing first an integer is even if its square is, and yet not be able to extend it to sqrt(3).

Once I noticed that since polynomials are "symmetric" in a sense, the reverse of the proof of Eisenstein's criterion would yield a proof of the reverse criterion, where p^2 does not divide the lead coefficient instead of the constant term. Only one in a class of over 30 abstract algebra students was willing to attempt this challenge problem, and that one never got it, even with several days of email hints. If a student cannot give this reverse but otherwise identical proof, how much does he understand of the original proof?

This suggests to me that proofs involving words are crucial to learning reasoning, and one should take great care not to assume that a sequence of correct symbols implies understanding of the logic. I would enjoy being able to sit in Pete's course and observe how he handles it.

I am not too impressed with most books teaching proofs. Often it seems the author is going through the motions and not thinking about the consequences of his statements. In one I received, they discussed bounds and least upper bounds and claimed it was obvious the natural numbers are an unbounded set of reals without relating the two concepts. Then later they made a big deal out of proving the archimedean property for the reals, but without linking it to the earlier equivalent but unjustified statement about the natural numbers. This undermines a good student's faith in the importance of the topic.

I got my own initiation first in high school, from a brief course in propositional calculus, and then from a Spivak type course at Harvard from Tate where the homework was all proofs. Then came Birkhoff and Maclane, and finally Loomis and Gluck reinforced it by a very clear use of quantifiers in lectures on real analysis and differential equations. There were no "proof" courses at Harvard in 1960.

I agree 100% with the questioner who asked how the students could be expected to have understood the first two years of math without seeing the logic until junior year. I would love to have that course moved much earlier. Having it in high school was great for me. And I also lived before proof was removed from high school geometry.

-
+1 just for the observation about the failure to generalise from sqrt(2) to sqrt(3) !!! I've seen that so many times. On a recent 2nd linear algebra course, the most dispiriting comments I got were complaints about how I "wrote too many words in proofs" (or similar). I was doing this, exactly as Roy says, to fill in the logical gaps that I felt existed in (some of) my sources. That the students didn't see this, and even complained about it, was pretty depressing. – Matthew Daws Jan 13 '11 at 20:11
I have also had the complaint that I teach "with words" in calculus. I wondered what else to substitute for them. – roy smith Jan 13 '11 at 20:15
None of them were able to articulate their difficulties, so I asked them to tell me what the problem was asking them. One student said, "$y = Ce^{kx}$," so I asked, "that's it?" Blank stares. So I repeated, "what is the problem asking you?" and added, "it's as easy as reading the question from the textbook out loud to me." So another student put up their hand and added, "$y' = ky$." It's as though it didn't occur to them that the words around the equations were relevant. – Amit Kumar Gupta Jan 13 '11 at 23:38
Indeed when faced with students for whom even remembering the formula is a challenge, we often give up the subtleties as pointless. We need a new generation of young imaginative teachers such as you guys, to keep stressing that what we have to offer is a powerful way of thinking, more valuable than a set of formulas. Don't give up! – roy smith Jan 14 '11 at 0:09
On the theme of what math is supposedly really about, let me quote verbatim from the catalog course description of Berkeley's Physics C10, Descriptive Introduction to Physics (i.e., Physics for Poets): "The most interesting and important topics in physics, stressing conceptual understanding rather than math..." See for yourself at sis.berkeley.edu/catalog/… – KConrad Jan 14 '11 at 8:19

I taught a fourth-semester course called "Introduction to Analysis," in which we looked at differential calculus for a second time, stressing the foundations, the logical structure, and proving all the key theorems. We used Stephen Abbott's excellent book, Understanding Analysis.

The course was intended primarily for math majors, although we had some interested students from other programs. Becuase we had 8 – 12 students each time I taught the course, I thought it would be a pity to lecture. So I ran the course as a seminar. I would lecture briefly to begin and end each chapter, and then I assigned problems from the textbook, for which the students had to present solutions in class. I would sit at the back of the class, and observe the discussions that took place after the presentations. Typically, if an error were made in a proof, the students wouldn't necessarily notice right away. Instead, someone would ask, "Could you explain again how you got from line 3 to line 4?" or some such question. The presenter would typically struggle to explain the point, and within a few minutes everyone could see that there was something wrong. If the group could patch up the proof on the spot, great. If not, I would send them away, sometimes with a hint, with the task of fixing it up and presenting it again next time.

As long as all the points that I wanted to be discussed were actually discussed, I would stay silent. Of course, if not all the relevant points were brought up, I would ask questions to move the class in the direction I wanted them to go.

The feedback I got from students was interesting. They told me it was much more work than a regular class, but they learned a lot more than in a regular class, too. I think this has implications for all of education ... it's a key reason why lecturing to 500 students is largely ineffective, no matter how brilliant the lecturer. I took this feedback as evidence that this method of teaching proofs can be effective.

Secondly, a comment about calculus/analysis textbooks: the vast majority of them provide no training in the kind of thinking needed for creating proofs. (This is the reason that commenters refer to specialist books (Polya is great, as is Proofs and Refutations by Imre Lakatos), not standard calculus texts.) They simply provide finished products, often very tersely, without any sense for the thinking that goes into shaping a proof. Abbott's book is a lovely counterexample. At a higher level (for analysis, anyway), T.W. Korner's A Companion to Analysis is beautiful. The first few pages of this book provide tremendous motivation for the need to prove seemingly obvious theorems.

My point here is that writers of standard textbooks can learn a lot about how to make sections on proof much more effective. Part of the problem is that publishers want to please everyone, to maximize profits, and so they tightly restrict page count while trying to cram in as much content as possible. As in classrooms, cramming in as much content as possible is counterproductive to good teaching and learning.

-
Thanks Santo. You mention the students' feedback was positive and they claimed to have learned a lot more than in a regular course, so that's some evidence for the effectiveness of this method. What about what you saw? Did you notice real improvements in their proof-writing abilities from the start of the semester to the end? What about on an absolute scale - by the end of the semester did they seem prepared to take an honest math course in their next semester? – Amit Kumar Gupta Jan 13 '11 at 19:48
I'm also curious, were there any math majors who didn't take your course? Do you have any idea how those students fared in comparison to your students in some of their fifth semester math courses? – Amit Kumar Gupta Jan 13 '11 at 19:49
Hi Amit, Yes, I did notice that students tended to improve their abilities a lot more than in a typical lecture course. They were forced to prepare for each class, and the additional work they did was the main reason. However, there are additional reasons. I find that students were far more engaged ... there was real enthusiasm for learning, particularly on the part of some of the students, not all of whom were math majors. (I recall one student in particular who did not accept Cantor's diagonal argument, and kept at it the whole semester, trying to poke holes in it. – Santo D'Agostino Jan 13 '11 at 20:11
Hi Amit, to continue my response, this was a required course for math majors at my (former) school, and it was an "honest math course" as we learned analysis at the same time as learning how to do proofs. This is part of what I liked about the course: the training in doing proofs was in the context of core mathematics. Since all math majors were required to take this course, one can't do the kind of comparison you ask about. However, some of the students who went through the course and are now graduate students say that it was an important preparation for graduate school for them. – Santo D'Agostino Jan 13 '11 at 20:15
Excellent point about standard textbooks. I have seen exactly one textbook not specifically written for the purpose give advice about how to construct proofs, and it was not a mathematics textbook: it was Sipser's Introduction to the Theory of Computation. – Qiaochu Yuan Jan 16 '11 at 22:17

Regarding different flavors of approach 1, here are some words from Halmos.

I have taught courses whose entire content was problems solved by students (and then presented to the class). The number of theorems that the students in such a course were exposed to was approximately half the number that they could have been exposed to in a series of lectures. In a problem course, however, exposure means the acquiring of an intelligent questioning attitude and of some technique for plugging the leaks that proofs are likely to spring; in a lecture course, exposure sometimes means not much more than learning the name of a theorem, being intimidated by its complicated proof, and worrying about whether it would appear on the examination.

Many teachers are concerned about the ... amount of material they must cover in a course. One cynic suggested a formula; since, he said, students on the average remember only about 40% of what you tell them, the thing to do is to cram into each course 250% of what you hope will stick. Glib as that is, it probably would not work.

Problem courses do work. Students who have taken my problem courses were often complimented by their subsequent teachers. The compliments were on their alert attitude, on their ability to get to the heart of the matter quickly, and on their intelligently searching questions that showed that they understood what was happening in class. All this happened on more than one level, in calculus, in linear algebra, in set theory, and, of course, in graduate courses on measure theory and functional analysis.
-
I agree. except about the retention rate. One of my friends, an outstanding high school teacher (the late Steve Sigur) said that after one year, essentially NO content is retained from a traditional course. So think hard about what you try to convey, if you want it to be memorable. – roy smith Jan 14 '11 at 2:51
@roy: The essentially no contents statement strikes me as too strong, as it leaves out the intangibles; the things you remember, influence you, but are unable to articulate cleanly. To me, most of my UG Physics classes are this. Or, in the immoral words of Édouard Herriot: La culture, c'est ce qui reste quand on a tout oublié. – Thierry Zell Jan 14 '11 at 12:36
Good point Thierry, I may have quoted him wrong, but I think he meant essentially what you are saying, but you are saying it better than I did: only the intangibles are retained, not the formulas, so it is important to teach some memorable things that are not just formulas. Great quote! – roy smith Jan 14 '11 at 16:49
@Qiaochu : Could it work to giving the students three different theorems (eventually loosely related) each with its own proof (one of the proof being false) and ask them which is the false one. Note that some may think that one of the theorem is false... – Jérôme JEAN-CHARLES Jan 17 '11 at 1:00
By the way Halmos is responsible in a sense for my getting a PhD, by his directness. I met him once about 1971 and said I did not care if I had a PhD, just that I was doing good mathematics. His response: "That is a cop - out!" I was so p***ed off, I began to commute 210 miles round trip 3 times a week to attend a class at the UW in Seattle from Ed Curtis to get back in the flow. Then shortly afterwards I took a long leave of absence to go back to grad school at Utah, and finish my degree. So Halmos is one of my revered teachers. – roy smith Jan 17 '11 at 1:12

As an undergraduate, I have no experience with the teaching side of this question, so I might not be able to answer it properly. However, I do feel very strongly about option (1) because of my own experiences, so I'll quickly mention them as it may be of some use:

In my high school we did very few proofs. I did AP calculus, which I did enjoy, but not to the same extent as physics. Before University I had no intention of going into mathematics, mainly because of several ill-conceived views of what it actually was.

However in first year, things changed a lot. My honors course was completely proof based, and we were taught calculus rigorously. There was also a weekly problem-solving session (Putnam) where improving at proving was the emphasis. Later that term, I realized I wanted to learn more, so I picked up Rudin 3E and began to read it. The chain of events that followed over the next year made me decide to do a degree in math (particularly my summer project). I remember feeling that "I had never seen mathematics before," because proving things in Analysis and Algebra (however basic) does require a very different style of thinking.

Anyway the point that I'm trying to get at is if in my first year we had not done any proofs, I would not have applied to work in math for the summer, or had the desire to read about it on my own. I probably wouldn't be doing a degree in honors math right now (it is likely either engineering or physics).

I have personally found a trend, the higher the level the course, the more aesthetically pleasing the material is. So how can people want to go into mathematics when they haven't seen as many of the real reasons that people pursue it.

(and the really pretty reasons too)

-
"So how can people want to go into mathematics when they haven't seen as many of the real reasons that people pursue it." Good question. I have often wondered such things. What does it feel like to be a math major who spends half his time studying how to solve problems in calculus and linear algebra and differential equations, and in the senior year learns a little group theory to the point of, say, Lagrange's theorem on subgroups? What idea do they have of mathematics when they graduate? Are they satisfied with what they learned? Should they be? These questions haunt me sometimes. – Pete L. Clark Jan 14 '11 at 11:12
I had a similar experience. I did not care much for math in high-school, but my parents both have degrees in math and promised me it gets more interesting, which is the only reason why I tried it after high-school. Fortunately, I ended up starting with abstract linear algebra (did not even see a single matrix until at least 6 weeks into the course). The irony of course is that my students barely get to see the things that got me excited about math towards the end of their training, if at all. – Thierry Zell Jan 14 '11 at 14:16
I know of exactly one subject in the liberal arts where the 'methods' course - an introduction to the epistemology and methodology of the discipline - is frequently taught to first year students. This is Religion, a subject where many students come in with a large number of 'facts' and an immediate deconstruction of them is healthy. Imagine telling a historian or philologist that historiography or literary theory ought to be taught to first years. They would tell you you were barking mad; almost all the students would be scared away from the major. How is mathematics different? – Alexander Woo Jan 16 '11 at 21:40

Let's say you choose 2. This is a sort of motivation-less course, naturally - all the things that will be proven, or at least many of them, are somewhat obvious to people who have lots of math experience, which the typical person to make it that far in the math curriculum will be (see David Bressoud's talks, of which that is one, for some fairly troubling statistics).

Okay, but you can turn that on its head. The reason such things are obvious (early in such a course, for instance, one usually proves that if $p|n^2$, then $p|n$) is because one has played with numbers a lot. So giving students something new in which to develop context and intuition is a great idea. Graph theory is a standard place to do this - proving easy things about colorings or connectivity - but one could introduce the groups $\mathbb{Z}_n$ or something with a little more structure than one initially thinks.

I saw a great talk where proving things about the decimal expansion of numbers was a big part of such a course. This can get into primitive roots, surds, etc., if you're ambitious - or just provide something a little off the beaten path.

Now, this doesn't look like an answer to your question, but it is. Namely, now that no one knows quite what the right answer is, the whole class can work together to make a proof that they all believe (and if they're wrong, you put it on the test). This isn't quite Moore method, but is of course influenced by it. Or you can make a journal for such things and give them feedback, or whatever you like. It's not the usual technique for teaching proof-writing, but is more realistic and can be easily complemented to the techniques you're currently studying (e.g., some graph theory stuff pretty much has to be proved by induction).

And something they've created from scratch is going to be much more effective in figuring out how to attack a proof. The key is that this will not be successful without doing it fairly consistently - not necessarily every day, but providing a consistent (perhaps weekly?) opportunity to do this.

-
I heard about a first course on proofs taught a few years ago in which the instructor based the whole course on graph theory. It was a complete disaster since the students in the course (math majors, but also math ed. students) never caught on to why they should give a hoot about graph theory. So be careful when you say that proving easy things about graphs is actually going to inspire students. – KConrad Jan 13 '11 at 4:35
Well, of course it depends on the clientele, as it were. And I wasn't recommending basing the whole course on graph theory - that is the OP's option 1. I'm just suggesting a possible supplement to a type 2 course. With respect to your friend's experience, I've had the opposite reaction - students who never really cared about why it was useful; they just loved drawing the graphs! I suppose there are as many experiences as groups of students. – kcrisman Jan 13 '11 at 15:44
@Andres: Yes if all students agree on a proof that means they also get some sense of what is 'no proof' or bad proof and before they will learn to be critical. – Jérôme JEAN-CHARLES Jan 17 '11 at 0:50
@KConrad: I agree that graph theory may seem rather artificial to students if it is presented without its numerous applications to areas such as combinatorial optimization, complex networks, computer science, and discrete geometry. That's the danger of using it in a proofs course, where the emphasis is unlikely to be on the applications. – J W Jan 25 '13 at 5:56

Although I don't speak especially from teaching experience, I think a good hybrid approach is to teach a combinatorics course which requires a lot of proofs. You're doing real math for its own sake, but it's a good subject to cut your teeth on serious proofs, because the definitions are clear and students don't have to deal with new abstractions at the same time.

-

I'll try not to rant.

Necessity of a Transition Course?

The way I see it, you will need a transition course if the following applies:

1. Your students start out with Calculus;
2. Your school mixes math majors with others in Calculus (for size reasons or other).

For instance, at Vassar the typical major starts with linear algebra in the fall followed by multivariate in the Spring. That's already very "proofy" (certainly the way they seem to do it is!) and, as you can check, there is no proofs course on their catalog. I had a somewhat similar experience doing my UG in France.

You need #2, because if you can have dedicated Calculus sections for math majors, then as Pete pointed out, you can take them through a course that will teach them both Calc and proofs, but you wouldn't want to submit the general public to that course.

So to come back to the OP's question, I don't really think there is much of a choice between option 1 and option 2 because which one applies depends only on your public and material circumstances, not really on pedagogical choices.

What I'm really interested in

So the way I see it, if #1 & #2 hold, then you do need that transition, because the first romp through calculus has to be more computational, or you're really short-changing your students, both math-majors and not, at least in a typical course. So at some point, the students will need to transition, i.e. OP's model 1.

Now a related question is how do you help the students transition. And I have yet to teach my institution's proofs course, but I am very skeptical of these. At the very least, I can say that I've seen textbooks that were not promising at all: I like the logic and truth table bits, though where I am this would be covered in Discrete Math, i.e. before the proofs class. But some texts have: here is a chapter about how to do proofs in linear algebra, here is a chapter about how to do proofs in geometry, etc., somehow emphasizing the differences instead of the commonalities in proofs.

I should mention that not all textbooks are this bad; this semester, we're using the art of proof that seems a decent book. However, I think it's interesting that none of these books really seem to stand on their own: they are textbooks first and books second, when most of the books in my math library can be picked up and enjoyed whether you're taking a course from them or not.

To me, a proofs course remains a weird animal. I'd much rather ease the transition within a specific topic (e.g. Linear Algebra in my Vassar example). Also, learning how to write proofs is a long process, just like writing in general. The proofs class somehow sends students the message that there's an off-on switch: before this course you don't know how to write proofs, after this course you will; leaving a rather misleading impression.

-

I taught the transitions' course at a large state university a number of years ago, with reasonable success. The clientele of this (purely elective) course was mainly B students in calculus who would likely have done poorly in real analysis or abstract algebra, and would have had difficulty completing a math major.

To maximize the impact on students' ability to understand and produce proofs, several things were important:

a) The text was Velleman's How to Prove It: A structured approach, which is readable by average students, clearly delineates the structure and construction of typical proofs, and is full of problems which are elementary but not boring. (For a regular beginning analysis class I just ask the students to read this book---esp. chapter 3 as mentioned by Jon Bannon---and I discuss the basics of this material for a few lectures.)

b) The format of most class sessions was discussion not lecture. To have these students passively listen, like in their previous courses which they demonstrably failed to master, would be useless. Discussion was structured like in a humanities or language course, led by the instructor with specific goals in mind and calling on individual students to involve everyone and make sure they get it. The 22 students were informed that it was essential that they come to class prepared, having read the day's material and having worked the relevant problems, laid out in each week's syllabus.

c) Why we insist on `proof beyond unreasonable doubt'' was explained, referring to the great discoveries of 19th and early 20th century analysis (especially regarding infinite sets and fractals) that demand the enormously skeptical approach to establishing truth which now dominates much of modern mathematics.

Many of the students were weak at the start and apparently benefited from all this. For one, this course was a big step in eventually changing his career from fisherman to gaining a Masters and working in a scientific software company. Another later did A work in a senior-level ODE course I taught. But I did not conduct a randomized controlled study.

-

I am just stepping into the teaching world, and finished my first semester as a teaching assistant in an introductory course in set theory and logic, which is giving a formal background to induction, order relations etc. etc..

I can give my own insight as someone who finished his undergrad degree recently. In my university it is mainly the first method for math students. We see proofs, we are given questions which are mostly about proving or disproving things. By the third year I think that everyone in my class (well, we were quite a small class to begin with) knew very well how to write a mathematical proof.

The second approach you described sounds a bit problematic to me, and I'll tell you why. I took a course in functional analysis. Other than the name of a few theorems, and maybe one or two theorems which I actually remember the contents (but not a single proof) I remember pretty much nothing of the course. Same can be said on the course I took in number theory (though I remember slightly more from that one), and on other topics. It's not all bad, when my friend who's taking a related course asks me a question I usually amaze myself by being able to supply a partial answer, and if I ever encounter the material it's easier to go through it. However, I still don't remember much. Giving someone a course in "How to write proofs" means that for some it will stick, and for others it won't stick - and they won't be able to wake up in the middle of the night and give a formal proof to some theorem they will later name "The Dreaming Lemma"; while in contrast it will take a long time for someone who spent three (or more) years just seeing proofs and writing proofs to forget that method, and not to mention the bonus for deep critical thinking which allows you to be able to scratch off ideas even before they reach your mouth or hands.

That been said, I do think that the second approach is very good when you want to focus on teaching mathematics in a lower level (i.e. non-academic level, or even low level math course to philosophy students) or if your students are in applied mathematics program, or something like that. I don't see how many set theorists and logicians will grow from this sort of method, but I might be wrong and even if I am right - not everyone loves set theory.

-

I am teaching such a course - in a 4 week intensive one course at a time format - right now. This is a reminder to myself to say something intelligent about it in February, and a placeholder for my future answer. (If you see this in mid-February, a reminder to actually put up an answer will be much appreciated. I am posting under my real name and can be Googled.)

One of the things I am thinking about now, 2 weeks in:

It has surprised me the extent that what one might simply call cognitive deficits are an obstacle. Some of my students have trouble consistently being able to keep three ideas with their precise statements in their head at the same time. (I mean to say that if they make a special effort for one or two statements, they can, but it is a struggle for them to do this routinely over even a short proof.) This is a serious problem because when a step involves going from a statement with two quantifiers to another statement, the first statement with the quantifiers has already fills up their head and there is no room for the next statement.

What I am suggesting to my students, with absolute seriousness, is to do a Sudoku puzzle or two every day, preferably with a pen (to force themselves to think through inferences rather than going by trial and error). The inferences involved in doing Sudoku might be quite simple to most of us, but you do have to keep a few facts in your head simultaneously to make the inference, and I am hoping the practice does improve their working memory.

-
Wow! I'm not sure the intensive format really lends itself to this type of course. But I'm sure you'll tell us all about it in a month's time. – Thierry Zell Jan 13 '11 at 13:09
I've got a figurative thread tied to my finger. – Amit Kumar Gupta Jan 13 '11 at 19:51

If you should like approach 2, even a little, you should check out chapter 3 of

How to Prove It: A Structured Approach

(Thanks to Amit and Thierry for their comments! This should have been my answer, as the other stuff was mostly my opinion/a defense for suggesting the book.)

-
Hi Jon, thanks for the response. Can you go into some more detail as to the manner in which such a course benefits students, and the degree to which it benefits students. What specifically have you experienced that demonstrates such manners and degrees of benefit? – Amit Kumar Gupta Jan 13 '11 at 19:58
Will do, Amit. Please let me know if you want me to clarify this more. – Jon Bannon Jan 13 '11 at 20:26
BTW: I posted this answer because the book in question serves the students well as far as allowing students to focus on those aspects of proof that are common to all mathematics courses. My personal taste, however, is that mathematical objects should be engaged fully, and that attempts to make things look "neat" like this may not be helpful. I never, for example, had a course in proof...it seems like something we think is a good idea only after we already know what a proof is. I report this because students seem to do better in analysis at my school once they have read the book. – Jon Bannon Jan 13 '11 at 20:39
I agree that a student should be sensitized to what is routine, and what is not, but it seems possible only when students have already learned how to dot their i's and cross their t's properly. The same way that it's unwise to break the rules of good writing before one has learned to appreciate why they're here. Unfortunately, all of this takes time! – Thierry Zell Jan 14 '11 at 1:23
@Thierry: It does take time. I perhaps said too much here too quickly...it is in danger of asserting something different than I intended it to. My original point was to point out Velleman's book. I found it a nice one for one of these "proof" courses. The comment you are referring to was intended to mean that Velleman's approach very clearly delineates how to dot the i's and cross the t's, leaving the non-routine parts of the proof right before our eyes. They are learning the details, perhaps more thoroughly than I did. – Jon Bannon Jan 14 '11 at 1:41