PROOFThis discussion addresses several different aspects of proof and includes many links to additional readings. You may want to jump to the activities, try some out, and then double back to the readings once you have had a chance to reflect on how you approach proofs. You can use the table of contents below to navigate around this chapter:
WHAT IS A PROOF?In everyday life, we frequently reach conclusions based on anecdotal evidence. This habit also guides our work in the more abstract realm of mathematics, but mathematics requires us to adopt a greater level of skepticism. Examplesno matter how manyare never a proof of a claim that covers an infinite number of instances. A proof is a logical argument that establishes the truth of a statement. The argument derives its conclusions from the premises of the statement, other theorems, definitions, and, ultimately, the postulates of the mathematical system in which the claim is based. By logical, we mean that each step in the argument is justified by earlier steps. That is, that all of the premises of each deduction are already established or given. In practice, proofs may involve diagrams that clarify, words that narrate and explain, symbolic statements, or even a computer program (as was the case for the Four Color Theorem (MacTutor)). The level of detail in a proof varies with the author and the audience. Many proofs leave out calculations or explanations that are considered obvious, manageable for the reader to supply, or which are cut to save space or to make the main thread of a proof more readable. In other words, often the overarching objective is the presentation of a convincing narrative. Postulates are a necessary part of mathematics. We cannot prove any statement if we do not have a starting point. Since we base each claim on other claims, we need a property, stated as a postulate, that we agree to leave unproven. The absence of such starting points would force us into an endless circle of justifications. Similarly, we need to accept certain terms (e.g., "point" or "set") as undefined in order to avoid circularity (see Writing Definitions). In general, however, proofs use justifications many steps removed from the postulates. Before the nineteenth century, postulates (or axioms) were accepted as true but regarded as self-evidently so. Mathematicians tried to choose statements that seemed irrefutably truean obvious consequence of our physical world or number system. Now, when mathematicians create new axiomatic systems, they are more concerned that their choices be interesting (in terms of the mathematics to which they lead), logically independent (not redundant or derivable from one another), and internally consistent (theorems which can be proven from the postulates do not contradict each other). (Download Axiomatic Systems (Lee) and see sections 6.1, 8.1, and 8.4 in book 3b of Math Connections (Berlinghoff) for further explanations, activities, and problem sets on axiomatic systems, consistency, and independence). For example, non-Euclidean geometries have been shown to be as consistent as their Euclidean cousin. The equivalence between these systems does not mean that they are free of contradictions, only that each is as dependable as the other. This modern approach to axiomatic systems means that we consider statements to be true only in the context of a particular set of postulates. WHY DO WE PROVE?To Establish a Fact with CertaintyThere are many possible motives for trying to prove a conjecture. The most basic one is to find out if what one thinks is true is actually true. Students are used to us asking them to prove claims that we already know to be true. When students investigate their own research questions, their efforts do not come with a similar guarantee. Their conjecture may not be true or the methods needed may not be accessible. However, the only way that they can be sure that their conjecture is valid, that they have in fact solved a problem, is to come up with a proof. Students confidence in a fact comes from many sources. At times, they appeal to an authoritative source as evidence for a claim: "it was in the text" or "Ms. Noether told us this last year." It has been my experience that such justifications carry little practical persuasive value. For example, a class discussed the irrationality of and proofs of that fact, yet an essay assignment on a proposal to obtain the complete decimal expansion of still generated student comments such as, "if eventually turns out not to be irrational then that project would be interesting." Thus, an authoritative claim of proof is only good until some other authority shows otherwise. Mathematical truths do tend to stand the test of time. When students create a proof themselves, they are less likely to think of the result as ephemeral. A proof convinces the prover herself more effectively than it might if generated by someone else. To Gain Understanding"I would be grateful if anyone who has understood this demonstration would explain it to me." Fields Medal winner Pierre Deligne, regarding a theorem that he proved using methods that did not provide insight into the question. There are proofs that simply prove and those that also illuminate. As in the case of the Deligne quote above, certain proofs may leave one unclear about why a result is true but still confident that it is. Proofs with some explanatory value tend to be more satisfying and appealing. Beyond our interest in understanding a given problem, our work on a proof may produce techniques and understandings that we can apply to broader questions. Even if a proof of a theorem already exists, an alternative proof may reveal new relationships between mathematical ideas. Thus, proof is not just a source of validation, but an essential research technique in mathematics. If our primary consideration for attempting a proof is to gain insight, we may choose methods and types of representations that are more likely to support that objective. For example, the theorem that the midpoints of any quadrilateral are the vertices of a parallelogram can be proven algebraically using coordinates or synthetically (figure 1). Figure 1. The diagrams for coordinate and synthetic proofs A synthetic proof rests on the fact that the segment connecting the midpoints of two sides of a triangle, the midline, is parallel to the third side. In quadrilateral ABCD (right side of figure 1), the midlines of triangles ABD and CBD are both parallel to the quadrilateral diagonal BD and, therefore, to each other. It is clear that if point C were to move, the midline for triangle BCD would remain parallel to both BD and the midline of triangle ABD. To complete the proof, one would consider the midlines of triangle ADC and triangle ABC as well. The coordinate proof uses the coordinates of the midpoints to show that the slopes of opposite midlines are equal. For many people, the synthetic proof is more revealing about why any asymmetries of the original quadrilateral do not alter the properties of the inner parallelogram. It also illustrates how a proof can be a research tool by answering other questions, such as "when will the inner quadrilateral be a rhombus?" Because midlines are one half the length of the parallel side, the inner parallelogram will have equal sides only when the diagonals of the original quadrilateral are congruent. Sometimes our inability to develop a proof is revealing and leads us to reconsider our examples or intuitions. After countless attempts to prove that Euclids fifth postulate (the parallel postulate) was dependent on the other four, mathematicians in the nineteenth century finally asked what the consequences would be if the postulate were independent. The doubts that arose from the failure to obtain a proof led to the creation of non-Euclidean geometries. To Communicate an Ideas to OthersOften, mathematicians (of both the student and adult variety) have a strong conviction that a conjecture is true. Their belief may stem from an informal explanation or some convincing cases. They do not harbor any internal doubt, but there is a broader audience that retains some skepticism. A proof allows the mathematician to convince others of the correctness of their idea. A Making Mathematics teacher, in the midst of doing research with colleagues, shared his feelings about proof: Just so I can get it off of my chest, I hate doing proofs with a passion. Its the part of mathematics that I grew to hate when I was an undergraduate, and its what so many of my former students come back and tell me turned them off to continuing on as a math major. I remember having a professor who held us responsible for every proof he did in class. Wed probably have a dozen or more to know for each exam, in addition to understanding the material itself. I can remember just memorizing the steps, because the approaches were so bizarre that no "normal person" would ever think of them in a million years (yes, I know I'm stereotyping). This teachers frustrations with proofs involved having to memorize arguments that were neither revealing (and therefore, not entirely convincing) nor sufficiently transparent about the process by which they were created. Yet, this same teacher, on encountering collegial doubts about his conjecture concerning Pascals triangle wrote, "Well, I decided to try and convince you all that the percentage of odds does in fact approach zero as the triangle grows by proving it." His efforts over several days produced a compelling proof. His conflicting attitudes and actions highlight the distinction between proofs as exercises and proofs as tools for communication and validation. A genuine audience can make an odious task palatable. For the ChallengeDifficult tasks can be enjoyable. Many mathematical problems are not of profound significance, yet their resolution provides the person who solves them with considerable gratification. Such success can provide a boost in self-esteem and mathematical confidence. The process of surmounting hurdles to a proof can have all of the thrill of a good mystery. Students (and adults) are justifiably excited when they solve a problem unlike any they have previously encountered and which no one else may have ever unraveled. To Create Something BeautifulThe more students engage in mathematics research, the more they develop their own aesthetic for mathematical problems and methods. The development of a proof that possesses elegance, surprises us, or provides new insight is a creative act. It is rewarding to work hard to make a discovery or develop a proof that is appealing. The mathematician Paul Erdös spoke of proofs that were "straight from the Book"the Book being Gods collection of all the perfect proofs for every theorem. Although Erdös did not actually believe in God, he did believe that there were beautiful truths waiting to be uncovered (Hoffman). To Construct a Larger Mathematical TheoryWe rarely consider mathematical ideas in a vacuum. Our desire to advance a broader mathematical problem is often a source of motivation when we attempt a proof. For example, a number of mathematicians spent many years attempting to characterize a class of objects known as simple groups (Horgan). Their cumulative efforts resulted in thousands of pages of proofs that together accomplished the task. Many of these proofs, significant in their own right, were of even greater value because of their contribution to the larger understanding that the mathematics community sought. For a further discussion of the role of proof in school curricula, see Do We Need Proof in School Mathematics? (Schoenfeld, 1994). WHAT DO WE PROVE?We can prove many different types of claims.
WHEN SHOULD STUDENTS PROVE?In general, students should attempt a proof in response to one of the motivations listed in the Why Do We Prove? section. If students only attempt proofs as exercises, they come to see proof as an after-the-fact verification of what someone else already knowsit becomes disconnected from the process of acquiring new knowledge. However, students derive considerable satisfaction from proving a claim that has arisen from their own investigations. If students in a class disagree about a conjecture, then that is a good time for the individuals who support it to look for a proof in order to convince the doubters. If a student seems particularly taken with a problem and starts to feel some sense of ownership for the idea, then she should attempt a proof in response to her own mathematical tastes. If two student claims have a connection, the students may want to prove the one that is a prerequisite for proving the other. A focus on formal proof should grow gradually. When we emphasize formal proof too soon and too often, before students have developed a rich repertoire of proof techniques and understanding, their frustration with, and subsequent dislike of, the challenge can become an obstacle to further progress. It is always appropriate to ask students what led them to their conjectures and why they think they are true. We begin by asking for reasons, not formal proofs, and establish the expectation that explanations should be possible and are important. Note that we ask "why" regardless of the correctness of a claim and not just for false propositions. As we highlight that they always should be interested in why an idea is true, students begin to develop the habit of asking "why?" themselves. A good time to ask a student to write out a proof is when you think that she has already grasped the connections within a problem that are essential to the development of a more formal argument. This timing will not only lead to an appreciation for how proofs can arise organically during research, it will also lead to some confidence regarding the creation of proofs. It is not necessary for students to prove all of their claims just for the sake of thoroughness. Published articles often prove the hard parts and leave the easier steps "for the reader." In contrast, a student should begin by trying to prove her simpler assertions (although it may be difficult to figure out how hard a problem will be in advance). When students have conjectures, label them with the students names and post them in the class as a list of open problems. Then, as students grow in the rigor and complexity of their proofs, they can return to questions that have become accessible. When a student does create a proof, have her describe it to a peer, give an oral presentation to the class, or write up her thinking and hand it out for peer review. The students should come to see themselves as each other's editorial board, as a group of collaborating mathematicians. They should not be satisfied if their classmates do not understand their argument. It is a long struggle getting to the point where we can write intelligible yet efficient mathematics. One of my students once presented proofs of a theorem four times before the class gave him the "official Q.E.D". Each of the first three presentations generated questions that helped him to refine his thinking, his definitions, and his use of symbols. HOW DO WE PROVE?General ApproachesLearning to prove conjectures is a lifelong process, but there are some basic considerations and methods that students should focus on as they begin to develop rigorous arguments. The first concern is that they be clear about what they are trying to provethat they unambiguously identify the premises and the conclusions of their claim (see Conditional Statements in Conjectures). The next goal should be to try to understand some of the connections that explain why the conjecture might be true. As we study examples or manipulate symbolic representations, we gain understanding that may lead to a proof. Because understanding and proof often evolve together, if a student wants to prove a conjecture that a classmate or teacher has presented, she should consider undertaking an investigation that will help her recreate the discovery of the result. This process may provide insight into how a proof might be produced. (See Schoenfeld (1992) for more discussion of problem solving and proof.) Often, a proof involves a large number of steps that, in our thinking about the problem, we organize into a smaller number of sequences of related steps (similar to when computer programmers turn a number of commands into a single procedure). This "chunking" of many steps into one line of reasoning makes it possible to grasp the logic of a complicated proof. It also helps us to create an outline of a potential proof before we have managed to fill in all of the needed connections (see Proof Pending a Lemma below). When we create a proof, we seek to build a bridge between our conjectures premise and its conclusion. The information in the premise will have a number of possible consequences that we can use. Similarly, we try to identify the many conditions that would suffice to prove our conclusion. For example, if we know that a number is prime, there are numerous properties of prime numbers that we might bring into play. If we seek to show that two segments are congruent, we might first show that they are corresponding sides of congruent figures, that they are both congruent to some third segment, or that it is impossible for one to be either shorter or longer than the other. Once we have considered the possibilities that stem from our premises and lead to our conclusions, we have shortened the length of our proof from "if premise, then conclusion" to "if consequence-of-premise, then conditions-leading-to-conclusion" (figure 2). A main task comes in trying to determine if any of these new statements (one for each combination of consequence and condition) is likely to be easier to prove than the original. Figure 2. Searching for a path to a proof Some conjectures conclusions involve more than one claim. Recognizing all of these requirements can be a challenge. For example, to show that the formula (n2 m2, 2mn, n2 + m2) is a complete solution to the problem of identifying Pythagorean triples, we need to show both that it always generates such triples and that no triples are missed by the formula. Cases such as this, in which we need to demonstrate both a claim and its converse, are common. Sometimes, two approaches to proving a result will differ in both their method and what they teach us. A student working on the Amida-kuji project defined a minimal configuration of horizontal rungs as one that results in a particular rearrangement of the numbers using the fewest rungs possible. He then conjectured that the number of distinct minimal configurations would always be greatest for the reversal of n items (1 2 3 n goes to n 3 2 1) than for any other permutation of the n values. Does this student need to find and prove a formula for the number of minimal configurations for each permutation? Can he somehow compare the number of minimal configurations without actually counting them explicitly and show that one set is larger? These two approaches might both prove his claim, but they require distinctly different findings along the way. Just as we make decisions about the sequencing of ideas that we use to construct a proof, so, too, do we choose from among an array of different technical tools. In the quadrilateral proof above, we represented the same setting using coordinates as well as synthetically. We transform our mathematical ideas into diagrams, numeric examples, symbolic statements, and words. Within those broad categories, there are numerous ways of representing information and relationships and each representation offers the possibility of new understandings. We may further our understanding of a problem by looking at a simpler version of it. We can apply this same approach to proof: prove a special case or subset of cases before taking on the entire problem. For example, a student working on the Raw Recruits project first proved theorems about the cases with one or two misaligned recruits and then worked up to the general solution. Choosing the right simplification of a problem is important. Had the student focused on a fixed number of total recruits rather than of misaligned ones, she might not have been as successful finding patterns. Proof methodsThe list of proof techniques is endless. Providing students with a repertoire of a few powerful, general methods can give them the tools that they need to get started proving their conjectures. These first techniques also whet students appetites to learn more. Each students own research and reading of mathematics articles (see Reading Technical Literature in Getting Information) will provide additional models to consider when constructing a proof. When students begin work within a new mathematical domain, they will need to learn about the tools (representations, techniques, powerful theorems) common to the problems that they are studying. It is not possible to give ironclad rules for when a given approach to proof will prove fruitful. Therefore, in addition to providing guidance ("It might be worthwhile holding one of your variables constant"), our job mentoring students engaged in proof is to ask questions that will help them reflect on their thinking. Is planning a part of their process (are they considering alternative strategies or just plowing ahead with the first approach that occurs to them)? Are they connecting the steps that they are exploring with the goal that they are trying to reach (can they explain how their current course of action might produce a useful result)? Are they periodically revisiting the terms of their conjecture to see that they have not drifted off course in their thinking? See Getting Stuck, Getting UnstuckCoaching and Questioning for further questions. The most basic approach that students can use to develop understanding and then a proof is to study specific cases and seek to generalize them. For example, a student was exploring recursive functions of the form . She wanted to find an explicit formula for f and began by looking at with . Her first values: revealed some patterns, but no breakthrough. She then took an algebraic perspective on the problem by looking at the form and not the value of the results. She decided to keep her examples general by not doing the arithmetic at each step: This form revealed an explicit formula, , which pointed the way to a general rule for all a, b, and . This example demonstrates why it is sometimes advantageous not to simplify an expression. Algebra is a familiar, all-purpose tool that we should encourage students to use more often. Many students primarily think of variables as specific unknowns and not as placeholders for an infinite number of examples (see the practice proofs and their solutions for examples of algebraic expressions used in this manner). For descriptions of, and exercises using, some of the most common and powerful proof methods, see the Mathematics Tools on proof: Examples as Disproof and ProofAn example cannot prove an affirmative statement about an infinite class of objects. However, a single example, called a counterexample, is sufficient to disprove a conjecture and prove the alternative possibility. For example, we know of many even perfect numbers (Weisstein). The discovery of a single odd perfect number would be an important proof that such numbers, conjectured not to exist, are possible. Proof By ExhaustionWhen a conjecture involves a finite set of objects, we can prove the conjecture true by showing that it is true for every one of those objects. This exhaustive analysis is sometimes the only known means for answering a question. It may not be elegant, but it can get the job done if the number of instances to test is not overwhelmingly large. The mathematicians who proved the Four Color Theorem (MacTutor) broke the problem into 1476 cases and then programmed a computer to verify each one. Such proofs are not entirely satisfying because they are less likely than a proof that covers all cases simultaneously to have explanatory value. We often break a problem down into categories of instances or cases and not all the way down to individual instances. For example, a theorem about triangles may require separate analyses for acute, right, and obtuse triangles. One challenge when proving via a case-by-case analysis is to have a rigorous means of showing that you have identified all of the different possible cases. Proof Pending a LemmaOne of the more exciting experiences in mathematics is the recognition that two ideas are connected and that the truth of one is dependent on the truth of the other. Often a student will be working on a proof and discover that they have a line of reasoning that will work if some other claim is true. Encourage the student to develop their main argument and then return to see if they can fill in the missing link. A claim that is not a focus of your interest, but which you need for a larger proof, is called a lemma. As students working on a common problem share their discoveries through oral and written reports, they may recognize that a fellow researcher has already proven a needed lemma. Alternatively, they may realize that their conjecture is a straightforward consequence of a general result that another classmate has proven. We call a theorem that readily follows from an important result a corollary. These events contribute enormously to students understanding of mathematics as a communal activity. There are many well-known cases of theorems that mathematicians have proven pending some other result. Of course, that means that they are not actually theorems until the lemma has been established. What is a theorem in these situations is the connection between two unproven results. For example, Gerhard Frey proved that if a long-standing problem known as the Taniyama-Shimura conjecture were true, then Fermats Last Theorem (MacTutuor) must be as well. This connection inspired Andrew Wiles to look for a proof of the Taniyama-Shimura conjecture. WHEN IS A PROOF FINISHED?How do we know that we have proven our conjecture? For starters, we should check the logic of each claim in our proof. Are the premises already established? Do we use the conclusions to support a later claim? Do we have a rigorous demonstration that we have covered all cases? We next need to consider our audience. Is our writing clear enough for someone else to understand it? Have we taken any details for granted that our readers might need clarified? Ultimately, the acceptance of a proof is a social process. Do our mathematical peers agree that we have a successful proof? Although we may be confident in our work, unless others agree, no one will build upon or disseminate our proof. Our theorem may even be right while our proof is not. Only when our peers review our reasoning can we be assured that it is clear and does not suffer from logical gaps or flaws. If a proof is unclear, mathematical colleagues may not accept it. Their clarifying questions can help us improve our explanations and repair any errors. On the other hand, mathematical truth is not democratically determined. We have seen many classes unanimously agree that a false assertion was true because the students failed to test cases that yielded counterexamples. Likewise, there have been classes with one voice of reason trying to convince an entire class of non-believers. The validity of a proof is determined over timereaders need time to think, ask questions, and judge the thoroughness of an exposition. Students should expect to put their proofs through the peer review process. When do peers accept a proof? When they have understood it, tested its claims, and found no logical errors. When there are no intuitive reasons for doubting the result and it does not contradict any established theorems. When time has passed and no counterexamples have emerged. When the author is regarded as capable ("I dont understand this, but Marge is really good at math"). Some of these reasons are more important than others, but all have a role in practice. See Davis and Hershs (1981) The Mathematical Experience for a fine collection of essays on the nature of proof, on methods of proof, and on important mathematical conjectures and theorems. How to End a ProofSince one reason we tackle proofs is for the challenge, we are entitled to a modest "celebration" when a proof is completed. The nicest honor is to name a theorem after the student or students who proved it. If you dub proofs after their creators (e.g., Lauras Lemma or the Esme-Reinhard Rhombus Theorem) and have them posted with their titles, students will be justifiably proud. Give conjectures titles, as well, in order to highlight their importance and as a way to promote them so that others will try to work on a proof. Introduce students to the traditional celebration: ending a proof with "Q.E.D." Q.E.D. is an acronym for "quod erat demonstrandum," Latin for "that which was to be demonstrated." At the end of a proof by contradiction, students can use "Q.E.A.," which stands for "quad est absurdum" and means "that which is absurd" or "we have a contradiction here." These endings are the understated mathematical versions of "TaDa!" or "Eureka!" Modern, informal equivalents include AWD ("and were done") and W5 ("which was what we wanted") (Zeitz, p. 45). We have also seen "" and "MATH is PHAT!" at the end of student proofs. Professional publications are now more likely to end a proof with a rectangle () or to indent the proof to distinguish it from the rest of a discussion, but these are no fun at all. Do remind students that once their celebration is over, their work is not necessarily done. They may still need to explore their theorem further to understand why it is true and not just that it is true, to come up with a clearer or more illuminating proof, or to extend their result in new directions. Additionally, proofs sometimes introduce new techniques that we can productively apply to other problems. In other words, the completion of a proof is a good time to take stock and figure out where to go next in ones research. Like movies that leave a loose strand on which to build a sequel, most math problems have natural next steps that we can follow. WRITING PROOFSWe are not very pleased when we are forced to accept a mathematical truth by virtue of a complicated chain of formal conclusions and computations, which we traverse blindly, link by link, feeling our way by touch. We want first an overview of the aim and of the road; we want to understand the idea of the proof, the deeper context. - Hermann Weyl (1932) The standard form for a mathematical proof is prose interwoven with symbolic demonstrations and diagrams. Students who write paragraph explanations will often comment that they do not yet have a "real proof." However, the two-column style that they believe to be the only acceptable format is often not as clear or informative as a proof with more English in it. Encourage them to add narrative to their proofs and to use whatever form seems most effective at communicating their ideas. Let them know that written language is a part of mathematics. Weyl encourages us tell the story of our proof at the start so that each step in the presentation can be located on that roadmap. We should be able to say to ourselves "Oh, I see why she did that. She is setting up for this next stage" rather than "Where on Earth did that come from? Why did she introduce that variable?" Our goal is not to build suspense and mystery, but to provide the motivation for the important steps in our proofs. As noted earlier, we improve a lengthy proofs story by considering how the pieces of the proof fit together into connected chunks that we can present as separate theorems or lemmas. These chapters in the story reduce the number of arguments that our readers have to manage at any given stage in their effort to understand our proof. Published proofs are often overly refined and hide from the reader the process by which the mathematician made her discoveries. As teachers, we want to encourage students to share the important details of that process. What methods did they consider? Why did some work and others not? What were the examples or special cases that informed their thinking? What dead ends did they run into? The teacher mentioned above, who disliked proof, was frustrated because the proofs that he had read were too polished to be a guide for how to develop a proof. The more we include our data, insights, experimentation, and derivations in our proofs, the more they will help others with their own mathematics. We want to find a balance between the desire to convey the process of discovery, which is often circuitous, and the need to present a coherent argument. Students should develop an outline for each proof that reflects which ideas are dependent on which others. They should punctuate their narrative with clearly labeled definitions, conjectures, and theorems. Proofs should include examples that reveal both the general characteristics of the problem as well as interesting special cases. Examples are particularly helpful, not as a justification, but because they provide some context for understanding the more abstract portions of a proof. Examples may also help clarify imprecise notation or definitions. Some additional recommendations for making proofs more readable:
If any parts of your research were carried out collaboratively or based on someone elses thinking, be sure to acknowledge their work and how you built upon it. For a full discussion on how to write up your results, see Writing a Report in Presenting Your Research. EVALUATING PROOFSWe evaluate proofs at several levels. First, we need to see if we can understand what the proof says. If our mathematical background is sufficient to understand the proof, then, with effort, we should be able to make sense of it (see Reading Technical Literature in Getting Information). Next, we want to decide whether the proof is actually a successful proof. Do all of the pieces fit together? Are the explanations clear? Convincing? A good proof does not over-generalize. If a proof does not work in all cases, is it salvageable for some meaningful subset of cases? Students should be given time to read each other's proofs. They should be skeptical readers who are trying to help their classmate improve their work. They should be supportive by offering helpful questions about claims that are unclear or steps that would improve the proof. The writer of a proof should expect to address any concerns and to work through several drafts before the class declares her work completed. Although we are tempted to believe in our own discoveries, we are also obliged to look for exceptions and holes in our reasoning and not leave the doubting just to our peers. Once a proof passes the first hurdle and we believe it is correct, we come to a different set of criteria for judging proofs. These criteria are both aesthetic and functional and help us to understand why we would want to find different ways to prove a particular theorem. Here are some considerations that students might apply to proofs that they study (see Evaluating Conjectures for further considerations):
Each of us has our own aesthetic for which areas of mathematics and ways of solving problems are most appealing. Mathematicians will often call a proof "elegant" or "kludgy" based on their standards of mathematical beauty. Is a substitution, offered without motivation, that quickly resolves a problem (e.g., let f(x) = cotan(1 x/2)) magical, concise, or annoying? Whichever of the standards above move us to call a proof beautiful, it is an important recognition that judgments of beauty are part of mathematics. Share your own aesthetics with students and encourage them to develop their own. It is perfectly reasonable simply to enjoy geometric or number theoretic problems and solutions more than some other area of mathematics. Some students may love problems that start out complicated but then sift down to simple results. Help them to recognize and celebrate these interests while broadening their aesthetics through the sharing of ideas with each other. Class Activity: One way to highlight the different characteristics of proofs is to ask students to study and compare alternative proofs of the same theorem. Handout Three Proofs that is irrational (table 1, below) and give students time to read all three slowly (note: students should be familiar with proof by contradiction). Ask them to write down questions that they have about the different steps in the proofs. Next have them work in small groups trying to answer the questions that they recorded and clarify how each proof achieves its goal. Have each student then write an evaluation of the proofs: Does each proof seem to be valid? If not, where do they identify a problem? Which proof appealed to them the most? Why? Ask them to consider the other criteria above and choose one or more to address in evaluating the proofs. Students may note that there are similarities among the proofs. All three proofs are indirect and all three begin by eliminating the root and converting the problem to one of disproving the possibility that . These first steps reduce the problem to one involving only counting numbers instead of roots and remove the likelihood that any not-yet-proven assumptions about roots or irrational numbers will creep into the reasoning.
Table 1. Three Proofs that is Irrational
Students are drawn to different parts of the three proofs. Some prefer Proof B because it does not rely on the assumptionkids may call it a gimmickthat a and b have no common factors. This objection is a good occasion to discuss the "story" of how that assumption comes into proofs A and C. It is essential to establishing the contradiction later on in the proof, but how did the prover know it was needed? The answer is that they didnt and that it was put in place once the need was discovered (we have watched students develop this proof themselves and then stick in the condition in order to force the contradiction). If the authors of these proofs included details of their derivationsthe story of how they thought up the proofsthey would avoid the discomfort that the austere versions create. Proof C relies on a case-by-case analysis that the different ending digits cannot match. Again, despite the bluntness of its means, it seems to explain why cannot reduce to 2. This method becomes more elegant with fewer cases when we look at the final digit in a smaller base such as base 3. The point of the above discussion is not to have your students choose one "best" proof, but to have them weigh the pros and cons of each. We want them to discover that not everyone in the class has the same mathematical tastes. However, some criteria are more objective than others. For example, one important criterion is how easily a proof may be generalized to related problems. In the case of the three proofs in table 1, you may ask students to decide which extend readily to show that the roots of other integers (or all non-perfect squares) are irrational. We might also inquire why the same proof methods do not show that is irrational. Another objective criterion is the sophistication of the mathematics needed to support a proof. Proof A requires fewer lemmas than the other two. Despite students frequent preference for proof B, it relies on the comparatively "heavy machinery" of the fundamental theorem of arithmetic (positive integers have a unique prime factorization). Mathematicians often applaud a proof that uses more elementary methods, but, in this case, the elementary approach is not necessarily easier to understand. You can introduce the activity described above with other accessible theorems. Pythagorean Theorem and its Many Proofs (Bogomolny) and Pythagorean Theorem (Weisstein) provide several dozen different proofs of the Pythagorean Theorem. Make handouts of a variety of these proofs and have each student pick three to study. Which did they like best? Why? Do they prefer those that involved geometric dissections or algebraic calculations? Those that were shorter and skipped steps or those that explained each step carefully? Can the class provide the missing arguments for the less rigorous "proof without words" diagrams? Encourage them to see the particular appeal of each proof. PRACTICE PROOF ACTIVITIESEarlier in this section, we suggested that students proof experiences are most effective when they emerge organically from student investigations. Nevertheless, for a number of reasons, there is value to students practicing creating proofs as well. For example, practice helps students hone techniques and instincts that they can use in work that is more open-ended. Additionally, some of the reasons given in Why Do We Prove? remain relevant even if we are told what to prove. When students share their proofs with each other, they get further practice reading proofs and comparing the different types of reasoning used to justify theorems. The transfer of understandings derived from practice problems is particularly likely if the practice is not overly structured. Proof exercises not connected to the study of a particular content area (e.g., triangle congruence or induction) force students to think about which of their many skills might help solve the problem. For each one, they might ask, "Should we introduce a variable? Will an indirect proof work?" This way, they are practicing methods and making thoughtful choices. If students do not a have a clear reason for choosing one approach over another, point out to them they do not have to be paralyzed in the face of this uncertainty. They can just start experimenting with different representations of the information and different proof methods until one of them works. Students first proofs are rarely polished or precise. They may over-emphasize one point while omitting an important consideration (see, for example, the student proof below). Without experience devising symbolic representations of their ideas, students representations are often inefficient or unhelpful. For example, a student working on the Amida Kuji project was asked by her teacher to clarify and strengthen an English argument using symbols. She devised substitutes for her words ("hi is a horizontal rung"), but the symbols had no value facilitating her computations and led to an argument that was more difficult to read. The proof had that "mathy" look to it, but, until the student had a better grasp of the underlying structures of the problem and their properties, she was in no position to develop a useful system of symbols. When we respond to students early proofs, our emphasis should be on the proofs clarity and persuasiveness. Their arguments may take many forms: paragraphs, calculations, diagrams, lists of claims. Any of these may be appropriate. We want to help them identify any assumptions or connections that they have left unstated, but we also have to judge how convincing and complete a line of reasoning has to be. Can steps that are obvious be skipped? To whom must they be obvious? Does a proof have to persuade a peer, a teacher, or a less knowledgeable mathematics student? We want to help younger students develop rigor without bludgeoning them on specifics that they may not be ready to attend to. Can students adopt the attitude of the textbook favorite, "we will leave it as an exercise for the reader to verify that " ? Fine readings on this topic include "I would consider the following to be a proof " and "Types of Students Justifications" in the NCTM Focus Issue on the Concept of Proof (1998). One answer to the above questions is that a students classmates should be able to understand and explain their proofs. If classmates are confused, they should explain where they lose the thread of an argument or what they think a sentence means so that the author can rewrite her proof to address these confusions. Once a proof has passed the peer test, we can note additional possible refinements that will help our students develop greater sophistication in their thinking and presentation over time. Try to focus on certain areas at a time and expand students rigor and use of symbols incrementally. We try to emphasize proper vocabulary first (see Definitions). The development of original and effective symbolic representations tends to take more time to appear. Be aware of "hand-waving" in proofs. Hand-waving is what a magician does to distract his audience from a maneuver that he does not want them to notice. For mathematicians, hand-waving is a, perhaps unintentional, misdirection during a questionable part of an argument. The written equivalent often involves the words "must" or "could" (e.g., "the point must be in the circle " ) without justification of the claimed imperative. Sometimes we need to note, but accept, a bit of hand-waving because a gap is beyond a students ability to fill. Many of the proof exercises provided here are more suitable for high school than middle school students. The whole class settings described below as well as practice problems 1, 4, 6, 7, 15, and 16 are likely to work with middle school students (although others may also be useful depending on the students background). Particularly with younger students, doing proof within explorations that help them see how a proof evolves naturally from questions and observations is more valuable than exercises that ask them to prove someone elses claims. When we are given a "to prove", we have to go back and explore the setting anyway in order to develop some intuition about the problem. Older students, who have a broader array of techniques from which to choose, are more likely to benefit from proof exercises. Once a class has proven theorems in the context of longer research explorations, you can use the practice problems as a shorter activity. Choose a few problems to put on a handout and distribute them to each student. Give the students a few days to work on the problems and then discuss and compare their discoveries and proofs. Based on these discussions and peer responses, each student can then rewrite one of their proofs to produce a polished solution. Kids need more experience trying to prove or disprove claims without knowing the outcome ahead of time. In genuine mathematical work, we pose a conjecture, but we are not sure that it is true until we have a proof or false until we have a counterexample. The practice problems below sometimes call attention to this indeterminate status by asking students to "prove or disprove" the claim. Some of them actually ask for a proof even though the claim is false. We include these red herrings because students are often overly confident about their own conjectures and need to develop greater skepticism. Students should not consider this feature foul play, but good training in skeptical thinking. We are often taught to see texts as unerring authorities, but even the most prestigious journals of mathematics and science occasionally publish results that turn out to be false or incomplete. We have found that students are delighted when, and will put great effort into proving that, a textbook or teacher is wrong. We are simply building in that opportunity. Once a false statement has captured students attentions, challenge them to turn it into a true claim. Can they identify a significant set of cases for which the claim is true (e.g., by changing the domain to remove the counterexamples, see problem 10)? Can they generalize the claim (e.g., problem 7 is false, but the more general claim for two relatively prime divisors is true)? A setting for whole class practiceThe related games Yucky Chocolate and Chomp are good settings for early work with proof. These games are effective with both middle and high school classes. Both games begin with an n-by-m array of chocolate squares (n not necessarily different from m) in which the top left square of chocolate has become moldy. Rules for the game of Yucky Chocolate: On each turn in the game of Yucky Chocolate, a player chooses to break the bar of chocolate along a horizontal or vertical line. These breaks must be between the rows of squares (figure 3). The rectangle that is broken off is "eaten" by that player. The game continues with the rectangle that includes the yucky square. You can introduce this game with real chocolate, but the incentive to break off large pieces for consumption may overwhelm any other strategic thinking. Players take turns until one player, the loser, is left with just the yucky piece to eat. Figure 3. A horizontal break in the game of Yucky Chocolate leaves a 2 by 4 board Introduce your class to the rules of the game and then have them pair off to play several rounds starting with a 4 by 6 board. They can play the game on graph paper, mark off the starting size of the chocolate bar, and then shade in eaten portions each turn. After a few rounds of play, students will start to notice winning end-game strategies. In one fifth-grade class, the students observed that when a player faced a 2-by-2 board, they always lost. Given that observation, additional play led them to see why a 3-by-3 board was also a losing position. They were able to turn these conjectures into theorems with simple case-by-case analyses. For the 3-by-3 board, the symmetry of the situation meant that there were really only two distinct moves possible (leaving a 2-by-3 or 1-by-3 board). Each of these moves gave the other player a winning move (reducing the board to a 1-by-1 or 2-by-2 case). After the class realized that the smaller square positions were losers, some students took the inductive leap to conjecture that all n-by-n boards represented losing positions. One girl, who had never studied proof by induction, excitedly began explaining how each larger square array could be turned into the next smaller one and that she could always force the game down to the proven losing square positions. She had an intuitive understanding of the validity of an inductive argument. She then stopped and realized that her opponent might not oblige her by carving off just one column and that she did not know how big the next board might be. She had cast doubt on the reasoning of her own argument. She was facing another form of inductive proof in which one builds not just from the next smallest case but all smaller cases. After a while, the class was able to show that regardless of the move that an opponent facing an n-by-n board takes, there was always a symmetrical move that made a smaller square board. Therefore, they could inexorably force a win. This argument made it possible for a full analysis of the games that led to a win for the first player (n m) and those that should always be won by the second player. Once students have a complete understanding of Yucky Chocolate, the game provides a nice opportunity for practicing problem posing. Ask the students to each develop one or more variations of the game. What characteristics can they change? Does the game remain interesting? Does it become more complicated? Do they have to change any rules to make it still make sense? Some of the changes that students have explored include moving the location of the moldy square, making the problem three-dimensional, changing the number of players, or playing with a triangular grid of chocolate. Rules for the game of Chomp: The game of Chomp starts with the same slightly moldy chocolate bar, only the players take turns biting the chocolate bar with a right-angled mouth. These bites remove a chosen square and all remaining squares below and/or to the right of that square (figure 4. See Joyce for further examples). Figure 4. Two turns in a game of Chomp These bites can leave behind boards with complicated shapes that make it difficult to analyze which player should win for a given starting board. Student investigations can identify many sets of initial configurations (e.g., the 2-by-n or n-by-n cases) where a winning strategy can be determined and a proof produced (see Keeley And Zeilberger). Zeilbergers Three-Rowed Chomp provides an elegant existence proof that the first player in a game must always have a winning strategy. Being an existence proof, it provides no hint at how the winning strategy might be found. See Gardner, Joyce, Keeley, and Stewart for more on the game of Chomp. The article by Stewart also discusses Yucky Chocolate. The Keeley article provides a lovely discussion of one classs definitions, conjectures, and theorems about the game of Chomp. Other Whole Class Problems and Resources
Rather than work through an exploration of each quadrilateral type sequentially, provide the class with standard definitions of each and have them draw (or construct) examples of each. Point out that each shape has a number of properties that are a consequence of their definition (e.g., reflection symmetry) that are not explicitly part of their definition. The handout Quadrilateral Properties will encourage a systematic exploration of these properties, each of which can be turned into a conjecture (e.g., "if the diagonals of a quadrilateral are congruent and bisect each other, then the figure is a rectangle" or "if a figure is a rhombus then it is a parallelogram") that students can try to prove (see writing conjectures for more on this topic). For each proof, they should produce a labeled diagram and a statement of the given information in terms of those labels. The given information should be strictly limited to that provided in the definitions of the terms in the premise of the conjecture. Once students have generated a number of proofs using the above activity, they can move on to explore the properties of the perpendicular bisectors or midpoints of the sides or the bisectors of the angles of the different quadrilaterals. They might even explore dividing the angles or sides into multiple equal parts (n-secting them). Dynamic geometry programs, such as Geometers Sketchpad, are particularly helpful in creating clear diagrams and taking accurate measurements that aid students in making discoveries with these settings. Proof Without WordsDiagrams play a complex role in mathematics. Many mathematicians think about even quite abstract ideas using visual images. Algebraic ideas often have natural geometric representations. We will often try to draw a picture of a problem that we are exploring because the image conveys a great deal of information organized according to a set of meaningful relationships. However, pictures do have limitations that students need to appreciate. In trying to gain insight from a diagram, we are restricted by its static nature. It shows us just one instance. The appeal of dynamic programs such as Geometers Sketchpad is, in part, that they allow us to quickly view multiple examples. Diagrams can mislead us if they are not created with precision and even accurate pictures may possess properties that are not typical of all cases. While diagrams may persuade and inform us, they do not constitute proofs. As with other types of examples, a picture may look convincing simply because we have not yet imagined how to construct a counterexample. We want to help our students learn how to use diagrams as tools for furthering their investigations and how to extract information from them. As they work on problems, we can prompt them to consider whether a graph or other visual representation can be generated and studied. When they are reading other peoples proofs, encourage them to study all labels and features and to connect those details to the text and symbolic statements in the discussionto see how they illuminate that discussion and whether they serve as an effective visual counterpart. Students can also get practice interpreting diagrams by studying "proofs without words." These "proofs" are pictures that their author considers so enlightening that they readily convince us that we can dependably generalize the pattern to all cases. Depending on how wordless a proof without words is (and some do have the occasional accompanying text), the pictures can take some effort to analyze. Effective pictures can be the inspiration for a more formal proof. Winicki-Landman (1998, p. 724) cautions that some students may respond negatively to proofs without words if they feel that they will have to come up with such elegant diagrams themselves. Be sure to emphasize the value of working with diagrams and the purpose of these activities. When "proof pictures" do not even have variable labels, encourage students to choose variables for the different quantities in the picture and to see what the pictures tell them about those variables. See Proof without words (Bogomolny) for further discussion and additional examples. Some Problems
Their Solutions
Twenty Practice problemsSolutions to these problems are provided below as a way for you to gauge the difficulty of the problems and to determine their appropriateness for your class. Do not expect or require the students solutions to match the ones provided here. Alternatively, try to work on the problems yourself and with your students so that you can model how you think about analyzing problems and constructing proofs. After you and the students have your own results, you can use the solutions to make interesting comparisons. As the class discusses the different solutions to the problems, be sure to highlight the different methods (e.g., induction, proof by contradiction, case-by-case analysis) that they used. This emphasis will reinforce the message that there are common techniques that are often effective. Once students have worked through some initial proofs, it is good to anticipate the frustrations and barriers that they will face as they attempt longer and harder problems. The NOVA (1997) video The Proof, which details Andrew Wiles work on Fermats Last Theorem, provides a motivational lesson that also tells students about one of the great mathematics accomplishments of the past century. Although Wiles proof is intimidating in its inaccessibility, his personal struggle and emotional attachment to the task are inspiring. After watching the video about his seven-year journey, students have a greater appreciation for the role that persistence plays in successful endeavors. The article Ten lessons from the proof of Fermats Last Theorem (Kahan) can be used as a teachers guide for a follow-up discussion. See Student and Teacher Affect for a further discussion of motivational considerations. Note: Some of these problems may ask you to prove claims that are not true. Be sure to approach each with some skepticismtest the claims and make sure that a proof attempt is called for. If you disprove a statement, try to salvage some part of the claim by changing a condition.
Sample solutions to the Practice Problems
Bogomolny, Alexander (2001). Pythagorean triples. Cut-the-knot. Available online at http://www.cut-the-knot.com/pythagoras/pythTriple.html. Bogomolny, Alexander (2001). Infinitude of primes. Cut-the-knot. Available online at http://www.cut-the-knot.com/proofs/primes.html. Bogomolny, Alexander (2001). Non-Euclidean geometries, models. Cut-the-knot. Available online at http://www.cut-the-knot.com/triangle/pythpar/Model.html. Bogomolny, Alexander (2001). Integer iterations on a circle. Cut-the-knot. Available online at http://www.cut-the-knot.com/SimpleGames/IntIter.html Bogomolny, Alexander (2001). Proof without words. Cut-the-knot. Available online at http://www.cut-the-knot.com/ctk/pww.shtml. Bogomolny, Alexander (2001). Proofs in Mathematics. Cut-the-knot. Available online at http://www.cut-the-knot.com/proofs/index.html Berlignhoff, William, Clifford Slover, & Eric Wood (1998). Math connections. Armonk, N.Y.: Its About Time, Inc. Brown, Stephen & Walters, Marion (1983). The art of problem posing. Hillsdale, NJ: Lawrence Erlbaum Associates. Carmony, Lowell (1979, January). Odd pie fights. Mathematics Teacher, 61-64. Chaitin, G. J. The Berry paradox. Available online at http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unm2.html. Davis, Philip and Reuben Hersh (1981). The mathematical experience. Boston, Massachusetts: Houghton Mifflin Company: Deligne, Pierre (1977, 305(3)). Lecture notes in mathematics, 584. Springer Verlag. Erickson, Martin & Joe Flowers (1999). Principles of mathematical problem solving. New Jersey, USA: Prentice Hall Flores, Alfinio (2000, March). Mathematics without words. The College Mathematics Journal, 106. Focus Issue on The Concept of Proof (1998, November). Mathematics
Teacher. Available from NCTM at http://poweredge.nctm.org/nctm/itempg.icl?secid=1&subsecid=12&orderidentifier=
Gardner, Martin (1986). Knotted doughnuts and other mathematical recreations. New York, N.Y.: W. H. Freeman and Company, 109-122. Hoffman, Paul (1998). The man who loved only numbers. New York, New York: Hyperion. Horgan, John (1996, April). The not so enormous theorem. Scientific American. Joyce, Helen (2001, March). Chomp. Available on-line at http://plus.maths.org/issue14/xfile/. Kahan, Jeremy (1999, September). Ten lessons from the proof of Fermats Last Theorem. Mathematics Teacher, 530-531. Keeley, Robert J (1986, October). Chompan introduction to definitions, conjectures, and theorems. Mathematics Teacher, 516-519. Knott, Ron (2000) Easier Fibonacci puzzles. Available online at http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibpuzzles.html. Lee, Carl (2002). Axiomatic Systems. Available for download at ../../../handbook/teacher/Proof/AxiomaticSystems.pdf. MacTutor History of Mathematics Archive (1996). The four colour theorem. Available online at http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/The_four_colour_theorem.html. MacTutor History of Mathematics Archive (1996). Fermats last theorem. Available online at http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Fermat's_last_theorem.html. MegaMathematics (2002). Algorithms and ice cream for all. Available online at http://www.cs.uidaho.edu/~casey931/mega-math/workbk/dom/dom.html. Nelson, Roger (1993). Proof without words. Washington, D.C.: The Mathematical Association of America. NOVA (1997). The proof. WGBH/PBS. See http://www.pbs.org/wgbh/nova/proof/ for more information and http://www.pbs.org/wgbh/shop/novavidedu06detect.html#proof to order. Peterson, Ivars (1996, December 23). Prime theorem of the century. MAA online: MathTrek. Available online at http://www.maa.org/mathland/mathland_12_23.html. Peterson, Ivars (1998, February 23). The limits of mathematics. MAA online: MathTrek. Available online at http://www.maa.org/mathland/mathtrek_2_23_98.html. Platonic Realms Interactive Mathematics Encyclopedia (PRIME). Gödels theorems. Available online at http://www.mathacademy.com/pr/prime/articles/godel/index.asp. Schoenfeld, Alan (1992). Learning to think mathematically: problem solving, metacognition, and sense-making in mathematics. Available online at http://www-gse.berkeley.edu/faculty/aschoenfeld/LearningToThink/Learning_to_think_Math06.html#Heading18. Read from this point in the essay to the end. Schoenfeld, Alan (1994, 13(1)). Do we need proof in school mathematics? in What do we know about mathematics curricula? Journal of Mathematical Behavior, 55-80. Available online at http://www-gse.berkeley.edu/Faculty/aschoenfeld/WhatDoWeKnow/What_Do_we_know 02.html#Heading4. Stewart, Ian (1998, October). Mathematical recreations: playing with chocolate. Scientific American, 122-124. Weisstein, Eric (2002). Perfect Number. Eric Weissteins World of Mathematics. Available online at http://mathworld.wolfram.com/PerfectNumber.html. Weisstein, Eric (2002). Pythagorean Theorem. Eric Weissteins World of Mathematics. Available online at http://mathworld.wolfram.com/PythagoreanTheorem.html. Weyl, Hermann(1932). Unterrichtsblätter für Mathematik und Naturwissenschaften, 38, 177-188. Translation by Abe Shenitzer (1995, August-September) appeared in The American Mathematical Monthly, 102:7, 646. Quote available online at http://www-groups.dcs.st-and.ac.uk/~history/Quotations/Weyl.html. Winicki-Landman, Greisy (1998, November). On proofs and their performance as works of art. Mathematics Teacher, 722-725 Zeilberger, Doron (2002). Three-rowed Chomp. Available online at http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/chomp.pdf. Zeitz, Paul (1999). The art and craft of problem solving. John Wiley and Sons: New York. |
Translations of mathematical formulas for web display were created by tex4ht. |