Reductio ad absurdum or the contrapositive? - MathOverflow

Reductio ad absurdum or the contrapositive?

2010-01-19T22:26:30Z

From time to time, when I write proofs, I'll begin with a claim and then prove the contradiction. However, when I look over the proof afterwards, it appears that my proof was essentially a proof of the contrapositive, and the initial claim was not actually important in the proof.

Can all claims proven by reductio ad absurdum be reworded into proofs of the contrapositive? If not, can you give some examples of proofs that don't reduce? If not all reductio proofs can be reduced, is there any logical reason why not? Is reductio stronger or weaker than the contrapositive?

Edit: Just another minor question (of course this is optional and will not affect me choosing an answer): If they are equivalent, then why would you bother using reductio?

And another bonus question (Like the above, does not influence how I choose the answer to accept.) Are the two techniques intuitionistically equivalent?

Answer by compguy for Reductio ad absurdum or the contrapositive?

2010-01-19T23:37:54Z

They are trivially equivalent. The contrapositive of (P → Q) is (¬Q → ¬P). This is equivalent to (¬Q → (P → ⊥)), which is a curried form of (¬Q ∧ P) → ⊥.

Edit: I'm not sure about your added comment. Reductio seems the more general proof technique to me (as Anweshi mentions, it works for statements which are not implications); contraposition seems less useful unless the contrapositive form ¬Q → ¬P is especially natural or intuitive.

Edit 2: These transformations would seem to be intuitionistically valid, with the proviso that a "proof by contradiction of (P → Q)" is only a proof of (P → ¬¬Q). Hence, the contrapositive (¬Q → ¬P) is strictly weaker than (P → Q).

On a further note, it is often the case that the antecedent P can be naturally seen as a negative statement (¬P'). In these cases, we may be able to provide a proof of (¬Q → P'). This may be the case of a proof by contrapositive which is a "direct proof", possibly accounting for J. Polak's remarks.

Edit 4: JD Hamkins points out that direct proofs often provide useful proofs of intermediate statements, whereas proofs by contradictions do not. But this technique can be generalized by pushing contradictory "contexts" to the very end of the proof: i.e. one can say: "We will prove a contradiction by assuming P, Q, R and S. From P, R and S we obtain the following lemmas..." It's not clear that all such proofs can be naturally stated as proofs by contrapositive.

Answer by François G. Dorais for Reductio ad absurdum or the contrapositive?

2010-01-19T23:46:13Z

Strictly speaking, the contrapositive of a statement which is not an implication doesn't make sense. However you can always fake the implication, the contrapositive of $\top \to A$ (or just $A$) is $\lnot A \to \bot$, i.e., a "proof by contradiction" is the contrapositive of a "proof (from tautology)."

I guess I can still answer the other two parts, which were added later on.

First, a proof by contradiction is a more versatile tool than the contrapositive. It is more efficient when dealing with complex statements, e.g. anything which is not a simple implication. Also, the contrapositive doesn't work very well when the hypothesis is not completely necessary or when implicit hypotheses are lurking around. For (pseudo-)example, suppose $A$ and $B$ are statements about widgets with property $C$. You have proof that $A \to B$ by assuming that $A$ and $\lnot B$ and concluding that either $\lnot A$ or the widget does not have $C$. You could formally conclude $\lnot A$ from the failure of $C$ since $C$ is an implicit hypothesis, but that would be unnatural. Proving $\lnot B \to \lnot A$ directly might be difficult since it is unclear where the implicit hypothesis $C$ should come in play. Of course, all of this can be fixed by removing unnecessary hypotheses and stating all implicit hypotheses, but this only happens in fairy tales (a.k.a. well written textbook exercises). See Pete's answer (and vote it up!) for more concrete examples...

Finally, to answer the very last part. The implication

$(B \to A) \to (\lnot A \to \lnot B)$

is intuitionistically valid. Indeed, the right hand side is a much weaker statement. The converse

$(\lnot A \to \lnot B) \to (B \to A)$

gives $\lnot\lnot A \to A$ when substituting $\top$ for $B$, so it only holds in classical logic. However,

$(B \to \lnot A) \leftrightarrow (A \to \lnot B)$

is intuitionistically valid, both sides say $\lnot(A \land B)$. So you can always take the contrapositive of an implication whose conclusion is negative. This is yet another face of the old saying "you can't prove a negative" or, more accurately, proving a negative is inherently nonconstructive.

Answer by Jason Polak for Reductio ad absurdum or the contrapositive?

2010-01-20T00:21:14Z

There does seem to be a difference, although I don't know how to distinguish them formally, but here are two cases which distinguish the two:

*Let V be a vector space. A linear map f on V is injective if its kernel is 0. (yes I know it's an iff). The contrapositive is, if f is a linear map and ker f is not 0, then f is not injective. Proof: $v\in \ker f$ nonzero means $f(v) = f(0) = 0$. We don't have to assume in the proof that f is injective first and get a contradiction.

Here we are arguing about a class of objects with one property and we are trying to prove another of that class.

*sqrt(2) is irrational. We can word this (artificially) as x = sqrt(2) implies there does not exist a,b rational such that x = a/b. However if we try the contrapositive, we get, there exists a,b rational such that x = a/b implies x is not sqrt(2). But to prove this we still need to assume that a/b = sqrt(2) and derive a contradiction.

Here we are trying to prove that a single object does not possess a certain characteristic. There must be a more formal treatment of these differences, however...

Answer by Pete L. Clark for Reductio ad absurdum or the contrapositive?

2010-01-20T03:02:35Z

My answer applies to standard logic only.

In terms of standard logic, proofs by contrapositive and by contradiction are "equivalent" in that they are both logically valid, and two logically valid propositions are equivalent to each other.

On the other hand, it is certainly true that every proof by contrapositive can be phrased as a proof by contradiction. Indeed, since the latter is perhaps a bit more intuitive, it is often used as a justification of the former when it is needed e.g. in calculus courses:

We wish to show $A \implies B$. Suppose we know that $\lnot B \implies \lnot A$. Suppose further that $B$ is false. Then $\lnot B$ is true, so $\lnot A$ is true, so $A$ is false, contrary to our assumption.

Suppose a proposition can be proved by contraposition. As above, there is then a standard recipe for modifying the proof to give a proof by contradiction. However, if you compare the two proofs you find that the one by contradiction merely has the above two line argument appended to it, so it is just slightly longer without any additional content. For this reason, when it is possible to give a direct proof of $\lnot B \implies \lnot A$ it is preferable to do so, rather than casting it as a proof by contradiction.

However, proof by contradiction is a more powerful technique in the informal sense that some proofs are more difficult to phrase using contraposition. (I don't want to say impossible, because as above, both "techniques" are simply logically valid arguments, so may be inserted in a proof at any point.)

What makes contradiction potentially more powerful? (This is a question that you have to face when you teach introduction to proofs classes, as I have. I wouldn't have had as ready an answer before.) I think it is because we get to assume two things rather than one. Namely, instead of just assuming $\lnot B$ and using that one assumption to work our way to $\lnot A$, we get to assume both $A$ and $\lnot B$ and play them off one another in order to derive a contradiction.

Here is an example of this. Suppose we wish to prove that $\sqrt{2}$ is irrational. First, let's phrase this as an implication:

For all $x \in \mathbb{R}$, $x^2 = 2 \implies x \not \in \mathbb{Q}$.

Or, contrapositively:

For all $x \in \mathbb{R}$, $x \in \mathbb{Q} \implies x^2 \neq 2$.

Taking the contrapositive was not so helpful! What we need to do is work from both ends at once:

Suppose that $x \in \mathbb{Q}$ and $x^2 = 2$. Now we are in business; we can work with this. (I omit the proof since I assume that everyone knows it.)

Here is another difference between the two proofs, which I didn't notice until I thought about this answer: the contrapositive of the statement

$\forall x \in S, P(x) \implies Q(x)$

$\forall x \in S, \lnot Q(x) \implies \lnot P(x)$:

note that the quantifier has not changed. (Of course we might have an existential quantifier instead, and the discussion would be the same. Anyway, in practice most mathematical propositions do begin with a universal quantifier.)

However, the negation of the statement is

$\exists x \in S \ | \ P(x) \wedge \ \lnot Q(x)$.

Note that the quantifier has changed from $\forall$ to $\exists$, which is a key feature of the above proof.

Finally, you ask why we would prefer one technique over another since both are equivalent. But of course we do this all the time, according to convenience and taste: e.g. induction, strong induction and well-ordering are all logically equivalent, but we use all three. We could e.g. phrase all induction proofs as appeals to the Well-Ordering Principle, but in many cases that would amount to inserting a tiresome rigamarole "Consider the set $S = \{ n \in \mathbb{N} \ | \ P(n)\ \text{is false} \}$ ..." which does not add to the clarity or concision of the proof.

Answer by Joel David Hamkins for Reductio ad absurdum or the contrapositive?

2010-01-20T09:37:03Z

Although the other answers correctly explain the basic logical equivalence of the two proof methods, I believe an important point has been missed:

With good reason, we mathematicians prefer a direct proof of an implication over a proof by contradiction, when such a proof is available. (all else being equal)

What is the reason? The reason is the fecundity of the proof, meaning our ability to use the proof to make further mathematical conclusions. When we prove an implication (p implies q) directly, we assume p, and then make some intermediary conclusions r₁, r₂, before finally deducing q. Thus, our proof not only establishes that p implies q, but also, that p implies r₁ and r₂ and so on. Our proof has provided us with additional knowledge about the context of p, about what else must hold in any mathematical world where p holds. So we come to a fuller understanding of what is going on in the p worlds.

Similarly, when we prove the contrapositive (¬q implies ¬p) directly, we assume ¬q, make intermediary conclusions r₁, r₂, and then finally conclude ¬p. Thus, we have also established not only that ¬q implies ¬p, but also, that it implies r₁ and r₂ and so on. Thus, the proof tells us about what else must be true in worlds where q fails. Equivalently, since these additional implications can be stated as (¬r₁ implies q), we learn about many different hypotheses that all imply q.

These kind of conclusions can increase the value of the proof, since we learn not only that (p implies q), but also we learn an entire context about what it is like in a mathematial situation where p holds (or where q fails, or about diverse situations leading to q).

With reductio, in contrast, a proof of (p implies q) by contradiction seems to carry little of this extra value. We assume p and ¬q, and argue r₁, r₂, and so on, before arriving at a contradiction. The statements r₁ and r₂ are all deduced under the contradictory hypothesis that p and ¬q, which ultimately does not hold in any mathematical situation. The proof has provided extra knowledge about a nonexistent, contradictory land. (Useless!) So these intermediary statements do not seem to provide us with any greater knowledge about the p worlds or the q worlds, beyond the brute statement that (p implies q) alone.

I believe that this is the reason that sometimes, when a mathematician completes a proof by contradiction, things can still seem unsettled beyond the brute implication, with less context and knowledge about what is going on than would be the case with a direct proof.

Edit: For an example of a proof where we are led to false expectations in a proof by contradiction, consider Euclid's proof that there are infinitely many primes. In a common proof by contradiction, one assumes that p₁, ..., p_n are all the primes. It follows that since none of them divide the product-plus-one p₁...p_n+1, that this product-plus-one is also prime. This contradicts that the list was exhaustive. Now, many beginner's falsely expect after this argument that whenever p₁, ..., p_n are prime, then the product-plus-one is also prime. But of course, this isn't true, and this would be a misplaced instance of attempting to extract greater information from the proof, misplaced becasue this is a proof by contradiction, and that conclusion relied on the assumption that p₁, ..., p_n were all the primes. If one organizes the proof, however, as a direct argument showing that whenever p₁, ..., p_n are prime, then there is yet another prime not on the list, then one is led to the true conclusion, that p₁...p_n+1 has merely a prime divisor not on the original list.

Answer by Terry Tao for Reductio ad absurdum or the contrapositive?

2010-01-20T17:04:20Z

I agree with Joel's answer: proofs by contrapositive are more satisfying than proofs by contradiction, because they give you more information beyond just knowing that the desired result is true. For instance, in analysis, proofs by contrapositive tend to be finitary in nature and yield effective bounds, whereas proofs by contradiction (especially when combined with compactness arguments) tend to be infinitary in nature do not easily yield such bounds (unless one very painstakingly converts each step of the infinitary contradiction argument into a finitary contrapositive argument). I discuss this for instance in

http://terrytao.wordpress.com/2008/08/30/the-correspondence-principle-and-finitary-ergodic-theory/

But by the same token, proof by contradiction is a more powerful method in practice than proofs by contrapositive, if your only aim is to prove the stated result; it is precisely because one is less ambitious that one can achieve one's goal more easily.

There is an analogy with the computational problem of trying to find a path in a maze from A to B. The direct approach would be to start from A and explore all reasonable-looking directions from A until one reaches B. The analogue of proof by contrapositive would be starting backwards from B and trying to reach A; then at the end one simply reverses the path. The analogue of proof by contradiction is a meet-in-the-middle strategy: explore both forwards from A and backwards from B until one gets an intersection. This is a faster strategy, with a run time which is typically the square root of the run time of the other two approaches (because of the birthday paradox, basically, or Metcalfe's law if you wish). This analogy is somewhat oversimplified because even in the meet-in-the-middle strategy it is not difficult to disentangle the solution to create a direct path from A to B; but with more complicated problem-solving tasks than mazes (e.g. trying to convert several hypotheses $A_1,\ldots,A_n$ into several conclusions $B_1,\ldots,B_m$, using deductive rules such as ``If $A_3$ and $C_5$ are true, then $D_7$ is true'', etc.) one can make the meet-in-the-middle solutions quite hard to convert back to a direct argument.

There is a class of proofs by contradiction that I call "no self-defeating object" arguments, which are particularly difficult to convert into proofs by contrapositive. Basically these proofs tend to show that A is false by using one argument to establish $A \implies B$ and another to establish $A \implies \neg B$, giving the contradiction (A defeats itself). One can convert this into a proof by contrapositive by making the inspired decision to divide into the two cases $B$ and $\neg B$, and show that each of these cases implies $\neg A$ by taking contrapositives of each side of the no-self-defeating object, but it is difficult in practice to motivate this choice of division into cases unless one had already seen the proof-by-contradiction version of the argument. This is particularly the case if A is an existence statement $\exists x: A(x)$ and B is dependent on x; then the dichotomy $B \vee \neg B$ cannot even be introduced without first introducing x. I discuss this type of argument on my blog at

http://terrytao.wordpress.com/2009/11/05/the-no-self-defeating-object-argument/

Answer by Artem Kaznatcheev for Reductio ad absurdum or the contrapositive?

2010-10-21T21:58:01Z

It often feels like a proof by contradiction is like making your point through a witty joke and the contrapositive is sitting down and explaining why the joke is funny.

Since the two approaches are logically equivalent, and since it is usually easy for the average journal reader to convert between the two --- the distinction for me comes down to style. Most of the arguments I have seen by contradiction are usually shorter, more intuitive, and elegant. Hence, I would usually favor proof by contradiction (it is usually the first proof I come up with...) unless the steps in the contrapositive are particularly insightful.