23
$\begingroup$

Every-so-often I come across proofs of the form

  • Assume $X$ is false.
  • Prove $X$ is true (without using that it is false).
  • This contradicts that $X$ is false.
  • Hence $X$ is true.

I've seen students write such proofs, and I've seen them read this structure into a proof even when it isn't there.

Why do students seem to prefer this type of proof by contradiction to direct proof?

A couple of ideas I thought might be behind this:

  • 'proof by contradiction' is a thing they can give a name to, whereas direct proof doesn't have its own 'identity' in the same way;
  • in a proof by contradiction you see at the start what you are aiming for, ie the opposite of your assumption (this won't always work, but is probably true of most cases they see);
  • proof by contradiction changes the logic to something they find easier to think about (I came across this with a standard uniqueness proof - I think the idea that I had two objects that in the end turn out to actually be the same object was too confusing as an idea that was true, but it made more sense as a contradiction).
$\endgroup$
  • 10
    $\begingroup$ I understand the sentiment of your question, although I don't have an answer. Many times when trying to prove something, I first stumble on a proof by contradiction, only to soon thereafter find a direct proof that is even shorter. $\endgroup$ – user52817 Jan 7 '16 at 21:31
  • 6
    $\begingroup$ mathoverflow.net/a/12400/1106 may be useful. I think it may actually be easier to find a contradiction in that "nonexistant, contradictory land" than it is to find a direct proof in our real mathematical universe. I think students are tempted by the increased ease of proof by contradiction, and so gravitate towards it toward everything, without realizing what they are giving up as a result. $\endgroup$ – Steven Gubkin Jan 10 '16 at 2:20
  • 7
    $\begingroup$ I have a distinguished friend who uses proof by contradiction only as a last resort, since often this proof technique can short-circuit concrete constructions that lead to insight. If this claim is true, then it would explain why students like the technique so much…it has the power to more quickly end homework problems! $\endgroup$ – Jon Bannon Jan 10 '16 at 23:57
  • 11
    $\begingroup$ Assume students don't like proof by contradiction.... $\endgroup$ – rbp Jan 11 '16 at 16:28
  • 1
    $\begingroup$ Proof by contradiction is powerful. Perhaps you emphasized it too much in class? Follow @JonBannon's colleague's policy... $\endgroup$ – vonbrand Jan 11 '16 at 23:59

11 Answers 11

15
$\begingroup$

Suppose you're in an unfamiliar city without a map. You're trying to get to a particular address, which you know is within five blocks of you, but you have no idea how the streets are laid out, whether they're all orthogonal to one another, in which direction the addresses increase, or anything.

So to start out you'll probably walk in one direction until you can find at least two buildings on the same street with their addresses written on them. (This is surprisingly hard, if you haven't tried recently; often there may only be a single building on a block that has its address displayed anywhere.) Then you at least know which direction the numbers increase in. Next, you might figure this out in a perpendicular direction, and so forth.

Eventually, you'll reach your destination, but you likely won't have a solid mental picture of how you got there. And the path you took would look convoluted and absurd to someone familiar with the city, who knows that all the numbered streets in this city all run east-west and are all on the south side.

Someone setting out to write a proof for the first time cannot hold an entire proof in his head, even of something completely trivial. A student may be able to start out from the hypotheses and get to the conclusion while having no idea how what happened along the way. Since contradiction is often helpful, it makes sense to start out by trying this. By the time the proof is done, the student doesn't know whether this got used or not, because the student doesn't have the mathematical maturity to see the proof as anything more than a long sequence of steps, only one or two of which can be held in the mind at once.

$\endgroup$
11
$\begingroup$

"For all" statements are hard to grasp because they don't really exist outside of mathematics (or philosophy or other abstract domains). In any vaguely empiricist epistemology, you can have "there exist" statements, and you can have "for some" or "for most" or "for every case we have seen" statements, but even the last is not "for all" statement in the mathematical sense, and you can't verify empirically a "for all" statement in the mathematical sense.

Hence for someone who is not familiar with mathematics, the easiest way to conceive of a "for all" statement is as an absolute negation of a "there exist" statement. In other words, once we break a student out of thinking of a "for all" statement as an empirical "for every case we have seen" statement, the next step is for the student to think of the "for all" statement as a "there cannot logically exist a counterexample" statement. If you think of the statement you are trying to prove as a "there cannot logically exist a counterexample" statement, then you are naturally led to proof by contradiction.

$\endgroup$
  • 2
    $\begingroup$ I should add a citation: Personal communication, math education colleague down the hall. Said colleague might try to develop this idea into a paper if he ever figures out a way of studying it. $\endgroup$ – Alexander Woo Jan 11 '16 at 7:28
  • $\begingroup$ Who would be such an empiricist? "In this view, we must say, that it is only probable all men must die, or that the sun will rise to-morrow." $\endgroup$ – user173 Jan 13 '16 at 12:12
  • $\begingroup$ @AlexanderWoo You seem to claim that the difficult with "for all"-statements is that in real world people only face "for all cases that I have seen"-statements. Can you support this claim with further arguments? $\endgroup$ – Tommi Brander Feb 14 '16 at 18:29
  • $\begingroup$ Is it really hard to imagine that some people may believe that immortality is possible? There are people paying good money to be cryogenically frozen. $\endgroup$ – Daniel McLaury Feb 16 '16 at 5:11
7
$\begingroup$

My impression is that proofs by contradiction are easier to find – within a direct proof you need to reach some particular conclusion, while it is enough for a proof by contradiction to reach just any contradiction.

Moreover, rarely the reasoning in some direct proof is non-constructive. Frequently we use non-constructive theorems, but the "glue" is usually constructive. In my experience very few of proofs actually directly invoke the law of excluded middle or something similar. Thus, a direct proof can be indeed considered stronger/harder.

$\endgroup$
  • $\begingroup$ Will you delete the last line? It violates our helpful and stated policy: "Do not use signature, taglines, or greetings". matheducators.stackexchange.com/help/behavior $\endgroup$ – user173 Mar 5 '16 at 21:37
  • $\begingroup$ @MattF. Sure can. I had to be out for too long, since I don't remember that policy being enforced. $\endgroup$ – dtldarek Mar 5 '16 at 23:27
  • $\begingroup$ There not simpler but they're easier. Sometimes it's easier to prove a result by contradiction, but after you've found that proof you can rearrange it into a direct proof that's simpler. $\endgroup$ – Michael Hardy Jul 12 '16 at 0:29
  • $\begingroup$ @MichaelHardy That's nit-picking, but you are correct. But then allow me to nit-pick in return: proofs by contradiction are easier to find (as opposed to, say, read and understand). $\endgroup$ – dtldarek Jul 13 '16 at 19:51
  • $\begingroup$ I don't agree that it's nitpicking. There are contexts in which that distinction is important. $\qquad$ $\endgroup$ – Michael Hardy Jul 13 '16 at 19:52
5
$\begingroup$

This is unavoidably going to be a subjective answer, but I always liked Proof by Contradiction because it's often easier to prove that one case isn't true than it is to prove all cases are true.

Proof by contradiction allows the prover to focus on one specific case and show that the identity doesn't hold, as opposed to having to show that the converse holds for all, which can be more difficult to grasp due to the greater generality.

$\endgroup$
  • 6
    $\begingroup$ That would depend on the nature of the result you want to prove, ie whether it is a for-all statement or a there-exists one. $\endgroup$ – Jessica B Jan 8 '16 at 13:42
  • 3
    $\begingroup$ Sure, but you asked why students tend to prefer them. Clearly proof by contradiction isn't always viable, but if you have a proof method that you inherently understand to be "easier", you're going to be tempted try and fit it before you try anything else. $\endgroup$ – Ieuan Stanley Jan 8 '16 at 13:53
5
$\begingroup$

When I prove a theorem by contradiction, I have more information available to use in my deductions --- not only the hypotheses of the theorem but also the negation of the conclusion. Having that extra information can't hurt (except aesthetically) and might help, so I might as well assume it. If, after I complete the proof, I see that I never used that extra information, I have (or at least I like to think that I have) enough aesthetic sense and enough respect for constructive ideas to rewrite the proof as a direct proof. But when a beginning student completes such a proof, the sense of relief at having succeeded may outweigh any aesthetic sense, and so the useless detour via contradiction will survive.

$\endgroup$
4
$\begingroup$

One issue is that students typically don't polish successful proofs. They might start proving a proposition of the form P => Q by assuming that P is true and Q is false (perhaps because they have had success with such arguments) and then be satisfied if they reach a contradiction of the form P and not P or Q and not Q. Unless explicitly enjoined to do so, few students will make the effort to streamline the proof, hence it wouldn't even occur to them to revisit their argument and notice if their proof failed to use the assumption P (making it essentially a contrapositive proof) or failed to use the assumption Q (making it essentially a direct proof).

I'm not really sure what could be done about it. Perhaps a grading policy in which correct but suboptimal proofs are not given full credit could help. Personally, I'm so overjoyed when I see a correct proof that I give it full credit and content myself with writing comments on the proof.

$\endgroup$
3
$\begingroup$

When students prove results by contradiction, it might just be following what they see in class.

Perhaps the first two theorems they see are "there are infinitely many primes" and "$\sqrt{2}$ is irrational", with both proved by contradiction. Then they naturally use that technique as a default.

As an alternative, one can prove the infinitude of primes in the Euclidean way, as "the number of primes is more than any assigned magnitude". And instead of proving irrationality, one can start with an example like "there is a sequence of 100 consecutive composite numbers".

This shows students a key ingredient in direct proof, and it has a name that they can learn too: proof by construction.

$\endgroup$
  • 4
    $\begingroup$ It's worth noting that neither of those theorems are really proved by contradiction. Euclid's proof is an explicit algorithm for generating primes not contained in a given finite list of primes; the version with unnecessary contradiction has unfortunately even made its way into some textbooks, demonstrating that this bad habit isn't limited to students. And the usual proof that $\sqrt{2}$ is irrational is a proof by negation, not by contradiction. $\endgroup$ – Daniel Hast Jan 11 '16 at 7:24
  • 3
    $\begingroup$ @DanielHast: the distinction between proof by negation and prof by contradiction is ignored by many mathematician, most of whom assume implicitly the law of excluded middle, making both concept practically equivalent. I think intuitionism should be acknowledged more, and this distinction should be known to mathematician, but I don't think it would be a relevant distinction to enforce to undergrads. $\endgroup$ – Benoît Kloeckner Jul 10 '16 at 8:22
  • $\begingroup$ @DanielHast : You are certainly right that Euclid's proof of the infinitude of primes is not by contradiction. But I'd have said "Neither of those theorems is_$\,\ldots$. (Neither of them _is a proof by contradiction.) (I wonder if using the plural here will soon be considered standard English?) $\endgroup$ – Michael Hardy Jul 11 '16 at 14:24
  • $\begingroup$ @MichaelHardy: Both sound grammatical to me. $\endgroup$ – Daniel Hast Jul 11 '16 at 14:48
3
$\begingroup$

This mistake is frequently made by mathematicians in the following way. First consider this proof:

  • Let $S$ be any finite set of prime numbers. (For example, one could have $S=\{2,7,19\}$.)
  • Prove that the prime factors of $1+\prod S$ are not members of $S$. [Details omitted.]
  • Conclude that every finite set $S$ of prime numbers is a subset of some larger finite set of prime numbers.

Euclid wrote that proof. It is not by contradiction.

Dirichlet in the 19th century and many eminent mathematicians since then have rearranged Euclid's proof to read as follows:

  • Assume only finitely many prime numbers exist.
  • Then insert the argument described above here, proving there are infinitely many prime numbers.
  • This is a contradiction; hence the assumption was false.

Dirichlet and many later authors wrote that Euclid's proof was by contradiction. That is a historical error. Rearranging it into a proof by contradiction just makes it more complicated and serves no purpose. It also leads to errors, in the following way. An author writes something like "The number $1+\prod S$, having no prime factors, must be prime itself. But that contradicts the assumption [etc.]." Then students think that it has been proved that if you multiply the first $n$ prime numbers and then add $1$, the result is always prime. But that is false: $1+(2\times3\times5\times7\times11\times13) = 59\times 509$ and there are many other counterexamples.

Without the assumption that $S$ contains all primes numbers, one would not conclude that a number not divisible by any member of $S$ is not divisible by any prime, and without that, one would not conclude that it must itself be prime. Hence rearranging the proof into a proof by contradiction has introduced a substantial error.

One student proposed to prove infinitely many twin primes exist by saying that $\pm1+\prod S$ are both prime whenever $S$ is the set of the first $n$ primes. (But that of course is false.)

Another student went to Wolfram and found numerous counterexamples and claimed that therefore Euclid's proof was wrong. But in fact, Euclid's proof was right.

Catherine Woodgold and I published a paper examining the history of this error committed by otherwise respectable mathematicians.

So why do mathematicians "read this structure into a proof even when it isn't there"?

$\endgroup$
  • 2
    $\begingroup$ If one wants to conclude that there are infinitely many primes, isn't there an argument by contradiction to be added to Euclid's proof? As you write it, we obtain that every finite set of prime numbers is contained in a larger finite set of prime numbers. Then to conclude, don't we at least implicitly assume that set of primes is finite, then reach a contradiction? Even so, I agree that your account is convincing, and it looks better to push the proof by contradiction to the end. $\endgroup$ – Benoît Kloeckner Jul 10 '16 at 8:16
  • 1
    $\begingroup$ @BenoîtKloeckner : No. What Euclid proved is that every finite set of primes can be extended to a larger finite set of primes, so, as we say in modern language, there are infinitely many primes. There is no need to make that into a proof by contradiction. Doing so is at best a pointless complication. Many mathematicians have unthinkingly passed along the error they were taught without noticing this. $\qquad$ $\endgroup$ – Michael Hardy Jul 10 '16 at 16:51
  • 1
    $\begingroup$ Hum, I guess one should be cautious about the definitions of finite set and infinite set to be sure no contradiction is used, even possibly in the basic properties of these notions, but I can believe it can be avoided even if I have not checked carefully. $\endgroup$ – Benoît Kloeckner Jul 11 '16 at 10:14
  • 1
    $\begingroup$ @BenoîtKloeckner A set of primes can be extended to grow beyond each natural number. Therefore each natural number cannot be the number of primes. Therefore the number of primes cannot be finite. There's no assumption made for contradiction there. $\endgroup$ – Reinstate Monica Jul 11 '16 at 14:25
  • 1
    $\begingroup$ @Solomonoff'sSecret in an intuitionistic point of view (which makes e.g. distinction between proof by contradiction and proof by negation more relevant), and depending on the definitions under use, it might not be obvious that a set which is not finite must be infinite (cf e.g. en.wikipedia.org/wiki/Finite_set for some possible definitions of finite). $\endgroup$ – Benoît Kloeckner Jul 11 '16 at 18:46
2
$\begingroup$

My other answer isn't quite at the heart of the topic, so I'll add this: Often (usually) students in math courses are uncertain how to proceed, so they just try whatever they've recently been told about in class. If proof by contradiction was introduced recently, they'll use it.

$\endgroup$
1
$\begingroup$

The most obvious reason of attraction towards the 'proof by contradiction' may be:

$1$.A Student knows the first line of proof which is just the inverse of the statement to be proved.

$2$. At least he/she knows what is the last line of proof, which is just the inverse of point $1$ or contradiction to a known mathematical fact.

$\endgroup$
1
$\begingroup$

I can understand the impulse to do so, because of the novelty and scandalousness of "proof by contradiction". Quite exotic and unlike any sort of rhetorical devices used in ordinary life. Also, as other answers and comments have observed, given typical prior human context, an assertion about an individual entity may be easier to contemplate than a universal assertion whether positive or negative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.