On the analysis of indirect proofs: contradiction and contraposition.
In the 17th century, proofs by contradiction became the focus of attention of philosophers and mathematicians, and the status and dignity of this method of proof came into question (Mancosu, 1991, p. 15). The debate centred around the traditional Aristotelian position that only causality could be the base of true scientific knowledge. In particular, according to this traditional position, a mathematical proof must proceed from the cause to the effect. Starting from false assumptions a proof by contradiction could not reveal the cause. As Mancosu (1996, p. 26) writes: "There was thus a consensus on the part of these scholars that proofs by contradiction were inferior to direct proofs on account of their lack of causality."
More recently, in the 20th century, the intuitionists went further and came to regard proof by contradiction as an invalid method of reasoning. In the classical approach the existence of an object can be proved by refuting its non-existence. To the intuitionist this is not acceptable. Led by the Dutch philosopher and mathematician L. E. J. Brouwer the intuitionists reject the law of excluded middle and only accept constructive proofs as valid proofs.
Despite all its past criticism and even rejection by some members of the mathematical community, the majority of today's mathematicians would agree with Rivaltus' position: "Proofs by contradiction have the same dignity as direct proofs because, even if they do not give us the cause of why a certain affection is to be predicated on the subject, they nonetheless give us a reason by which we know that a state of affairs holds" (cited in Mancosu, 1991, p. 34).
Nowadays, proof has been assigned a more prominent place in the mathematics curriculum at all levels. As Hanna and de Villiers (2008, p. 329) write: "The recent National Council of Teachers of Mathematics (NCTM) Principles and Standards document and several other mathematics curricular documents have elevated the status of proof in school mathematics in several educational jurisdictions around the world."
This renewed emphasis on proof and proving in mathematics education means that "mathematics educators face a significant task in getting students to understand the roles of reasoning and proving in mathematics" (Hanna & de Villiers, 2008, p. 329). More specifically, Hanna and de Villiers are challenging educators "to foster the use of proof as a method to certify not only that something is true, but also why it is true." (p. 330). The aim of the paper is to describe a general model of proof by contradiction. The misconceptions that seem to exist between proof by contradiction and proof by contraposition are clarified through the examination of their similarities and differences. More generally we shed some light on the specific details and peculiarities of the indirect proof structure, some of which are often left unattended whilst studying and practising proof techniques. We expect the paper to be of interest to undergraduate students and their university teachers as well as anyone interested in indirect proofs.
Description of a general model
We now investigate the theoretical foundations of proof by contradiction. This method of proof is an application of the rule of logical reasoning known as modus tollens. According to this rule, a proposition is proved by showing that its falseness leads to unacceptable consequences. Wishing to prove a statement p, one first assumes its negation [logical not]p to be true. One then goes on to show that [logical not]p implies q, where q is already known to be false. By this argument, [logical not]p must be false and it follows logically that its negation, the original proposition p must be true. Goubault-Larrecq and Mackie (1997, p. 4) give a simple example to illustrate modus tollens. Suppose we know the following two facts to be true: "If it is raining then I am inside", and "I am outside". From these two facts we can readily deduce that it is not raining. More formally, modus tollens can be stated as:
1. p [right arrow] q (if p then q)
2. [logical not]q (not q)
3. [therefore] [logical not]p
For completeness we briefly mention here another commonly used rule of reasoning known as modus ponens, which can be formally stated as:
1. p [right arrow] q (if p then q)
3. [therefore] q
Such rules of reasoning are not part of mathematics itself. Rather, they stand above the subject matter to which they are applied.
To reiterate, the aim of a proof by contradiction is essentially to contradict one of our assumptions. If the aim is achieved then, as a consequence of modus tollens, the original statement must be true. In Figure 1 below we propose a general model for proof by contradiction.
The very first step--assuming the opposite--can, in many cases, be a stumbling block for students. In his 1979 study, Williams (cited in Thompson, 1996) presented students with a number of items dealing with indirect proof. Asked to evaluate a proof that 1 [not equal to] 0, many students did not view the argument as valid, owing to the fact that the initial assumption 1 = 0 is false. Obviously this difficulty considerably hindered students' ability to use indirect proof effectively as many students appeared unwilling to argue from an hypothesis they saw as untrue (p. 478).
In general, a mathematical statement may contain any number of logical connectives--and, or, if-then--as well as the two quantifiers--for all, there exists. Many researchers (Epp, 1998; Lin et al., 2003, Thompson, 1996) report that, formulating the opposite of such statements is a difficult task for most students. As Epp (1998, p. 711) states: "One of the most serious difficulties that students have in actually constructing proofs by contradiction on their own is in supposing the wrong thing". This first step is indeed crucial. Thompson (1996, p. 476) adds, "If students have difficulty writing a negation, they have difficulties at the onset".
The 'black box' is truly the heart of the proof. It is usually a direct argument which proceeds from our (false) assumptions. What is in the box is utterly context dependent. Even for the simplest cases, the logical steps to be taken may be far from obvious to the novice and require much insight. As Barnard and Tall (1997, p. 42) explain: "Mathematical proof introduces a form of linkage different from the familiar routines of elementary arithmetic and algebra. In addition to carrying out sequential procedures in which each action cues the next, mathematical proof often requires the synthesis of several cognitive links to derive a new synthetic connection."
Their investigation into students' difficulties in proving the irrationality of the number [square root of 2] found that none of the students new to the proof were able to spontaneously link the algebraic statement [a.sup.2] = 2[b.sup.2] to the verbal representation "[a.sup.2] is even" (p. 44).
In a proof by contradiction, the aim is not always clear. We do want to arrive at a contradiction, but where is that contradiction to be found? Certainly, contradicting one of our assumptions will achieve the desired aim but the contradiction is not always this apparent. Indeed, rather than contradicting our assumption, the contradiction may take the form of a mathematical fact we know to be false or it may even emerge out of our own construction produced during the proof.
Proof by contradiction versus proof by contraposition
This part of the paper explores the differences and similarities that exist between proof by contraposition and proof by contradiction. The literature refers to both methods as indirect methods of proof. We will keep with this terminology in the paper. Both methods are closely related. In fact, the two methods are so closely related that they are sometime confused and so their differences and similarities are worthwhile exploring and clarifying. For example, Antonini and Mariotti (2008, p. 402) write: "In Italy, in general, mathematicians and teachers call 'proof by contradiction' ... both proof by contraposition and proof by contradiction." This confused state of affairs extends well beyond Italy. In the United States, many textbooks fail to clearly distinguish between these two types of proof. Epp's Discrete Mathematics with Applications (2011) is an exception and she contends that proof by contraposition applies only to "a specific class of statements--those that are universal and conditional" (p. 204).
To proceed further we need to provide more details on both types of statements. A universal statement is a statement about all the elements of a given set. "All humans are mortal" is an example of a universal statement. A conditional statement is a statement of the form "if p then q", with the two propositions p and q referred to as the hypothesis and the conclusion respectively. In logic conditional statements are known as implications and may be written as "p implies q" (p [right arrow] q in symbols).
Proof by contraposition
Proof by contraposition rests on the fact that an implication p [right arrow] q and its contrapositive [logical not]p [right arrow] [logical not]q (not q implies not p) are two logically equivalent statements. In this method of proof, there is no contradiction to be found. Rather our aim is to show, usually through a direct argument, that the contrapositive statement is true. By logical equivalence this automatically assures us that the implication is also true. In a proof by contraposition both the starting point and the aim are clear: assume that [logical not]q is true and show that it logically leads to [logical not]p. To illustrate, below is an example of a proof by contraposition.
Let x be an integer. Prove that if [x.sup.2] is even, then so is x.
Formally the statement can be written as
[for all]x [member of] Z p [right arrow] q
where p and q are defined as "[x.sup.2] is even" and "x is even" respectively. Negating the two propositions, the statement we want to prove has the form
[for all]x [member of] Z [logical not]p [right arrow] [logical not]q
where [logical not]p and [logical not]q are now "[x.sup.2] is odd" and "x is odd" respectively. Thus, we are trying to show that, given any odd integer, its square is also odd. By definition of an odd number our starting point is therefore x = 2k + 1, k [member of] Z and we proceed this way:
[x.sup.2] = [(2k +1).sup.2] = 4[k.sup.2] + 4k + 1 = 2(2[k.sup.2] + 2k) + 1
[x.sup.2] = 2n + 1, n [member of] Z
We have proved that the square of an odd number is odd. In fact, by logical equivalence we have also proved Example 1. We note that Proof 1 can be regarded as a special case of the more general statement that the product of two odd numbers is odd.
Proof by contradiction
We now turn our attention to the other method, the proof by contradiction. As previously stated, in general, to prove a statement by contradiction, we assume that statement to be false and we show that the logical consequences of our assumptions lead to a contradiction or an impossibility. For example, to prove that there is an infinite number of primes we assume from the onset that number to be finite. Now, we are in a position to examine the main difference between the two methods of proof. In the context of implications a proof by contradiction does not simply assume the conclusion to be false. Rather it assumes the entire statement to be false. Negating the entire statement has two consequences:
1. The universal statement becomes an existential statement.
2. The conditional statement becomes a conjunction. In particular, the negation of p [right arrow] q is the [conjunction] p [conjunction] [logical not]q (p and not q).
The logical steps shown below provide a justification for the logical equivalence between [logical not](p [right arrow] q) and p [conjunction] [logical not]q.
[logical not](p [right arrow] q) [equivalent to] [logical not] ([logical not]p [disjunction] q) implication law
[equivalent to] [logical not]([logical not]p [conjunction] [logical not]q de Morgan's law
[equivalent to] p [conjunction] [logical not]q double negation law
To illustrate the difference between the two methods we revisit Example 1 here. We prove by contradiction that for any integer x if [x.sup.2] is even then so is x. As explained previously, Example 1 has the form
[for all] x [member of] Z p [right arrow] q
where p and q are defined as "[x.sup.2] is even" and "x is even" respectively. Now we need to assume both p and [logical not]q to be true as our starting point. This means that we assume both "x is odd" and "[x.sup.2] is even" to be true. Formally, the statement we prove can be seen as
[there exists] x [member of] : p [conjunction] [logical not]q lead to a contradiction.
Essentially we are trying to show that we cannot find an odd integer whose square is even and our starting point can now be any of the above two assumptions. Choosing "x is odd" we proceed along the same lines as the proof by contraposition.
[x.sup.2] = [(2k + 1).sup.2] = 4[k.sup.2] + 4k + 1 = 2(2[k.sup.2] + 2k) + 1
[x.sup.2] = 2n + 1, n [member of] Z
The result "[x.sup.2] is odd" contradicts the other assumption "[x.sup.2] is even". This completes the proof. We note, whilst it may be possible to start the proof with the assumption "[x.sup.2] is even", that approach will change the proof to the direct mode, which is not considered in the paper. According to Epp (2011), "... any statement that can be proved by contraposition can be proved by contradiction. But the converse is not true. Statements such as '[square root of 2] is irrational' can be proved by contradiction but not by contraposition" (p. 204).
Indeed, "[square root of 2] is irrational" is a single proposition which cannot be written as a conditional statement since such statements require at least two propositions. Some conditional statements may be proved by contradiction but not by contraposition. This is especially the case when the hypothesis contains more than one proposition. Consider for instance the following example.
Let a, b and c be three integers. Prove that if c divides a + c but c does not divide a then c does not divide b.
Symbolically, the statement can be written as
[for all] (a, b, c) [member of] [Z.sup.3] (c | a + b) a (c [??] a) [right arrow] c [??] b
A proof by contradiction assumes the following three propositions to be true.
Schematically, the proof can be seen as
[there exists](a, b, c) [member of] [Z.sup.3]: [p.sub.1] [conjunction] [p.sub.2] [conjunction] [logical not]q lead to a contradiction.
We now show that, working from the first and third propositions, namely [p.sub.1] and [logical not]q, a few steps lead to a contradiction. Indeed, the first proposition means a + b = [k.sub.1]c, the third b = [k.sub.2]c with [k.sub.1], [k.sub.2] [member of] Z. It follows by substitution
a + [k.sub.2]c = [k.sub.1]c
a = ([k.sub.1] - [k.sub.2])c
a = [k.sub.3]c where [k.sub.3] = [k.sub.1] - [k.sub.2]
The difference of two integers is an integer thus [k.sub.3] [member of] Z, and we have shown that c divides a, contradicting the second proposition [p.sub.2]. The proof is complete.
In fact, an attempt at a proof by contraposition quickly leads to an impasse since we only have a single assumption to work with--namely c divides b. Knowing nothing of the divisibility of a (or a + b) by c, no further progress is possible.
Further examples of proof by contradiction
Besides number theory proof by contradiction may be applied in many areas including geometry, linear algebra and calculus. As previously mentioned, the contradiction we are looking for may be on our original assumption or it may arise from our own construction produced during the proof. The calculus example below falls into the latter category, where the constructed derivative function cannot be both positive and equal to zero.
Prove that the function f(x) = 3[x.sup.5] + 2[x.sup.3] + 2x + 1 has exactly one root.
The proof is in two parts: (1) existence and (2) uniqueness.
1. To establish the existence of a root it is sufficient to show that the function crosses the x-axis. Given that f is a continuous function with f(0) = 1, we need to find another value of x that produces a negative value of f(x). Guessing x = -1, we get f(-1) = 3.(-1)5 + 2.(-1) + 1 = -3 - 2 - 2 - 1 = -6. Thus, the intermediate value theorem ensures that [there exists] c [member of] (-1, 0) : f(x) = 0. Figure 3(a) below confirms the graph of f crossing the x-axis between -1 and 0.
2. The uniqueness of the root is proved by contradiction. Assuming two or more roots (say [r.sub.1] and [r.sub.2]) exist, then the mean value theorem tells us
[there exists] c [member of] ([r.sub.1], [r.sub.2]): f'(c) = [f([r.sub.1]) - f([r.sub.2])]/[[r.sub.1] - [r.sub.2]] = [0 - 0]/[[r.sub.1] - [r.sub.2]] = 0
In other words, there should be a horizontal tangent to the graph of y = f(x) at the point x = c. However,
[d/dx]f(x) = [d/dx](3[x.sup.5] + 2[x.sup.3] + 2x + 1) = 15[x.sup.4] + 6[x.sup.2] + 2 > 0, [for all] x [member of] R
which means any tangent to the graph has a positive gradient and therefore cannot be horizontal (Figure 3(b)). Thus, we get a contradiction. This function cannot have more than one root. It is increasing everywhere, it is differentiable so its derivative is always greater than zero.
The next example is from geometry. In this example the original assumption is contradicted.
Given a triangle ABC such that the two sides AB and BC are not equal and BD is a median, prove that BD is not perpendicular to AC.
Assume BD is perpendicular to AC, that is [angle]ADB = [angle]BDC = 90[degrees].
Now BD is a median so AD = DC. Therefore the two (right-angled) triangles ABD and BCD have two corresponding sides equal. It follows that the two triangles must be congruent, therefore AB = BC. Contradiction.
In the linear algebra example below, it is also the original assumption that is contradicted.
Let A be an invertible matrix. Prove that [A.sup.-1] is unique.
Suppose that A has two distinct inverses, namely B and C (B [not equal to] C).
We have AB = BA = I, where the identity matrix is
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
We also have AC = CA = I, so it follows that AB = AC.
Pre-multiplying by C gives C(AB) = C(AC).
By associativity, we have (CA)B = (CA) C. That is, IB = IC.
Hence, B = C. Contradiction. The inverse of A is unique.
Our final example shows how the given conditional statement may be proved by contradiction as well as by contraposition.
Prove that the reciprocal of any irrational number is irrational.
Proof 6 by contraposition
The statement may be written symbolically as
[for all] x [member of] R, x [not member of] Q [right arrow] [1/x] [not member of] Q
The contrapositive statement is
[for all] x [member of] R, [1/x] [member of] Q [right arrow] x [member of] Q
Our starting point is 1/x [member of] Q.
This means that, by definition of the rational numbers,
[there exists] m, n [member of] Z (n [not equal to] 0): 1/x = m/n
That is, x = n/m, which means x [member of] Q.
Proof 6 by contradiction
The negation of the original statement is
[there exists] x [member of] R: x [not member of] Q [conjunction] [1/x] [member of] Q
Again, our starting point is
1/x [member of] Q
and the next line of the derivation is identical to the proof by contraposition.
The result x [member of] Q contradicts the assumption x [not member of] Q.
The paper explored and clarified the similarities and differences that exist between proof by contradiction and proof by contraposition. The paper also focussed on the concept of contradiction mainly and a general model for this method of proof was offered.
The introduction of mathematical proof in the classroom remains a formidable challenge to students given that, at this stage of their schooling, they are used to manipulating symbols through sequential steps. There is a consensus that learners do find indirect types of proof quite difficult and do struggle with the conceptual and technical aspects of indirect proofs. As Epp (1998, p. 711) states, "Students find proof by contradiction considerably harder to master than direct proof". Indeed, learners may struggle with understanding the concept of indirect proofs in general and of proof by contradiction in particular. To address this issue further, and for learning purposes, proof by contradiction may be considered in conjunction with other methods and didactic tools, e.g., counterexamples or the pigeon-hole principle. But, this is a topic for another investigation.
Nicolas Jourdan & Oleksiy Yevdokimov
University of Southern Queensland
The authors wish to thank an anonymous reviewer for the useful comments and suggestions which helped to improve the paper.
Antonini, S. & Mariotti M. A. (2008). Indirect proof: What is specific to this way of proving? ZDM--The International Journal of Mathematics Education, 40(3), 401-412.
Barnard, T. & Tall, D. (1997). Cognitive units, connections and mathematical proof. In E. Pehkonen (Ed.), Proceedings of the 21st International Conference for the Psychology of Mathematics Education, (Vol. 2, pp. 41-48). Lahti, Finland: University of Helsinki.
Epp, S. (1998). A unified framework for proof and disproof. The Mathematics Teacher, 91(8), 708-713.
Epp, S. (2011). Discrete mathematics with applications (4th ed.). Boston, MA: Brooks/Cole & Cengage Learning.
Euclid. (1956). The thirteen books of Euclid's elements (translation and commentaries by T. L. Heath). New York: Dover Publications.
Goubault-Larrecq, J. & Mackie, I. (1997). Proof theory and automated deduction. Dordrecht, The Netherlands: Kluwer Academic Publishers.
Grossman, P. (2009). Discrete mathematics for computing (3rd ed.). New York: Palgrave Macmillan.
Hanna, G. & de Villiers, M. (2008). ICMI Study 19: Proof and proving in mathematics education. ZDM--The International Journal of Mathematics Education, 40(2), 329-336.
Heath, T. L. (1921). A history of Greek mathematics: From Thales to Euclid (Vol. 1). New York: Dover Publications.
Lin, F., Lee, Y. & Wu Yu, J. (2003). Students' understanding of proof by contradiction. In N. Pateman, B. Dougherty, & J. Zilliox (Eds), Proceedings of the Joint Meeting of PME and PMENA, (Vol. 4, pp. 443-449). Hawaii: PME.
Mancosu, P. (1991). On the status of proofs by contradiction in the seventeenth century. Synthese, 88, 15-41.
Mancosu, P. (Ed.). (1996). Philosophy of mathematical practice. Oxford, UK: Oxford University Press.
Thompson, D. R. (1996). Learning and teaching indirect proof. The Mathematics Teacher, 89(6), 474-482.
Williams, E. R. (1979). An investigation of senior high students' understanding of the nature of mathematical proof. PhD dissertation, University of Alberta, Canada.
Please note: Some tables or figures were omitted from this article.
|Printer friendly Cite/link Email Feedback|
|Author:||Jourdan, Nicolas; Yevdokimov, Oleksiy|
|Publication:||Australian Senior Mathematics Journal|
|Date:||Jan 1, 2016|
|Previous Article:||Proof and rhetoric: the structure and origin of proof--from ancient Greece to Abraham Lincoln's speech in defence of the union and Paul Keating's...|
|Next Article:||Editorial: the challenge continues.|