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

Contents

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 objectives that are often neglected, but are in fact surprisingly legitimate - these include the rote learning of proofs, the ability 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 exposed 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 mathematically. 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 application 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 curricula. 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 taxonomy of [Bloom56]. Throughout the paper we will recall definitions and observations from [Bloom56] so as to make our presentation accessible to a wider audience. However, we briefly recapitulate 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 exhaustive; we refer to [Bloom56] for more details.

Objective Description Example
Knowledge recall knowing technical terms
Comprehension translation, explanation, and predicting consequences predicting continuation of trends
Application usage in new and concrete situations apply science principles to new situations
Analysis the breakdown into constituent elements distinguishing facts from hypotheses
Synthesis the putting together of elements so as to form a whole mathematical discoveries
Evaluation judgements about the value of learning comparison of major theories

Although this taxonomy is not a hierarchy of objectives, the objectives reported later in the hierarchy will often be built on the achievement of previous educational objectives. Also, some taxonomy objectives are partly overlapping [Bloom56]; 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 mathematical course a subset of the objectives below should be emphasized, the choice of the specific subset depending on the students' profile.

2. Knowledge

The first educational objective that we examine pertains the acquisition 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 objective 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 repertoire of methods for attacking mathematical and non-mathematical problems.

A very basic educational objective is the knowledge of proof terminology, classification, and methodology; words like theorem, lemma, corollary, proof, entailment, and contradiction are a sample 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 European 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 educational 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 critical 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 statement, 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 entities. More complex educational objectives are impaired if the student is not able to determine what exactly is given in the hypothesis 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, unwarranted, 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 generalize 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 technique 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 unproductive [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 college freshmen and sophomores. Moreover, we think that the students 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 encountered 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 justify a proof passage by citing the correct previously known result. Another common difficulty is the comprehension of questions that are phrased differently from those in previous assignments. All these problem sometimes confuse the students on what is required of them and special care has to devoted in formulating questions that test the achievement of the comprehension objectives.

3.2. Application

In the taxonomy, the application objectives is the goal of applying 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 attention. 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 problem 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 application. 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 objectives is the method of guided discovery, that is, by proceeding a step at a time and demonstrating the consequences that a particular decision, method, or strategy would bring about [Katona67]. The methods of lecturing and guided discovery can be compared as follows.

Lecturing, as we remarked above, is a perfectly 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 other 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 distinguish conclusions from supporting statements, relevant from extraneous 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 relate 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 summarizes 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 objectives 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 reading the current literature. We also discovered that different objectives require very different teaching methodology; in particular, application and synthetic abilities cannot be effectively taught by lecture methods commonly used to pursue knowledge objectives.

Acknowledgments. We would like to thank Ann Yasuhara for many comments.

References

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 intended educational objectives. In this section, we will illustrate 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 confine 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 argument, 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 contain 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 questions 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 taxonomy 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 similarity of the answer with the proof of Pascal's identity.

Suppose now that Pascal's identity is exploited to pursue application 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 combinatorial 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 alternating ideas and hints, until the final proof is obtained. The interaction between the student and the instructor is usually superior to the lecturing method.

The interactive method is also superior to the following common strategy: the instructor expounds 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 significantly from those in the student's repertoire, many subjects will find the assignment too difficult; but if the proof closely follows 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 identity and a proof by induction.

------- End of Forwarded Message