Why are proofs by contradiction counterintuitive?

Question

And how to make them intuitive?

---

We are tasked to prove $P \implies Q$. So we assume $P$ and are trying to prove $Q$. We assume not-$Q$ ($\neg Q$) and derive a contradiction, establishing $Q$.

There is something counterintuitive about this. To prove $Q$ is true, we assume $Q$ is false. So we have in mind both $Q$ and $\neg Q$ simultaneously. We reason with a falsity to arrive at truth. Why is it legitimate to reason with something you know (eventually) is false? Couldn't assuming something false lead your reasoning astray?

Have any of you had difficulty making this type of reasoning convincing? I would appreciate hearing your strategies.

---

^{I think my question is different from: Why do students like proof by contradiction?.}

Answer 1

One reason why proof by contradiction is difficult for students is because mathematical notation (and other written language) does not allow for a subjunctive mood.

Let me elaborate on this: In English and other "natural" languages, we can distinguish between a state of affairs that is true, and a state of affairs that can be provisionally thought of as true. We can say:

I am the President of the United States, and therefore I support this legislation

but we can also say

If I were the President of the United States, then I would support this legislation

and we understand these two sentences as meaning very different things. Mathematical notation, however, elides or erases those shades of meaning: If $P$ is the proposition "I am the President of the United States" and $Q$ is the proposition "I support this legislation" then both of the two sentences above would be symbolized as $P \implies Q$ or written as "If $P$ then $Q$".

What does this have to do with proof by contradiction? Consider how one starts a proof that $x^2=2$ has no rational solutions. We say:

Suppose $x = m/n$ is a solution, with $m, n$ relatively prime whole numbers. Then $m^2 = 2n^2$, so $m^2$ is even, which means that $m$ is even. Therefore...

Now, in the above proof, consider how you would read aloud the equation $m^2 = 2n^2$. I strongly suspect that most people would read it as

"$m$ squared equals two $n$ squared"

rather than as

"$m$ squared would equal two $n$ squared"

This is precisely the sticking point: We read the symbol $=$ as saying (falsely!) that two things are equal, rather than as saying (correctly!) that two things would be equal if the initial hypotheses were true. The absence of a subjunctive mood in mathematics leads us to say things like

"Suppose $m/n$ is a solution; therefore..."

when what we really mean is

"Suppose $m/n$ were a solution; then..."

This observation, by the way, has been made before: A few years ago I came across a very brief article from The Mathematics Teacher, published more than 60 years ago, that made essentially the same argument. The article is

Butler, C. (1955). "A note on the statements of theorems and assumptions." Mathematics Teacher, 48, 106-107.

The Butler article does not explicitly invoke the subjunctive mood by name, but expresses the same idea, as the following excerpt shows (all emphases in the original):

Such apparent discrepancies... do bother immature high school students who are just learning what a demonstration means. To them it doesn't make sense to say "assume that $\angle x = \angle y$" when they can see from the diagram that angle $x$ actually is not equal to angle $y$, or to conclude that $RS \hskip{0.05 in} || \hskip{0.05 in} PQ$ when those lines can be seen actually to intersect in the diagram.

On the other hand, most students, even though mathematically immature, would find no difficulty in accepting the statement that "IF angle $x$ WERE equal to angle $y$, then $RS$ WOULD BE parallel to $PQ$" as a reasonable statement even though the diagram does not appear to exhibit these conditions.

To cite a non-geometrical proposition which is the exact counterpart of the foregoing example, it might easily appear ridiculous to young students for a $5 \frac{1}{2}$ foot man to say "Assume that I am $9$ feet tall; therefore I can touch the ceiling," but the same students would readily accept from the same man the statement, "IF I WERE 9 feet tall, THEN I COULD touch the ceiling" and regard it as a perfectly normal kind of statement.

Logically there is no difference between saying "Assume this is true; therefore that is true" and "If this were true, then that would be true," but there is a profound difference in the attitude or feeling induced in immature students by the two forms of statement.

Notice in particular that Butler realizes that a symbolic expression like "$\angle x = \angle y$" would be read as "angle $x$ is equal to angle $y$"; the only way to invoke the subjunctive mood is to drop the symbolic language altogether and use verbal formulations instead.

Answer 2

Disclaimer:

I was looking for modes of though that would produce your question, and I found one, which might help you clarify some things. Still, (I hope not) it might confuse you even more, I don't know. Proceed at your own risk.

On proof by contradiction:

When writing a proof by contradiction of $P \to Q$, we indeed assume $\neg Q$ and try to prove that together with $P$ it implies falsehood $\bot$, that is,

$$P \land \neg Q \to \bot.$$

You can think of it, as an enumeration of cases type of proof. Let me give you an example:

Suppose Steve can be in New York or San Francisco (at least one). It is enough to check that he is not in New York to conclude that he is in San Francisco.

This type of reasoning hinges on the fact that there are at most two cases to check. In other words, proof of contradiction looks like this:

Assume $P$. Suppose that $Q$ can be either true or false. It is enough to check that $Q$ is not false, to conclude that it is true.

It works, because in classical logic we have the law of excluded middle: $Q \lor \neg Q$. However, sometimes $Q$ can have more values, in particular in intuitionistic logic, where proof by contradiction is not a valid proof. For example, if we would allow third valuation unknown, then you cannot conclude something is true based on whether it is not false.

A nice everyday example is "not X" language pattern. Many times people prefer to use "not good" instead of "bad", among others, because it doesn't say how much the person is disappointed/angry/whatever – it could be continued by "a few small tweaks and it will work" or "we won't be able to fix it in a million years". On the other hand, "not X" has clear meaning if there are only two possible states, e.g. "What are you doing?! The gun's safety is not on!".

Similar phrases can also mimic the proof of contradiction. For example, observe how drastically the following dialogue changes meaning:

Alice: Where is Steve, is he working?

Bob: He's not in New York.

if from the context of the situation we know that Steve:

• has a girlfriend in New York, where he spends all the free time he has.
• he is an international journalist who frequently visits his parents to care for them.

The first one basically says "yes, he's working", while the other means Bob doesn't have the slightest idea whether Steve embarked on another work-related trip, or is just visiting his parents.

Answer 3

I think the context is red herring — the core issue is the fact that (where $\bot$ denotes contradiction)

$R \implies \bot$ is equivalent to $\neg R$

Similarly, by applying double negation

$\neg R \implies \bot$ is equivalent to $R$

So what you need to do is wrap your head around these facts. Once you have that, we can apply it to the proof form you're considering:

$P \implies Q$ is equivalent to $P \implies (\neg Q \implies \bot)$.

Answer 4

A proof by contradiction starts by assuming the opposite (complement) of your main assumption, and deriving a contradiction with your hypothesis. Since "not A" (the opposite of your assumption) produces an absurd result, by implication, your main assumption must be true.

It requires a good understanding of the ideas of "complementarity," contrapositve and "converse," which many students don't have, because they haven't studied enough set theory and logic.

It's easy enough to understand for someone who has a good grounding in say, truth tables.