Learning to Prove: A Taxonomy of Objectives Vincenzo Liberatore Department of Computer Science, Rutgers University, Hill Center, Busch Campus, New Brunswick, NJ 08903. E-mail: liberato@paul.rutgers.edu Abstract We consider the educational objective of learning how to prove a statement in a mathematically rigorous way and we break down this educational objective into several partial objectives following the standard taxonomy of [Bloom56]. Three advantages stem from this approach: first, the partial objectives are more manageable in the process of curriculum development; second, it is easier to individuate the teaching strategies that are most effective for each educational objective; and, finally, we discover some objec- tives that are often neglected, but are in fact surprisingly leg- itimate - these include the rote learning of proofs, the abili- ty of interpreting mathematical statements, the analysis of proofs and proof techniques, and the ability of reading the current literature. 1. Introduction A most important educational objective for most students in the technical and scientific disciplines is to grasp the method of proving a statement mathematically and rigorously; in this sense, mathematical proofs are contrasted with experimental results and with assertions by intuition. In practice, most students at the undergraduate level are not ex- posed to operational techniques of mathematical proving. In most courses, proofs are expounded by the instructor, but the students are not required to know those proofs, to modify them, or to create new proofs. The principal educational objective is the application of the theorems and, as far as mathematical reasoning is concerned, the sole outcome of this method is the intuition that it is possible in principle to prove a statement mathemati- cally. The main assumptions of this paper are that the ability to prove a statement mathematically can be learned just like any other ability, and that this broad objective can be broken down into partial objectives exactly like any other educational objec- tive. The emphasis of this paper is on the general logical thinking necessary to prove mathematical statements; the applica- tion to mathematical logic is a particular instance of this methods. The educational objective "to learn how to devise a convincing mathematical proof" is extremely broad; for this reason, it only points out a general policy and a criterion for evaluating curri- cula. This broad objective should be more accurately defined if we desire to determine the specifical goals to be achieved in a course and if we wish to define more clearly the outcomes of the educational process. In this paper, we attempt to break down this objective in partial objectives following the standard tax- onomy of [Bloom56]. Throughout the paper we will recall defini- tions and observations from [Bloom56] so as to make our presenta- tion accessible to a wider audience. However, we briefly recapi- tulate the main points of the taxonomy in the remainder of this section. The taxonomy "is intended to provide for classification of the goals of our educational system" [Bloom56], and for convenience it is shortly sketched in the table below. Our definitions are by necessity very short, and our examples are far from being exhaus- tive; we refer to [Bloom56a] for more details. Objective Description Example - --------- ----------- ------- Knowledge recall knowing technical terms Comprehension translation, predicting continuation explanation, and of trends predicting consequences Application usage in new and apply science principles to concrete situations new situations Analysis the breakdown into distinguishing facts from constituent elements hypotheses Synthesis the putting together of mathematical discoveries elements so as to form a whole Evaluation judgements about the comparison of major theories value of learning Although this taxonomy is not a hierarchy of objectives, the ob- jectives reported later in the hierarchy will often be built on the achievement of previous educational objectives. Also, some taxonomy objectives are partly overlapping [Bloom56a]; we will observe an example of this phenomenon in the appendix. We remark that we do not make any recommendation about the development of a curriculum because curricula would have to take into account, in addition to the educational goals reported in this paper, also the information available about the students, and in particular issues regarding their present development, needs, and interests. However, we believe that in any mathemati- cal course a subset of the objectives below should be emphasized, the choice of the specific subset depending on the students' pro- file. 2. Knowledge The first educational objective that we examine pertains the ac- quisition of knowledge, that is, the development of the ability to recall information about proofs and proof techniques. Knowledge, as defined in the taxonomy, involves mainly the psychological processes of remembering; by contrast, the objec- tive examined in the following section will involve processes like relating, judging, and reorganizing. Knowledge is often neglected as an educational objective in the context of teaching mathematical reasoning. Nevertheless, knowledge can be deemed a legitimate educational goal as it is a prerequisite to all other advanced educational objectives in mathematical reasoning. For example, knowledge of established proof techniques form a reper- toire of methods for attacking mathematical and non-mathematical problems. A very basic educational objective is the knowledge of proof ter- minology, classification, and methodology; words like theorem, lemma, corollary, proof, entailment, and contradiction are a sam- ple of crucial phrases and the methods these terms define are fundamental. In the category of knowledge, the objective that most educators would probably agree on is the acquisition of the major ideas and general schemes and patterns exploited in proofs. For example, a broad objective is the knowledge of the structure of a proof by induction. The generality of these objectives often causes great difficulty in learning because students are not familiar with the specific proofs that the general schemes intend to describe [Bloom56]. We therefore conjecture that more basic educational objectives should precede the learning of universal proof schemes. The preliminary objective we assume is the knowledge of specific proofs (objective 1.12 in [Bloom56]), which is to say that students should be able to recall some proofs in all their details. This objective demands that a list of proofs be given to the students, and that the students then be asked to repeat some of those proofs in a detailed and rigorous way. In passing, we remark that currently this objective is earnestly pursued in some Euro- pean universities where freshmen in Engineering departments have to memorize between 100 and 120 mathematical proofs for each one of their basic courses in Calculus and Algebra. We believe that a lighter version of such a requirement might be extremely useful in basic mathematical courses if accompanied by the simultaneous testing for the comprehension objectives that we will describe below. 3. Intellectual Abilities and Skills In no field is knowledge alone commonly regarded as the final educational objective. In this section, we examine the educa- tional objectives that aim at the development of intellectual abilities and skills. 3.1. Comprehension At this level, the student should be able to explain passages in the proofs, possibly paraphrasing them and giving examples, and, conversely, she should be able to extract a proof from a set of examples and rewrite arguments into a more compact form. She should be able to defend her exposition of a proof against criti- cal comments and to give examples of each proof passage. The student should be able to translate symbolic formulas into verbal form and vice versa. A very common problem for students is to determine what is exactly given by the hypothesis of a state- ment, and what exactly is required to be proven. In particular, an educational objective is to enable the student to translate the statement of a proposition into the mathematical entities whose existence is given or required. The student can sometimes accomplish this simply by replacing the definitions for the terms that appear in the proposition statement, but often she will have to examine the relationships among the given mathematical enti- ties. More complex educational objectives are impaired if the student is not able to determine what exactly is given in the hy- pothesis and what exactly has to be proven [Bloom56]. Moreover, the student should be able to grasp the sequence of implications and quantifications of the statement she has to prove. The student should be able to distinguish among warranted, unwar- ranted, or contradictory conclusions drawn from the premises. Test scores differentiating between "crude errors", "going beyond the premises", and "over-caution" could be especially useful in monitoring a student progress [Bloom56]. A student might sometimes come across a proof step that can be applied to situations of more general nature than the proof of a certain particular result. The student should be able to gen- eralize such passages to applications not strictly needed in the proof, but immediately obtainable, and she should be able to do so even if these applications are drawn from a domain different >from the one addressed by the proof. She should also be able to carry out a proof when the proof tech- nique to be used is suggested to her. Hints and directions need not be limited to suggestions for a good approach for solving the problem, but could also point out that some strategies are unpro- ductive [Gagne85]. The author has gained some experience in teaching a class that emphasizes among others the objectives listed in this section, and we believe that these objectives are not unrealistic for col- lege freshmen and sophomores. Moreover, we think that the stu- dents gained a better understanding of proof methodologies and we conclude that this method was generally successful. We will now describe the most critical problems that students found in the process of pursuing these objectives. A first difficulty is en- countered when students try to express an argument in a general verbal form; in particular, students tend to have problems when asked to justify a proof step with some general argument rather than by examples. Problems also arise when students have to jus- tify a proof passage by citing the correct previously known result. Another common difficulty is the comprehension of ques- tions that are phrased differently from those in previous assign- ments. All these problem sometimes confuse the students on what is required of them and special care has to devoted in formulat- ing questions that test the achievement of the comprehension ob- jectives. 3.2. Application In the taxonomy, the application objectives is the goal of apply- ing what the student has learned, but with the following remark: the major difference between the objective of comprehension and application is that now the student should be able to carry out a proof without being prompted to use any specific method, so that he will have to find a way to attack the problem on his own. The achievement of some of the educational objectives pointed out in section 2 and 3.1 is a necessary prerequisite of the application objectives [Gagne85]. Testing for the application objective requires some special at- tention. Tests consist of requiring the students to prove a mathematical statement; usually, these statements can be selected >from material unknown to the student or can be similar to a prob- lem known to the student, but with a new slant he is unlikely to have thought of. A test should also present the student with some preliminary questions to ascertain whether he has correctly understood the statement to be proven, and questions asking to state explicitly the chosen proof methodology. We now compare and contrast the teaching methodologies that are most effective for the objectives of knowledge and of applica- tion. Suitable methods for the presentation and the acquisition of knowledge are lectures, printed material, and the like; these methods are usually preferred because of their simplicity [Bloom56]. The most effective way to achieve the application ob- jectives is the method of guided discovery, that is, by proceed- ing a step at a time and demonstrating the consequences that a particular decision, method, or strategy would bring about [Kato- na67]. The methods of lecturing and guided discovery can be com- pared as follows. Lecturing, as we remarked above, is a perfect- ly suitable way to achieve objectives related solely with knowledge, but it was found that the pure demonstration of several solutions of similar problems is the least effective teaching method to pursue problem solving objectives. On the oth- er hand, guided discovery is the most effective teaching method in this situation. Finally, problem solving without assistance is often too difficult for many subjects [Katona67], and it is not recommended for pursuing application objectives. 3.3. Analysis At this level, the student should be able to identify and distin- guish conclusions from supporting statements, relevant from ex- traneous material, necessary steps from corollaries, factual from normative statements, logical fallacies in a proof, questionable term usages, unstated assumptions, and the purpose of a proof passage or a proposition. The student should also be able to re- late analogies and differences among proofs and proof techniques. She should also be able to identify the fundamental part of a proof from the technical details and grasp the structure of a proof. She should be able to outline the main points of a proof and correlate them. Finally, she should acquire facility in reading a well-structured paper, as for example those published in journals. 3.4. Synthesis An educational objective for this level is the ``ability to make mathematical discoveries and generalizations'' [Bloom56]. When synthesis is the main objective, the educational approach should be as non-direct and stimulating as possible, the reason being that at this level the greatest amount of intellectual growth should occur. In particular, the student should feel free from tension and from pressure to adopt a particular viewpoint, and should be free to set his own objectives [Bloom56]. 3.5. Evaluation At this level, the students should be able to judge the value, significance, and relevance of a proof. He should be able to sum- marizes proofs and whole lines of thought, to compare different proof techniques, and to discuss the application of proof methods. 4. Conclusions In this paper, we have given a detailed taxonomy of partial ob- jectives implied by the necessity of teaching how to prove a statement in a mathematically rigorous way. We found that some objectives are surprisingly legitimate and fall in established teaching methodologies --- these include the rote learning of proofs, the ability of interpreting mathematical statements, the analysis of proofs and proof techniques, and the ability of read- ing the current literature. We also discovered that different objectives require very different teaching methodology; in par- ticular, application and synthetic abilities cannot be effective- ly taught by lecture methods commonly used to pursue knowledge objectives. Acknowledgments We would like to thank Ann Yasuhara for many comments. References [Bloom5] Benjamin S. Bloom, editor. Taxonomy of Educational Objectives, volume 1. McKay, New York, 1956. [Gagne85] Robert M. Gagne'. The Conditions of Learning and Theory of Instruction. Holt, Rinehart and Winston, New York, 4th edition, 1985. [Katona67] George Katona. Organizing and Memorizing. Studies in the Psychology of Learning and Teaching. Hafner, New York, 1967. [Rosen95a] Kenneth H. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill, NY, third edition. [Rosen95b] Kenneth H. Rosen. Instructor's Resource Guide to Discrete Mathematics and Its Applications. McGraw-Hill, NY, third edition. Appendix: An Example One of the main conclusions of this paper is that the same topic could be presented in very different ways, depending on the in- tended educational objectives. In this section, we will illus- trate how the same theorem and proof can be approached in quite different ways according to the educational goals. In the first levels of the taxonomy, the educational approach is very well-defined, but, as we move on to subsequent objectives, the teaching strategy becomes less and less rigid, and in the more advanced levels, the approach is highly dependent on the context of instruction and on the students' reaction. Therefore, only the first four levels (knowledge through analysis) will be considered in this example, as it is much more difficult to con- fine the other levels in only one case study. We will use for our example the Pascal's identity and its proof. Although the proof is rather short, it is complicate enough to cause students' uneasiness [Rosen95b]. Also, Pascal's identity is a very important combinatorial equality, and its proof is the prototypical examples of a combinatorial proof. Usually Pascal's identity is introduced in a basic course in discrete mathematics or combinatorics after the sum and product rules, the definition of permutations, combinations, and binomial coefficients; we will assume that the students are familiar with all these concept. In the discussion of the proof we will use the following notation by now standard in combinatorics: [n] is the set {1, 2, ... , n} and C([n],k) is the collection of all subsets of [n] of size k. If the educational objective is the knowledge of the result and of the proof, then the instructor could expound the following ar- gument, adapted from [Rosen95a]. Theorem(Pascal's Identity) Let n and k be positive integers with n greater than or equal to k. Then C(n + 1,k) = C(n,k - 1) + C(n,k). Proof. Let S be a set containing n+1 elements, a in S, and T = S - - {a}. There are C(n + 1,k) subsets of S containing k elements. However, a subset of S with k elements either contains a together with k-1 elements of T, or contains k elements of T and does not contain a. Since there are C(n,k - 1) subsets of k - 1 elements of T, there are C(n,k - 1) subsets of k elements of S that con- tain a. And there are C(n,k) subsets of k elements of S that do not contain a, since there are C(n,k) subsets of k elements of T. Consequently, C(n + 1,k) = C(n,k - 1) + C(n,k). QED Then, in a test addressing the knowledge objective, the students will be required to repeat the proof as it is. The next level is the comprehension objectives. When the instructors wishes to test for the comprehension of the proof, he could for example ask the following questions: 1. List C([3],2), C([2],1) and C([2],2). Is it true that C([3],2) = C([2],1) U C([2],2)? Is it true that C(3,2) = C(2,1) U C(2,2)? 2. Recall that binomial coefficients count the number of subsets that can be extracted from a certain universe and that have a certain size. What does C(n,k-1) count in the proof of Pascal's identity? What does C(n,k) count? What does C(n+1,k) count? 3. How is a chosen among all elements of S? Why is it always possible to choose such an a? 4. Where is the sum principle used? How do we know that the sets are disjoint? 5. Where is the multiplication principle used? 6. What is wrong in the following argument: "The subsets of S of size k containing a are subsets of S and have k elements, so there are C(n+1,k) of them"? 7. Show that if n is a positive integer, then C(2n,2) = 2 C(n,2) + n^2 with a combinatorial argument. Some of the questions above deserve some comments. The two ques- tions about the sum and product rule belong to the comprehension objective as long as the verbal phrasing of the two principles has been emphasized. Otherwise, these questions are probably too hard for the comprehension objective and belong more properly to the analysis objective - as we noted in the introduction the tax- onomy objectives are sometimes partly overlapping. Analogously, question 7 would appear to belong to the application objective, but moves to the comprehension objective because of the similari- ty of the answer with the proof of Pascal's identity. Suppose now that Pascal's identity is exploited to pursue appli- cation objectives. We assume that students have already mastered the main ideas pertaining combinatorial proofs, as well as other proof techniques, and we want to use the method of guided discovery. Then, the student is given only the statement of the theorem, and asked to prove it, without suggesting that a com- binatorial proof is the best way to attack the problem. After a while, if the student did not obtain the solution, the best hint is probably to demonstrate that an algebraic proof leads quickly to quite complicate calculations. Now, the student has to come up with another proof method. If he tries induction, we could point out that singling out one element of S is in fact a form of induction. The student and the instructor then continue alter- nating ideas and hints, until the final proof is obtained. The interaction between the student and the instructor is usually su- perior to the lecturing method. The interactive method is also superior to the following common strategy: the instructor ex- pounds several combinatorial proof, and then asks the student to obtain an original combinatorial proof of a new result without assistance. Unfortunately, if the new proof differs significant- ly from those in the student's repertoire, many subjects will find the assignment too difficult; but if the proof closely fol- lows other known proofs, then the assignment does not qualify for the pursuit of application objectives. However, most students should be able to carry out proofs without assistance once the method of guided discovery has been used by the instructor. Eventually, at the analysis level, the students should be able for example to relate analogies and differences between the proof of Pascal's identity and other known combinatorial proofs, and the difference and analogies between the proof of Pascal's iden- tity and a proof by induction. ------- End of Forwarded Message