DRAFT MAY 2003

by Susanna S. Epp

Even rather simple proofs are built atop a normally unexpressed substructure of great logical and linguistic complexity. One can easily write a "clarifying" analysis for a proof which, if the students were capable of comprehending would not be needed in the first place. Figuring out how to describe proof construction simply enough to be intelligible yet detailed enough to be effective is one of an instructor's greatest challenges.

Use of Puzzle Problems: To make the transition from elementary logic to proof, it can be helpful to assign puzzle problems such as Raymond Smullyan's knights and knaves.[ ] When solutions are discussed in class, quite a number of students make it clear that they do not have a natural feeling for the kind of indirect reasoning needed to solve most of the puzzles. Nonetheless, almost all students seem to enjoy them, and working on them helps develop a basis of intuition for proof by contradiction. Discussing the solutions serves to illustrate how inference rules are used in practice and helps students develop a sense for the flow of deductive reasoning, which they will use later in mathematical proofs of all types. Work of Lee and Stenning [ ] provides evidence that Barwise and Etchemendy's computer program Hyperproof [ ] is effective in conveying similar ideas in a course with sufficient time to make use of it.

Identifying the Starting Point and the Conclusion to Be Shown: The most important initial point to communicate to beginning students is that to prove a given property is true they need to move from something that is supposed to something that is to be shown. It then becomes natural to (1) identify what is supposed and what is to be shown, which determines the outer structure of the proof, and (2) address the crucial question "How do I show that?" which determines the proof's inner structure.

The most common type of proof is direct and the most common type of mathematical statement has the form

For all elements x in a set D, if <hypothesis> then <conclusion>.

A direct proof of such a universal conditional statement has the following outline: "Suppose that x is a particular but arbitrarily chosen (or generic) element of D for which the hypothesis is true. We must show that x also makes the conclusion true." A descriptive name for this type of reasoning is generalizing from the generic particular.

A dramatic way to emphasize the power of this procedure for moving from a certain form of statement to an outline of its proof is to show how one can use it to structure proofs involving terms one does not even understand. For instance, given the statement "For all toths T, if T has a rath then every wade of T is brillig," the outline of a proof would be "Suppose T is any toth that has a rath. We must show that every wade of T is brillig." This transformation may seem obvious to a mathematician, but it does not come naturally to many students. Yet as students venture further and further into realms of mathematical abstraction, instinctive ability to use the transformation becomes increasingly essential to their success.

Later, after introducing proof by contraposition and proof by contradiction as well as direct proof, one can help students keep the three basic proof methods separate by pointing out that while for each method there is something supposed and something to be shown, these "somethings'" are dramatically different in each case. In a direct proof one supposes one has a particular but arbitrarily chosen object that satisfies the hypothesis, and one shows that this object satisfies the conclusion. In a proof by contraposition one supposes one has a particular but arbitrarily chosen object for which the conclusion is false, and one shows that for this object the hypothesis is also false. In a proof by contradiction one supposes that the entire statement to be proved is false, and one shows that this supposition leads to a contradiction.

Using Definitions: Mathematically speaking, of course, the most important part of the proof of a statement is how one gets from its hypothesis to its conclusion. But for most of the proofs undergraduate students are asked to construct, the majority of this task is achieved through a logico-linguistic analysis of definitions because the inner structure of a straightforward, or routine, mathematical proof is largely determined by the meanings of the terms in the hypothesis and the conclusion. To answer the question "How do I show that the conclusion follows from the hypothesis?" the prover needs an operational understanding of the "if" direction of the definitions of the mathematical terms in the conclusion. For instance, to show that a certain quantity is rational, one needs to show that it can be expressed as a ratio of integers with a nonzero denominator. To show that one set is a subset of another, one needs to show that any element in the one set is an element in the other. To show that a function f is one-to-one, one needs to show that for any elements x₁ and x₂ in the domain for which f(x₁) = f(x₂), we have x₁ = x₂. Similarly, to work forward from the starting point of a proof, the prover needs an operational understanding of the "only if" direction of the mathematical terms in the hypothesis. Helping students translate the formal wording of a definition into operational terms is one of the most important tasks facing a teacher in a course introducing students to proof.

It is also important to discuss alternate but logically equivalent ways to phrase definitions because it is often the case that the truth or falsity of a mathematical statement is more apparent if one uses one phrasing of a definition rather than another. Moore [ ] gives several examples of student failure resulting from a lack of awareness of alternate versions of definitions. In an introductory course, an instructor needs to build in exploration of such alternate phrasings, showing how to operate with each in the circumstances where it is superior to the others. Selden and Selden [ ] argue that students' difficulty "packing and unpacking" the logic of mathematical definitions and theorems seriously undermines their ability to judge the correctness of mathematical arguments and to formulate arguments of their own. My experience supports this view. It is the main reason I give students practice in translating back and forth from formal mathematical statements to their many different informal versions. Because so many students find this difficult, I often continue to assign translation exercises throughout a large portion of the course.

Tall and Vinner [ ] shed considerable light on students' understanding of mathematical definitions when they introduced the notion of "concept image." They describe the concept image associated with a definition as consisting of "the total cognitive structure that is associated with the concept, which includes all the mental pictures and associated properties and processes." For students to develop concept images adequate to help them effectively evaluate abstract mathematical statements, they need experience with a broad range of examples for each newly defined term. An overly narrow concept image leads to mistaken assumptions and may result in incorrect mathematical arguments. When they define a new term, instructors should also introduce the diagrams and other visual representations that mathematicians use in reasoning about the term. These might be arrow diagrams for relations and functions, the image of a nonspecific real number and its floor sitting on a number line for the study of the floor function, or a kind of blurry generic fraction with an indeterminate numerator and denominator for discussions about rational numbers.

Subject Matter for Students’ First Proof Efforts: A good vehicle for students’ initial proof attempts is elementary number theory – properties of even and odd integers, rational numbers, divisibility, and so forth. Since numbers are familiar objects, students have no hesitation about working with them, yet when challenged to justify whether or not various properties hold, they have considerably more difficulty than one might predict. The many statements whose proofs involve straightforward working from definitions give students ample opportunity to practice fledgling skills.

Disproof by Counterexample: In any course where students are asked to write proofs, it is important to give them statements to disprove by counterexample. One reason is that it is easier for most students to understand disproof by counterexample and to learn to construct counterexamples in simple cases than for them to understand the structure of even simple direct proofs and to become adept at writing them. Another reason is that continuing to challenge students with mathematical statements whose truth or falsity they must determine themselves makes the point that proof and counterexample are first and foremost problem-solving tools.

Exploration and Experimentation: Many instructors have developed introduction-to-proof courses with a heavy emphasis on student experimentation and exploration. See, for example [],[], [], and []. In such courses students are typically given laboratory-style problems to work on, often in groups, and are encouraged to challenge each other’s discoveries and explanations. The idea is to motivate students to come to perceive the need for precise definition and careful reasoning in determining truth and falsity of mathematical statements.

At Franklin and Marshall College, for instance, an initial "module" guides students through a sequence of increasingly pointed questions and activities to discover and verify basic properties of even and odd integers. Another module leads students to discover a pattern in the Fibonacci sequence though having them fill in values in a table for n, f_n (the nth Fibonacci number), and S(n) (the sum of the first n Fibonacci numbers). Later modules treat a variety of mathematical topics ending with an introduction to rings and fields. []

At Queen’s University students who have had some exposure to proof and disproof are given an activity that tells a story about a high school students who has found that for every positive integer up to 23, the quantity n²+n+41 is prime and who has, therefore, conjectured that this expression always produces a prime number. They are then asked "to assert whether they think the high school student was right to make the conjecture, whether the conjecture is right, and if they think so, whether the computations done provide a proof for it by mathematical induction."[]

In France, mathematics educators led by D. Alibert have developed a teaching method they describe as "scientific debate." In a first step, "the teacher initiates and organizes the production of scientific [mathematical] statements by the students. These are written on the blackboard without any immediate evaluation of their validity." In the second step, "the statements are put to the students for consideration and discussion. They come to a decision about their validity by taking a vote, with each opinion supported in some way, e.g. by scientific argument, by proof, by refutation, by counter-example, etc." In the third step, "the statements which can be validated by a full demonstration become theorems, whilst those which are established as incorrect are preserved as "false-statements," with a corresponding counter-example."

My own experience with such methods has been positive, my main reservation being the amount of class time required to use the methods extensively. Especially in discrete mathematics courses with relatively large class sizes and many topics to be covered, it is usually not possible to dedicate a lot of time to exploration. However, even in such a setting, it is possible to incorporate some of it, as indicated in some of the sections below.

Student Presentations: Despite careful preparation for the process of writing proofs on their own, a significant fraction of students have great difficulty. Part of the reason may be that just a few weeks of background material is insufficient to overcome casual attitudes toward language and reasoning that have developed over a lifetime. In my own classes, I find that some students cannot believe I am serious about my demand for coherent expression, while others simply have difficulty putting all the pieces together correctly.

One helpful countermeasure is to have students present proofs from homework assignments for the rest of the class at the blackboard. This is especially effective if started in the very first class period after proofs have been assigned. It is important, however, to do this in a way that preserves the self-esteem of the presenters. One can thank them for being good sports when they volunteer and point out that to the extent that they make mistakes, their mistakes and the ensuing discussion will help the rest of the class avoid similar errors in the future. If the proofs are good, the other students see that the demands made by their instructor can actually be met by one of their own kind. If the proofs contain mistakes or sections that are not well expressed, an instructor can ask for suggestions for improvement from the rest of the class. A ploy is to ask students to imagine they are a research team for a large company, that if they can collectively come up with a perfect answer they will get to share a sizeable bonus. After the class has finished its critique and some changes have been recorded, the instructor can take a turn, using the opportunity both to comment on significant errors that have gone undetected and also to show students the kinds of things the instructor will be looking for when grading students' work.

When I use this technique, I discuss small details as well as larger issues, but I try to put my criticisms in perspective, explaining frankly that certain corrections are more important than others, but that I also care about what might seem to be relatively minor points. For instance, if a student’s proof states that a certain number, say n, is even because it equals 2k, I would ask what was missing. Most likely, based on the emphasis I had previously placed on definitions, one of the other students would tell me to add "for some integer k." I would agree, pointing out that 1=2×(1/2) and yet 1 is not even, and adding that it is not enough that n is 2 times something - that something has to be an integer.

My main reason for engaging in these kinds of critiques with the class is to provide immediate feedback on students' proof writing. A secondary reason is to counteract student anxiety about how their proofs will be evaluated. Since there is more than one right way to construct any given proof and since different instructors may well have different standards of correctness, I feel obliged to try to give my students a sense of the range of proof styles I consider acceptable and to indicate which parts of a proof I consider most important. So when I critique student proofs, present my own, and write proofs at the board that have been developed collaboratively with members of the class, I discuss alternative ways of expressing the steps which I would consider acceptable. I also talk about conventions of mathematical writing (such as giving only part of the reason for a certain step, enough to indicate that the writer of the proof has considered and resolved the issue but not so much as to overload the proof with verbiage) and the fact that the amount of detail included in a proof varies considerably depending on the intended audience. In my classes I generally suggest that students address their proofs to a fellow student who has missed the last few classes.

Problems asking students to determine whether a given mathematical statement is true or false are especially useful for class presentations. For instance, consider the statement "For all integers a, b, and c, if a divides bc then a divides b or a divides c. Typically, one significant fraction of the class will claim that this statement is false and another will say they think it is true. Once when I asked two students from each group to go to the board and present their solutions, I have had two false proofs or partial proofs, one false counterexample, and one true counterexample. Especially if one points out that the ability to come up with correct answers to questions like this provides the theoretical foundation for engineering airplanes that do not crash, etc., such an outcome is a powerful argument for the importance of careful reasoning.

Additional Strategies for Dealing with Students’ Difficulties: Other strategies for dealing with student difficulties are

• having students complete a few fill-in-the-blank proofs as part of the process of starting to write their own;
• supplying model solutions for some of their homework problems so that they come to see that their individual work is really supposed to look something like the kind of thing we have been doing in class;
• discussing the kinds of errors often made in writing proofs and assigning homework problems of the find-the-mistake variety;
• suggesting that students read their proofs out loud to test whether they are written in coherent sentences; and
• making sure that even in a large class one gives each student detailed feedback about the work they have done on each type of proof that is assigned.

A good way to accomplish the last item is to have students submit one or two drafts of their solutions to a few selected problems and make suggestions for improvement on each draft. Another way is to have students work on proofs in groups and go from group to group reviewing their work and helping them see how to correct it. One can also give students "partner quizzes," in which they work in pairs to prove or disprove various statements. When I use this technique, I make extensive comments on the paper submitted by each pair and return both the original and a photocopy so that each student will have a record of both their work and my remarks. This approach gives students practice in speaking mathematics with each other and reduces grading time in a large class. To learn as complex a skill as proof construction, most students need quite a bit of individual, back-and-forth interaction with an instructor. To the extent that one cannot act as a private tutor to every student, one can try to devise effective substitutes.

To help students cope with the often frustrating enterprise of mathematical discovery, I encourage class discussion about the psychological aspects of the process. For instance, if a few students have found a counterexample for a mathematical statement that stymied a majority of the class, I ask the successful students to share the thoughts that went through their minds when the counterexample occurred to them. I also point out that mathematical discovery may involve emotional ups and downs, that even the best mathematicians find mistakes in their arguments which force them to abandon one approach and seek another. I also cite results of Schoenfeld [45] that while successful problem solvers are persistent, they readily change to new approaches when previous ones do not appear to be working, though they might well return to a previous approach if a new attempt seems unsuccessful.

To assist students in structuring their time when they are trying to determine truth or falsity of a mathematical statement, I suggest that they begin by imagining they actually have an object or objects satisfying the conditions described in the hypothesis. They can then ask themselves whether the conclusion must necessarily follow. If, after some effort, they do not see why this must be so, they can explore the possibility that the statement might be false by trying to think of elements that satisfy the hypothesis but not the conclusion. If this effort also fails, they can posit a situation where the hypothesis is true and the conclusion is false and try to derive a contradiction. If this method also seems to lead nowhere, the very process of having tried it and the other approaches may have resulted in insights that may lead to greater success when one of the previous approaches is tried again.

Once students have a sense for the overall structure of a proof, which is largely determined by the logical form of the statement to be proved and of the definitions of its terms, I encourage them to try to identify the crux, or essential idea of the proof. This is a process similar to Polya's [ ] "looking back" and is also related to Leron's [ ] "top-level view of the proof." For a simple proof, the pivotal idea may come immediately to mind. For a more complicated proof, one may only realize the essence some time after plowing mechanically through a mass of detail. A practiced mathematician can easily reconstruct a lengthy proof just by recollecting its essence, but students often have difficulty when told the main idea because they are still struggling to master the underlying logic of proof construction.

Conclusion: A few years ago I had an experience with one particular class that made a special impression on me. The class was unusually small, only twelve students, and was the second quarter of a sequence. The previous quarter had dealt with logic, an introduction to direct and indirect proof, mathematical induction, and elementary combinatorics, all interwoven with various computer science applications. The second quarter was to cover set theory, function properties, recursion, some analysis of algorithms, relations on sets, and an introduction to graph theory, also with an admixture of applications. The class met only once a week but in three-hour sessions.

The small size of the class and the length of the sessions gave me a chance to work with students more intimately than usual. I began each period by having students discuss in groups of three or four the homework they had prepared for that day and went from group to group talking with each at length. Overall the class atmosphere was excellent, and several students showed the kind of eager, enthusiastic intelligence that is a teacher's joy. What surprised me was that as the course moved from one topic to the next, almost all the students who had attained a relatively sophisticated level of achievement in dealing with a previous topic made it clear that they felt they had to struggle to succeed with the next. Yet as we worked through their questions and difficulties, they ultimately performed excellently with the new topic as well. Their understanding of general methodological principles clearly made it easier for them to learn the new material but it did not make it trivial for them.

This experience brought home to me more effectively than any before that abstract mathematical thinking is not something that either one is able to do or one is not able to do. Because of the experience I have become especially conscious of the need to respect my students and never to act surprised by their questions. Even when a student asks a question whose answer I have already discussed, I try to respond to it as if it were fresh. After all, nobody can concentrate 100% of the time when new ideas are coming in fast and furiously. In all likelihood the student was not mentally prepared to absorb the answer when I previously addressed the question. For the student to formulate the question means that they have thought about the issue, want to know the answer, and are probably ready to understand it. That is cause to celebrate. It may also be that clarifying the issue at this point in the course (if possible in a slightly different way from that presented earlier) will give the other students in the class greater insight also.

My main advice to those teaching courses whose goal is to develop students mathematical reasoning powers is to play an activist role but recognize that achieving success is a long-term process. I have sometimes been surprised when students who in my view fell far short of achieving the levels of accomplishment I strive for tell me how valuable they found the course in helping them do better work in their other courses or (I am always pleased to hear) in their jobs.

The analogy I like to draw is of a child learning to walk. It takes months of daily effort for most children to take their first steps and several more months until they actually become steady on their feet. When a child is trying to move from one stage to the next in learning to walk and has failed several times, we don't say "Forget it." We remain calm, good humored, and encouraging. And when the child finally succeeds, we spare nothing in expressing our delight.