Are the "proofs by contradiction" weaker than other proofs?

Solution 1:

To this MathOverflow question, I posted the following answer (and there are several other interesting answers there):

• 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 nonexistant, 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.

For an example of a proof where we are led to false expectations in a proof by contradiction, consider Euclid's theorem 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 because 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. (And Michael Hardy mentions that indeed Euclid had made the direct argument.)

Solution 2:

Most logicians consider proofs by contradiction to be equally valid, however some people are constructivists/intuitionists and don't consider them valid.

(Edit: This is not strictly true, as explained in comments. Only certain proofs by contradiction are problematic from the constructivist point of view, namely those that prove "A" by assuming "not A" and getting a contradiction. In my experience, this is usually exactly the situation that people have in mind when saying "proof by contradiction.")

One possible reason that the constructivist point of view makes a certain amount of sense is that statements like the continuum hypothesis are independent of the axioms, so it's a bit weird to claim that it's either true or false, in a certain sense it's neither.

Nonetheless constructivism is a relatively uncommon position among mathematicians/logicians. However, it's not considered totally nutty or beyond the pale. Fortunately, in practice most proofs by contradiction can be translated into constructivist terms and actual constructivists are rather adept at doing so. So the rest of us mostly don't bother worrying about this issue, figuring it's the constructivists problem.

Solution 3:

In order to prove A, let's assume not A.

[Insert 10-page argument here.]

Which of the assertions proved in the foregoing 10 pages are false because they were deduced from the (now proved false) assumption that not A? Which are true but cannot be considered to have been validly proved because the proofs relied on the false assumption that not A? And which were validly proved since their proofs did not rely on that assumption? It can be hard to tell. And if you saw an assertion proved along the way, you might think it's known to be true.

In that way, a proof by contradiction can be at best confusing.