Why do students like proof by contradiction?

Question

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).

Answer 1

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.

Answer 2

"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.

Answer 3

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.

Answer 4

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.

Answer 5

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"?

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

When doing a proof by contradiction of "if A then B", you get to assume A and you also get to assume NOT B. Proving it directly, you only get to assume A. So proof by contradiction gives you more to work with from the start. I think that's why students like it.