When is proof by contradiction necessary?

It’s been a while since I have written a post in the “somewhat philosophical” category, which is where I put questions like “How can one statement be stronger than an another, equivalent, statement?” This post is about a question that I’ve intended for a long time to sort out in my mind but have found much harder than I expected. It seems to be possible to classify theorems into three types: ones where it would be ridiculous to use contradiction, ones where there are equally sensible proofs using contradiction or not using contradiction, and ones where contradiction seems forced. But what is it that puts a theorem into one of these three categories?

This is a question that arises when I am teaching somebody who comes up with a proof like this. “Suppose that the sequence $(a_n)$ is not convergent. Then … a few lines of calculation … which implies that $a_n\rightarrow a$ . Contradiction.” They are sometimes quite surprised when you point out that the first and last lines of this proof can be crossed out. Slightly less laughable is a proof that is more like this. “We know that $|y-x|<\delta$ . Suppose that $|\sin(y)-\sin(x)|\geq\delta$ . Since the derivative of $\sin$ has absolute value at most 1 everywhere, it follows that $|y-x|\geq\delta$ , which is a contradiction. Therefore, $|\sin(x)-\sin(y)|<\delta$ .” There, it is clearly better to work directly from the premise that $|y-x|<\delta$ via the lemma that $|f(x)-f(y)|\leq\|f'\|_\infty |x-y|$ to the conclusion that $|\sin(y)-\sin(x)|<\delta$ . However, the usual proof of the lemma does use contradiction: one assumes that the conclusion is false and applies the mean value theorem.

The result of all this is that I don’t have a good tip of the form, “If your theorem is like this then try a proof by contradiction, and otherwise don’t.” For the remainder of this post I’ll discuss another couple of examples that show some of the complications that arise.

Example 1. The irrationality of the square root of 2.

This is of course the classic proof by contradiction, and one can even give a kind of quasi-proof that it must use contradiction. The reason is that the word “irrational” means “not equal to $p/q$ for any pair of integers $(p,q)$ “. If that is the definition, then let us suppose that the last two lines of the proof went: therefore $\sqrt{2}$ has property $P$ ; therefore $\sqrt{2}$ is irrational. We could then ask, “Why does having property $P$ imply that a number is irrational?” It might be obvious that property $P$ implies irrationality, but to prove it it would still be necessary to say, “Well, take any rational number $x=p/q$ … therefore $x$ does not have property $P$ .” (Why would that be necessary? For precisely the same reason! Perhaps this is an induction on proof length or something like that.)

With those thoughts in mind, consider the following argument. We begin by calculating the continued-fraction expansion of $\sqrt{2}$ . We find that $\sqrt{2}=1+(\sqrt{2}-1)=1+1/(\sqrt{2}+1)$ . The denominator of the fraction is $2+(\sqrt{2}-1)=2+1/(\sqrt{2}+1)$ , so we see that the continued-fraction expansion repeats itself, and, in one reasonably standard notation, is $[1;2,2,2,\dots]$ . In particular, it is infinite. Therefore, $\sqrt{2}$ is irrational.

At first sight, this looks like a direct argument rather than a proof by contradiction: we used the hypothesis that $x^2=2$ to deduce that $x$ has a property that obviously implies irrationality. However, as I mentioned in the general remarks, one could question this by asking, “Why is it that a number with an infinite continued-fraction expansion has to be irrational?” The answer? It’s obvious that a rational number has a terminating continued fraction, because as you work it out the denominators keep decreasing … oops, sorry, that was a proof by contradiction.

So perhaps the answer is indeed that if you are trying to prove a negative statement, then you have to use a proof by contradiction. But what is a “negative statement”? How about the following theorem?

Theorem. If $p$ and $q$ are integers, then $p^2\ne 2q^2$ .

Aha, you say, the “not equals” makes that negative. But we can deal with that by a quick reformulation.

Theorem. If $p$ and $q$ are integers, then $(p^2-2q^2)^2>0$ .

What’s negative about that? If you think that it’s somehow bound up in the notion of “strictly greater than”, then how about this?

Theorem. If $p$ and $q$ are integers, then there exists a real number $x$ such that $(p^2-2q^2)x=1$ .

That looks pretty positive to me, since it is asserting the existence of something.

It becomes less positive if you imagine how you would establish the existence of such an $x$ . The obvious thought would be, “Well, the only thing that could possibly go wrong is if $p^2=2q^2$ , so all we have to prove is that $p^2\ne 2q^2$ .” And that’s negative again. So does that mean that a statement is negative if the only sensible way of proving it is to reduce it to a statement that includes the word “not”? Even if something like that is correct, it seems quite hard to formalize.

Here’s another example of that last type of question. Is being infinite a negative property? One might say yes, because it means not being finite. But when we were talking about continued fractions, all we cared about was sequences, and we can define a sequence to be infinite if its terms can be put in bijection with the natural numbers. (And we could define a set to be infinite if there is an injection to a proper subset. But is a proper subset a negative concept because it means not including all elements?)

Example 2. Continuous functions on closed bounded intervals.

Until recently I “knew” that the following was the case. If you want to prove something using the compactness of $[0,1]$ , then you can either prove it directly using the Heine-Borel theorem or you can prove it by contradiction by reformulating everything in terms of sequences and applying the Bolzano-Weierstrass theorem. For example, to prove that a continuous function $f$ on $[0,1]$ is bounded, you either find a neighbourhood of each point on which $f$ is bounded (by the definition of continuity) and cover $[0,1]$ by finitely many such neighbourhoods (by the Heine-Borel theorem), or you assume that $f$ is unbounded, construct a sequence $(x_n)$ such that $f(x_n)\geq n$ for every $n$ , apply the Bolzano-Weierstrass theorem, and reach a contradiction.

I had also tacitly assumed that there is an algorithm for converting proofs of one kind into proofs of the other, though I had never actually tried to work out the details.

But recently, a colleague and I had a conversation that led to the following proof of the theorem, which disturbs my cosy view of how things work. The idea is to try to imitate the above proof by contradiction as much as possible, but without actually bothering to prove the result by contradiction. Specifically, one builds a sequence that is the most likely sequence to cause trouble, and then proves that it does not cause trouble. Here is how the argument goes.

Let $S\in\mathbb{R}\cup\{\infty\}$ be the supremum of $\{f(x):x\in[0,1]\}$ . By the definition of a supremum, we can find a sequence $(x_n)$ such that $f(x_n)\rightarrow S$ . Pick a convergent subsequence $(y_n)$ , by Bolzano-Weierstrass. Then $(f(y_n))$ is a subsequence of $(f(x_n))$ , so $f(y_n)\rightarrow S$ . But if $y$ is the limit of the sequence $(y_n)$ , then $f(y_n)\rightarrow f(y)$ . So $S=f(y)$ . So $f(y)$ is an upper bound for $f$ . (Note that this proof also shows that the bound is attained.)

There seems to be no contradiction involved. But again, if we dig a little deeper it starts to look as though what is really going on is that the contradiction is hidden in the “obvious” steps of the proof. For instance, how do we know that we can find a sequence $(x_n)$ such that $f(x_n)\rightarrow S$ ? We’ll need to split into two cases (unless we want to define the topology we are implicitly putting on the extended real line). The case where $S\in\mathbb{R}$ is not really worth investigating, since it instantly gives us that $f$ is bounded (though it was by unnecessarily doing this step that we obtained the added information that $f$ attains its upper bound). And if we then look at the case $S=\infty$ , how is what we are doing any different from assuming that $f$ is unbounded? I find myself rather confused.

Final remarks.

One thing that seems to be coming out of these examples is that the notion of a proof by contradiction is relative to the definitions you use and the small results that you take for granted. For instance, I could define a number to be irrational if its continued-fraction expansion is non-terminating. I wouldn’t actually advocate doing that, but if one did, then the “direct” proof I gave of the irrationality of $\sqrt{2}$ would be just that — direct. And if I do not allow myself to assume that $|f(y)-f(x)|\leq \|f'\|_\infty |y-x|$ then the proof that $|\sin(x)-\sin(y)|<\delta$ whenever $|x-y|<\delta$ appears to stop being direct and require a contradiction.

In which case, perhaps the advice that I give to students — proof by contradiction is a very useful tool, but try not to use it unless you really need it — is, though not completely precise, about the best one can do.

This entry was posted on March 28, 2010 at 3:59 pm and is filed under Somewhat philosophical. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

64 Responses to “When is proof by contradiction necessary?”

Terence Tao Says:
March 28, 2010 at 4:21 pm | Reply
Nice post, as always 🙂

One can use the continued fraction expansion of $\sqrt{2}$ to give a constructive algorithm to solve the equation $(p - \sqrt{2} q)x = 1$ with an $x$ which is guaranteed to be well-defined (basically, x will be another continued fraction, in which all denominators can be shown to be non-zero). Once one can solve $(p-\sqrt{2} q)x=1$ and $(p+\sqrt{2} q)x=1$ , one can of course solve $(p^2-2q^2)x=1$ , though it is amusing that this proof of a purely rational fact proceeds using the reals (via continued fractions). Though it may be possible to terminate the continued fraction after a finite time and make this a purely “rational” proof as well (though this may require an infinite descent, leading to another way for proof by contradiction to sneak in).

At some point one has to use the fact that the sum of two positive numbers is positive (and thus has a reciprocal), but if such a statement falls under the category of “proof by contradiction” then really there’s no escaping that category. There may also be subtleties in the construction of the real numbers, and the demonstration that every continued fraction converges to a real number.

For me, the purest examples of proofs by contradiction are those of the “non self-defeating object” type, where the existence of an overpowered object is crucially needed to demonstrate the non-existence of said object. See my post at

The “no self-defeating object” argument

Even in those cases, though, one can often extract a large component of the argument which does not involve proof by contradiction (Euclid’s theorem on the infinitude of primes being a good example of this).
- Terence Tao Says:
  March 28, 2010 at 5:10 pm
  Actually, I just realised that the proof I had in mind that the algorithm to solve $(p - \sqrt{2} q)x =1$ terminates relies on infinite descent, which of course uses contradiction. But… one can take contrapositives and prove the solubility of, say, $(p^2-2q^2)x=1$ by strong induction and a division into cases instead. Indeed, if p is odd, or if p is even and q is odd, then $p^2 - 2q^2$ is either odd, or twice an odd number, in which case solubility is clear; and if $p,q$ are even then one can appeal to the strong induction hypothesis.
  
  The division into cases would be problematic if one were to adopt an intuitionistic stance on logic, though. (I believe that one can still prove irrationality of sqrt(2) intuitionistically, but now proof by contradiction is definitely required.)
- Ben Lund Says:
  April 29, 2010 at 3:41 am
  Following Gowers’ logic above, you still need a contradiction to prove the irrationality of sqrt(2).
  For any rational number a, $(p^2 - a^2q^2)x = 1$ is soluble. This is not the case for $a^2=2$ , so $\sqrt(2)$ is irrational.
porton Says:
March 28, 2010 at 4:36 pm | Reply
Field medalist Gowers, it is really simple indeed.

A direct proof “A1 => A2 => … => An” is equivalent to proof by contradiction “not An => not A(n-1) => … => not A1”.

What is more natural depends on what statements are more natural “Ai” or “not Ai”.

No philosophy.
- gowers Says:
  March 28, 2010 at 4:39 pm
  Er … thanks.
- kazek Says:
  March 29, 2010 at 9:52 am
  Axiom1: “X={A,B,C}”
  Axiom2: “[ (s =A) or (s= B) or (s = C) ] => p(s)”
  
  A1= “s=A”
  A2= “p(s)”
  
  A1=>A2 (axiom 2)
  
  not A1 = “not (s = A)” or equivalent not A1 = “s=/= A”
  not A2 = “not p(s)” ( if s=B then s=/=A and p(s) is still true).
  
  So as things are different at least from that You wrote.
- kazek Says:
  March 29, 2010 at 10:49 am
  Last sentence should be: “So things are different at least from that You wrote.” I suppose You are saying that proof by contradiction and direct are equivalent, and that is true, but a way You describe equivalence is probably not correct.
- daniel. Says:
  April 16, 2010 at 10:18 am
  You are thinking of ‘contrapositive’ and not contradiction.
  
  sincerely, non-Fields medalist nobody.
Qiaochu Yuan Says:
March 28, 2010 at 5:07 pm | Reply
As far as exercises in classes go, I’ve found it most natural to use proof by contradiction if the statement I want to prove is universally quantified, since its negation is an existential statement. I can then use the object the existential statement gives me to “power up” my proof in a way that a “direct” proof (checking that some condition really does hold everywhere) cannot do, at least as easily. I think I’ve heard similar sentiments expressed somewhere; maybe MO.

As far as the larger question at hand, if “proof by contradiction” means “using the law of the excluded middle” then the problem is, as you say, that many definitions commonly in use in mathematics are equivalent only if the law of the excluded middle is assumed. Without it one must make some extra choices, and then one can ask what is provable in intuitionistic logic and what is not. (Or something like that.)
- gowers Says:
  March 28, 2010 at 6:28 pm
  What I’m looking for is a way of recognising in advance which statements are best tackled by contradiction. I don’t think your suggestion captures it — there are just too many counterexamples. For example, suppose I need to prove that there is no smallest positive real number. Then I am proving that for every positive real number there is a smaller one. If I followed your advice, the proof I would write out would go like this.
  
  1. Suppose the result is false, and let $x$ be the smallest positive real number.
  
  2. The number $x/2$ is positive and smaller than $x$ .
  
  3. But this contradicts the assumption that $x$ was the smallest positive real number.
  
  It seems to me more natural to say this.
  
  1. Let $x$ be a positive real number.
  
  2. Then $x/2$ is positive and smaller than $x$ .
  
  The point in this example is that the assumption that $x$ is the smallest positive real number is of no help in finding a smaller positive real number. I think a sensitivity to something like that should be part of the general principle I am looking for.
  
  Another example is this: prove that the product of any four consecutive integers is divisible by 24. Contradiction doesn’t come into it. One can either argue that $n(n-1)(n-2)(n-3)/24$ is the binomial coefficient $\binom n4$ , or one can argue that the set $\{n-3,n-2,n-1,n\}$ must contain at least one multiple of 4, one other even number, and one multiple of 3. (Of course, as above it may be that justifying these further facts eventually requires contradiction to prove some very low-level assertion.)
- Qiaochu Yuan Says:
  March 29, 2010 at 6:57 pm
  Hmm. Maybe I should give an example and leave the extraction of the general principle to others. Here’s a typical example of when I found it useful to negate statements in topology.
  
  Proposition: Suppose a topological space $X$ has the property that every open cover has a finite subcover. Then closed subsets of $X$ with the finite intersection property have non-empty intersection.
  
  Proof. Suppose that $X$ has the first property but not the second. Then there exists a collection $X_{\alpha}$ of closed subsets of $X$ with the finite intersection property with empty intersection. The collection $X - X_{\alpha}$ is then an open cover of $X$ , so it admits a finite subcover, but this contradicts the finite intersection property.
  
  Maybe it’s equally easy to phrase this proof without the use of contradiction and I am missing something. But the hypotheses don’t seem to match up as nicely if you don’t use contradiction.
- Qiaochu Yuan Says:
  March 29, 2010 at 7:02 pm
  Ah, I am missing something: the statement I wrote above can be proven directly by using the complement of the intersection to build an open cover. Let me see if I can find an example with more quantifiers…
Tom Ellis Says:
March 28, 2010 at 5:31 pm | Reply
“It’s utterly obvious because if it has a terminating continued-fraction expansion then you can just work out what rational number”

Am I missing something, or did you mean the converse here?
- gowers Says:
  March 28, 2010 at 5:55 pm
  Whoops — no, that was my mistake. I’ll change it right away.
Joshua Green Says:
March 28, 2010 at 5:32 pm | Reply
In your first example “Suppose that the sequence (a_n) is not convergent. Then … a few lines of calculation … which implies that a_n\rightarrow a. Contradiction.” it isn’t necessarily the case that the first and last lines can be removed, as that first line might be necessary for one of the implications along the way. On the other hand, it is often the case that the last line can be dropped, replaced instead by a contradiction with the line before. Terence Tao points out my favorite example of this, Euclid’s proof of the infinitude of primes, where arguably the final contradiction is with the Fundamental Theorem of Arithmetic but many people use that theorem to instead derive a contradiction with the opening statement.
- gowers Says:
  March 28, 2010 at 5:59 pm
  I’d be inclined to say that the assumption that $(a_n)$ fails to converge is rather unlikely to be helpful in proving that $a_n\rightarrow a$ . The main point is that I really have seen proofs written by students in which it really is the case that the initial “Suppose not” and final “contradiction” can be crossed out with no loss to the argument.
Emmanuel Kowalski Says:
March 28, 2010 at 7:37 pm | Reply
In the proof of irrationality of sqrt(2), I find it interesting to see how it enters in a proof of the a priori stronger, and “direct”-looking, statement that gives a positive lower-bound for $|\sqrtt{2}-p/q|$ for any integers $p$ and $q$, as a function of $q$. This is a special case of Liouville’s inequality, and the idea is to compare an upper bound for $|f(p/q)|=f(\sqrt{2}-f(p/q)$, where $f(x)=x^2-2$, which comes from the mean-value theorem and involves $|\sqrt{2}-p/q|$, with a lower bound coming from the fact that $q^2f(p/q)$ is an integer, which is non-zero… because $\sqrt{2}$ is not rational.
Klas Markström Says:
March 28, 2010 at 8:37 pm | Reply
This is certainly biased due to my own way of thinking about things but I have found that proofs by contradiction are often another way of stating a construction algorithm for an object with given properties . E.g. the proof by contradiction for the infinitude of primes can be turned into an algorithm which constructs an infinite list of primes. The proof of the four colour theorem is another proof by contradiction, which can be turned around and made into a polynomial time algorithm for constructing a four-colouring of a planar graph.
- Mark Bennet Says:
  March 28, 2010 at 10:40 pm
  The Four Colour Theorem is an interesting example – it is necessary to prove that the algorithm for four-colouring works for all planar graphs, and this seems to me to be done by contradiction? [Any planar graph must contain one of a finite list of special subgraphs, find such a subgraph and you can reduce your problem to a smaller case. And to prove it contains one of the subgraphs – assume it doesn’t and establish a contradiction]
  
  Fermat’s method of descent can be structured to use contradiction in a similar way to many approaches to 4CT – by assuming a minimal counterexample and then showing that there must be a smaller one – contradiction. There are alternate proofs of results proved by this method – but now I’ve been tuned to see contradiction where I didn’t expect it, I can’t confidently cite one where the alternative is definitely positive.
Sobre las demostraciones por contradicción Says:
March 28, 2010 at 10:49 pm | Reply
[…] publicado en su blog una reflexión sobre las demostraciones por contradicción. Se los recomiendo: When is proof by contradiction necessary? Clase: Matemáticas | Etiqueta: […]
Arnaud Spiwack Says:
March 29, 2010 at 12:21 am | Reply
I’m not quite sure, but when I read the sentence: “How can one statement be stronger than an another, equivalent, statement?”. It seem to me that you want to know more about constructive mathematics.

Also it seems that by “proof by contradiction” you mean two things that are logically rather different. First that too prove that ¬a, it suffices to prove a contradiction while assuming a (dubbed “negation introduction”). The second is that ¬¬a → a (or ¬(¬q→¬p)→(p→q), equivalently) (dubbed “double-negation elimination”). Now, the latter is not a valid principle in constructive mathematics (it is equivalent to the principle of excluded middle). This results in having a way to prove negated formula, but no real way to use them to prove stuff (apart from contradiction, basically). Consequently definition formulated as negative are quite weak, compared to a classically equivalent definition that would be “all positive”.

Now that means that constructive mathematicians avoid negative definitions as much as possible. I would recommend reading Errett Bishop’s book : Foundations of constructive analysis — which is, unfortunately out of print, and rather hard to find second-hand. He develops a rather significant amount of analysis without ever resorting to a proof by contradiction of the second kind, and little, if any, of the first kind.
- gowers Says:
  March 29, 2010 at 8:27 am
  Undoubtedly whether or not a proof is constructive is closely related to whether or not it relies on contradiction in an essential way. But my question is a less formal one: I want to know how an ordinary mathematician who doesn’t mind non-constructive proofs can look at a statement and recognise that a proof by contradiction is more or less forced. It sometimes happens that one proves a result by contradiction and then realizes that it is quite easy to prove all the contrapositives of the steps. Is there some way of recognising in advance that this is going to be the case?
  
  Even at the informal level, it may well be that thinking about whether one can prove something constructively will be relevant, as Terry showed in his comments above.
  
  I can see though that it’s quite likely that my informal question cannot be made formal and answered except in more or less the way you indicate.
- Arnaud Spiwack Says:
  March 29, 2010 at 11:12 am
  Well, I doubt it can be made formal, because different people might put the limit of what is reasonably “forced” to be proved by contradiction. My guess was something like: maybe reading some constructive-intensive mathematics can help one make up his mind. Especially regarding whether this or that definition should contain a negation.
- Andrej Bauer Says:
  March 29, 2010 at 4:05 pm
  I think what Arnaud is saying is that you are calling two things “proof by contradiction” when only one of them deserves this name. If you are trying to prove a negation of a statement then what you call “proof by contradiction” is unavoidable in a certain sense (there are meta-theorems in logic about this). If you are proving a statement which itself is not a negation by assuming its negation and getting to a contradiction, then very likely you can find a direct proof. For example, your Bolzano-Weierstrass example has a direct proof. It’s to long to be posted here, but I wrote a blog post which explains all this more carefully and contains the proof at http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/.
- gowers Says:
  March 29, 2010 at 5:21 pm
  I’ve just read your blog post and found it very interesting. And I perfectly fit your paradigm of somebody who was unaware of the difference between proof by negation and proof by contradiction. I’ll try to heighten my awareness from now on. (In fact, your analysis of why I wrote what I wrote was spot on all the way through: I’m so used to cancelling out double negations that I didn’t really appreciate the significance of what Arnaud was saying.)
  
  Two small further remarks. The constructive proof you gave of the boundedness of continuous functions on [0,1] was essentially the same as one that my colleague came up with, and the argument in my blog post was a different argument that I produced in response.
  
  Finally, with reference to your comment about countable choice, one could obtain the sequence by imitating the proof of the intermediate value theorem: for each $n$ one wants to find $x$ such that $f(x)\geq n$ , so one lets $A_n$ be the set of all such numbers and takes $x$ to be the infimum of $A_n$ ; one then checks, using the continuity of ${}f$ , that $f(x)=n$ .
- Andrej Bauer Says:
  March 29, 2010 at 5:39 pm
  Your suggestion for eliminating countable choice works very well classically. Intutitionistically there is trouble (how do you know these infima exist?) so people who usually worry about choice (namely constructive mathematicians) don’t think of such tricks. Anyhow, I think my blog was not explicit enough, so I’ll reiterate my answer to your question: proofs of negation cannot be eliminated, except via previously proved lemmas which eventually reduce to a proof of negation. Proofs by contradiction can almost always be eliminated (in analysis), except for some well-known theorems that are equivalent to (weak forms of) excluded middle.
- Kenny Easwaran Says:
  April 10, 2010 at 11:15 pm
  When I started reading the post I was going to make a point similar to Andrej Bauer, that when a statement begins with a negation, then negation-introduction is going to be necessary.
  
  But in the original post, I think Tim Gowers raises some issues that make this characterization a bit problematic – whether or not the formal version of an informal statement begins with a negation depends on how you formalize it. Statements with strict inequalities look like positive statements, but are often equivalent to negated equations. I suppose constructivists/intuitionists (I’m not always clear on the distinction) avoid this worry by allowing that $x\neq 0$ and $x>0\textrm{ or }x<0$ are not equivalent statements. So a classical mathematician can't just use this particular distinction.
  
  I think instead the phenomenon of interest has to be about the informal proofs (which mathematicians actually use), and not the formalized counterparts (which logicians study). There's something displeasing about using proofs by contradiction in certain contexts, but often it can only be eliminated by using some lemma that hides it, or by mutilating the proof in some worse way. I'm not certain if there's any way to characterize the set of statements whose proofs will be like this. (I suppose in some sense, this problem seems like it might be strictly harder than characterizing the set of statements that are provable at all, which is of course impossible given the formalized notions of "characterizing" and "provable".)
- Zed Norwood Says:
  October 12, 2011 at 4:14 pm
  Andrej: Would you mind indicating what meta-theorems you’re referring to in your first reply to this comment?
  
  Sorry to resurrect an old conversation.
- andrejbauer Says:
  October 12, 2011 at 4:52 pm
  @Zed: what I have in mind is the theorem which states that in the intuitionistic propositional calculus proofs can be converted to normal forms (eliminations followed by introductions). You can understand a normal form proof as “optimal and direct” in the sense that it has no unecessary steps and does not use any lemmas. Because “not A” is the same thing as “A implies false”, the normal form proof of a negation is of the form “assume A then prove false”.
porton Says:
March 29, 2010 at 12:24 am | Reply
You ask: “How can one statement be stronger than an another, equivalent, statement?”

Consider an algorithm (with or without the requirement that it terminates on every input) which proves a class of mathematical theorems.

The we can define the statement A to be stronger than B if (A=>B) can be proved by this algorithm.
Sam Says:
March 29, 2010 at 12:05 pm | Reply
I think the reason why it is so difficult for a mathematician to recognise a priori that a proof by contradiction is forced, is that it is even difficult a posteriori, after writing down the proof, to recognise whether or not a proof “really”, “essentially” is a proof by contradiction.

So I think a question that needs to be answered prior to the one you are posing here would be: what are the conditions a proof has to satisfy in order for it to be called “a proof essentially by contradiction”?
S Says:
March 29, 2010 at 2:00 pm | Reply
The approach I take is usually “Which direction has more information?”, or rather, “Which approach gives me more to work with?”.
Proof of negation and proof by contradiction « Mathematics and Computation Says:
March 29, 2010 at 4:00 pm | Reply
[…] have been meaning to write for a while. It was finally prompted by Timothy Gowers’s blog post “When is proof by contradiction necessary?” in which everything seems to be called “proof by […]
DC Says:
March 30, 2010 at 3:47 am | Reply
Ignoring formal mathematics, this is a thorny pedagogical issue. We develop intuition for how proofs of statements of various “kinds” will “go,” and want to transmit it to students— but much of what we experience as “intuition” is really hindsight.

The heart of any tip of the form “If your theorem is like [blank] then try a proof by contradiction, and otherwise don’t” is not the blank, but the word “theorem.” We ask students to find proofs of statements that are known to be true— and known to have proofs using what we have taught them. This is often more significant than anything specific to the phrasing of a statement being proved. Surely, sometimes we deliberately phrase a statement so that it conveys information about a proof (e.g. “prove that the polynomial x^2 – 2 has no rational roots” may suggest a classroom theorem), but in general, this information is not explicit— making the relevant connections is part of the student’s job. Make enough of these connections, and you develop intuition… or is that hindsight?

What does your intuition say about a proof of “the Euler-Mascheroni constant is irrational”? Just to speak of a proof, we need to know more than we know.

This seems bound up with the meta-mathematical issue of “knowing something is true” versus “having a proof”. These are certainly different concepts in the classroom: I can know Liouville’s theorem is true, but not remember any proof during an exam. Outside the classroom it is harder to say what the difference is. It is the basis of a very unfunny math joke.

Q: What’s the best way to start a proof of X?
A: Know that X is true.
Jonathan Vos Post Says:
March 31, 2010 at 6:51 pm | Reply
I remembered Feynman telling me the last quote here, and googling it I saw this nice page:

http://infoproc.blogspot.com/2006/12/keynes-and-planck.html
Found in the comments on Economist’s View:

“Professor Planck, of Berlin, the famous originator of the Quantum Theory, once remarked to me that in early life he had thought of studying economics, but had found it too difficult! Professor Planck could easily master the whole corpus of mathematical economics in a few days. He did not mean that! But the amalgam of logic and intuition and the wide knowledge of facts, most of which are not precise, which is required for economic interpretation in its highest form is, quite truly, overwhelmingly difficult for those whose gift mainly consists in the power to imagine and pursue to their furthest points the implications and prior conditions of comparatively simple facts which are known with a high degree of precision.” (Keynes, Essays in Biography 1951 158n)

It’s true: powerful mathematical minds are not necessarily comfortable with the messiness of the real world. This observation might be applied as well to string (or more formal or mathematical) theorists vs theorists who are more data- or intuition-driven (often called phenomenologists, in a terrible use of terminology). Of course, some people (like Feynman, although he wasn’t very mathematical by today’s standards) are good at everything…

“We know a lot more than we can prove” — Feynman.

Posted by Steve Hsu
John Says:
April 1, 2010 at 4:37 am | Reply
Your final comments resonate with some of my own informal observations – it depends on what kind of objects and statements you are working from.

For example, like I think you were saying, it seems that you can `bundle’ some of the non-constructive or inherently `negative’ aspects into definitions and give direct proofs based on these definitions, while different definitions might require a `negative’ proof, given the definitions you are using.

In practice, I sometimes like to think about contradiction as about consistency and elimination of alternatives, usually arising when you think, `this MUST be true, because it can’t not be’ vs `this IS true because I know this’. Whenever you feel like saying `MUST’ you might think about contradiction.
- John Says:
  April 1, 2010 at 4:43 am
  Or `MUST not be true because if it was…’
- gowers Says:
  April 1, 2010 at 11:31 am
  I like that “must” test. I’ll try it out on a few examples and see whether it seems to work.
fan Says:
April 1, 2010 at 10:26 pm | Reply
In graph theory the easiest way to get your induction right is a proof by contradiction. Rather than trying to figure out in what ways small graphs can extend to bigger ones (messy and error-prone), you grab a “smallest counterexample”.
Anonymous Says:
April 2, 2010 at 1:29 am | Reply
As a non-mathematician can I ask why proof by contradiction is so disliked? I get that it would seem to be inherently non-constructive and that might annoy some people. I suppose if you arrive at a contradiction you know that something is wrong – but is it necessarily the thing you were trying to disprove, or is the the problem with the method of proof/disproof? Perhaps equally you might be suspicious of a direct constructive proof as it could be an accident of flawed logic or other false assumptions?
Getting to know your math tools. « Math Society the club Says:
April 2, 2010 at 3:28 pm | Reply
[…] Getting to know your math tools. Timothy Gowers is a Fields Medal winner who writes a blog about math. He has written a post asking “When is proof by contradiction necessary?” […]
Paulo Oliva Says:
April 14, 2010 at 10:32 am | Reply
Two points. First, in [R. L. Goodstein, Proof by reductio ad absurdum. The Mathematical Gazette, Vol 32, No. 300, pp 198-204, 1948] the same issue of this blog is also discussed, and a proof that square root of 2 is irrational is given without using proof by contraction. The article is short and easy to read. Regarding the question “How can an ordinary mathematician look at a statement and recognise that a proof by contradiction is more or less forced?”, I would say, given my background in proof theory, that if the theorem states that an object x has property P(x), where P(x) is computer-checkable then proof-by-contradiction can normally be avoided. For instance, existence of infinitely many prime (object x in this case is a number, and P(x) says that x is prime and bigger than n), or square root of 2 being irrational (object x is an epsilon, and P(x) says that square root of 2 is away from p/q by that epsilon). In these two cases n and p/q are arbitrary parameters, which can be thought of as inputs. If, on the other hand, the theorem states that an object x with property P(x) exists but P(x) cannot be checked “computationally”, then you most certainly will only be able to prove the theorem via a proof by contradiction. For instance, in the case of the Bolzano-Weierstrass theorem, the object x is a real number, and the property P(x) saying that x is an accumulation point would require someone to check infinitely many possibilities. Another example is Brouwer’s fixed point theorem on [0,1] for instance, in this case x is a real in [0,1] and P(x) says that fx = x, which is an equality between real numbers that cannot be checked effectively by computer (think of how you would check two real numbers are the same, you might check digit by digit and never know). This is of course an informal answer to an informal question.
Anonymous Says:
April 19, 2010 at 4:29 am | Reply
I agree with Andrej and Paulo generally, the question you are asking is a natural question in foundations of mathematics and logic, and there is a difference between “Reductio ad absurdum” and introduction rule for negation. I just want to add three minor points.

About Andrej’s comment, in Intuitionistic logic, one is mainly concerned with true statement, therefore if you want to show something is false the only thing we can do is to show that by assuming it we can derive contradiction, i.e. it does not study how to refute a statement directly. There are statements that we can refute directly without going through this, example $0 \neq 1$. Similarly, to show that $\forall x, \varphi(x)$ is false we can give a specific $x$ such that $\varphi(x)$ is false. We don’t need to derive a contradiction form it. Intuitionistic logic is not symmetric with respect to true and false statements.

About Paulo’s comment, his trick work in many cases because computable mathematics is a model of constructive mathematics. But it is not faithful with respect to constructive reasoning, i.e. there are statements that hold in computable mathematics which can not be proven constructively. As a result, a statement can be both true in classical mathematics and computable mathematics, and still you may need to use proof by contradiction to derive it.

Finally, I want to emphasize the seemingly obvious but not trivial point that to prove a statement using proof by contradiction can be much easier than proving it without it.

If you are interested, I would suggest taking a look at Beeson’s book:
Foundations of Constructive Mathematics: Metamathematical Studies, Springer, Berlin/Heidelberg/New York, 1985.
It is a nice book, and it is not an ideological one so it should make sense to classical mathematicians.
- Andrej Bauer Says:
  April 19, 2010 at 5:51 am
  Dear Anonymous, your examples of direct refutations ($0 \neq 1$ and giving a counterexample to a universal statement) work intuitionistically just as well as clasically, and are frequently used in intuitionistic mathematics, just as in classical mathematics. If you boil them down to their formal proofs, you will discover however, that they (a) either rely on an axiom which has the form of a negation, such as $0 \neq 1$ in the theory of fields, or $n+1 \neq 0$ in Peano arithmetic, or (b) your “direct” method of proving a negation relies on a lemma of the form $A \implies \lnot B$ (for example $(\exists x, \lnot \phi) \implies \lnot \forall x. \phi)$) whose proof then contains a proof of negation.
  
  Your view of truth in intuitionistic logic is somewhat strange. What is “in intuitonistic logic one is concerned mainly with true statements” supposed to mean? I thought all mathematicians, no matter what party they belong to, are mostly concerned with true statements. The trouble is, we don’t know which one are true 🙂
  
  Anyhow I think this question is not about intuitionistic logic. It’s just that having practice with intuitinstic logic helps one distinguish various logical forms which classical mathematicians autoamatically view as “the same”.
- Anonymous Says:
  April 20, 2010 at 4:00 am
  Hi Andrej,
  
  In classical logic we have symmetry between truth and falsity, so the point I made does not effect it. Stating something is true is the same as stating its (classical) negation is false. This symmetry is broken in intuitionistic logic, if we need constructions for proving a statement is true, we can also have constructions to show that a statement is false. Of course if we don’t treat falsity similar to truth and formalize them as intuitionistic negation we will end up with what you said. But similar to the situation with true statements, we can have direct observations showing that a statement is false. To show that 2^2=5 is false, we can just compute 2^2 and get 4 and compare the normal forms of them to conclude that this statement is false, where as in intuitionism since falsity is replaced with intuitionistic negation, what we end up is that assuming 2^2=5 we derive 0=1 (and either define $\bot$ to be just $0=1$ or have an axiom that states $0=1 implies \bot$) and conclude with $\lnot 2^2=5$. Even a computer does not need to find a proof of contradiction from $2^2=5$ to claim it is a false statement. My point is there is a more natural way to establish that $2^2=5$ is false. This is a toy example but this holds in general, in place of coming up with a construction for $\lnot \varphi$ we can show directly $\varphi$ is false by giving a construction showing its falsity. “A white raven” is enough to show the universal statement “every raven is black” is false, there is no need to assume it and derive a contradiction. But for this to make sense one has to distinguish between falsity and intuitionistic negation, similar to the situation in linear logic.
  
  As far as I remember, the negation and falsity in intuitionism was considered problematic even by some pioneers (Gilevenko?).
Andrej Bauer Says:
April 20, 2010 at 6:51 am | Reply
I will reiterate, but then I hope we can close discussion because intuitionistic mathematics is not relevant to this post. You give examples of how a classical mathematician proves negations and that equations such as $2^2 = 5$ do not hold. But all of your examples and methods of proof are badly chosen because precisely the same methods work for the same reasons intuitionistically. I write papers in constructive mathematics, and I assure you we do not derive false every time we want to prove a negation. In fact, good math is written in such a way that it is largely irrelevant whether it is classical or intuitionistic.

If on the other hand we speak about formal proofs (without cut and in “normal form” as far as that is possible for classical math, so we cannot hide things inside lemmas), then proofs of negated statements will generally end with an introduction rule for negation, both in classical and intuitionistic mathematics. You speak of a symmetry in classical mathematics between truth and falsity, but even that symmetry has to be proved somehow, does it not? The rules of inference for negation (in natural deduction style) are the same classically and intuitionistically. The symmetry you speak of is proved for classical logic from the law of excluded middle. But the rules of inference come first, and they do not include the symmetry. (You can build the symmetry into the logic if you use classical sequent calculus, but that’s not how mathematicians write proofs.)
Bivek Says:
April 30, 2010 at 6:22 am | Reply
Hi there,

Why we use this proving technique?

General Application?

Thank you.
Some Mathematical Gifts « Gödel’s Lost Letter and P=NP Says:
December 20, 2010 at 2:40 pm | Reply
[…] that does not use “proof by contradiction.” See also Tim Gower’s interesting discussion on this and […]
Mike Says:
January 26, 2012 at 4:55 pm | Reply
I was just wondering, if you don’t get a contradiction when using a proof by contradiction, what does it mean?
I’m asking this question because in the books I’ve read so far, usually a counterexample was used to show that a proposition is false. But can we also use the proof by contradiction and not get a contradiction to show that the proposition is in fact false?
Thanks.
Anonymous Says:
February 29, 2012 at 4:27 am | Reply
According to his biography packet (available on Wikipedia) the late, great statistician David Blackwell was able to provide a positive approach to the proof of the irrationality of the square root of 2. Unfortunately, no details were provided.
Quora Says:
September 5, 2012 at 3:26 am | Reply
What is the most beautiful theorem proof, and why?…

Stephen: To answer “What specific advantages are there to viewing this as a constructive proof”, one answer is that it will no longer be a false statement, historically speaking (i.e., it will really be closer to “Euclid’s proof” rather than a lat…
How proof by contradiction differs of direct proof | Victor Porton's Math Blog Says:
February 26, 2014 at 4:03 pm | Reply
[…] famous mathematician Timoty Gowers asked this question: What is the difference between direct proofs and proofs by […]
Friday, February 28 | Discrete Mathematics Says:
February 28, 2014 at 5:09 am | Reply
[…] Check out the post on Gowers’ blog Is contradiction necessary? […]
Emi Says:
January 26, 2015 at 3:27 am | Reply
Reblogged this on Pathological Handwaving and commented:
Great post on Gower’s blog on when contradiction is appropriate.

The first comment by Tao lends additional considerations to the post with a reference to non self-defeating objects!
Jared Deckard Says:
April 28, 2015 at 12:37 am | Reply
I’m not sure “try not to use [proof by contradiction] unless you really need it” is the optimal conclusion. In “Meta Math”[1], Gregory Chaitin explores the question: “What makes a mathematical concept desirable?”

Simplicity was the solution. The best theorems seem obvious in retrospect, because they are reduced into relationships between existing concepts.

I would recommend trying all angles of attack when searching for a proof. If it starts to take too long or you hit a dead end, try a different angle. Even if you discover a proof, try your other opening moves, look for a more elegant solution.

I believe Wolfram Alpha converges on this solution by performing some sort of weighted, breadth-first search on the permutations of an equation.

I highly recommend “Meta Math”[1] if you are interested in theories about entropy and algorithms that generate proofs.

[1] (“Meta Math”, Gregory Chaitin, http://arxiv.org/pdf/math/0404335.pdf)
Anonymous Says:
April 28, 2015 at 1:43 am | Reply
I don’t like the conclusion that students should avoid proving by contradiction unless they really need it.

I almost always start with contradiction as my initial method of choice when taking exams because you don’t always have time to completely rewrite your proofs. Contradiction helps with this since it naturally encompasses proving by contrapositive also since if you’re trying to prove that p->q, you can assume p and ~q and getting to ~p is a contradiction since p^~p (which is also the same structure as a proof by contrapositive if you got to this line without assuming p). And of course if you find any other absurdities along the way sooner, you’re done quicker.

This is nice because a proof by contrapositive is more or less equivalent to a direct proof. So simply by always starting with proof by contradiction, you cover the cases where the theorem:
– is simple enough for you to find out exactly why it’s true (direct proof hidden in the contrapositive).
– is complex and wide reaching enough for you to hit an absurdity quickly
Greg Magarshak Says:
April 28, 2015 at 3:12 am | Reply
A proof by contradiction is essentially something like this:

Suppose B and ~A. Then… ~B. Therefore A.

But, we can express “If X Then Y” as “Y Or ~X.” So the above proof can be expressed as:

A Or ~(B Or ~(B and ~A))
=
A Or ~(B Or (~B Or A))
=
A Or ~((B Or ~B) Or A)
=
A Or ~A
=
True

If we work backwards we are basically saying:

Exactly one of A or Not A is true.

Not A is not true because of the contradiction with help of B, namely the argument for “contradiction” is:

~(B Or ~(B and ~A))

Therefore A is true.
But you can always trace the introduction if B through the (B or ~B) term and logical operations.

And the other way is trivial: if you show that A is true given some assumptions B, C, …, which don’t depend on A, then assuming A is false leads to a contradiction, since B, C, … are still true and the same argument implies A is true. Which is a contradiction.

Thus you can always transform between the two forms of proof.
Sakunthala Panditharante Says:
April 28, 2015 at 3:30 am | Reply
My intuition – proof by contradiction means we have to use one step that inverts the set of values for which the statement is true – so whether we need a contradiction step depends on the cardinality of this truth set. Perhaps it depends on the relationship between the ‘truth set’ of our premises and our conclusions (e.g. the square root of 2 is one number, but all of the rationals is infinite)

Supporting this intuition, getting rid of proof by contradiction leaves us unable to construct uncountable sets. Maybe some proofs need several contradiction steps (i.e., when their truth set cardinality is aleph-2,3, etc.)
Descending Proofs Into Algorithms | Gödel's Lost Letter and P=NP Says:
August 29, 2016 at 1:13 am | Reply
[…] gave a proof by induction in a post some years ago, where we also noted a MathOverflow thread and a discussion by Tim Gowers about this […]
Personal Development Leadership Skills Says:
February 5, 2021 at 3:04 pm | Reply
Personal Development Leadership Skills

When is proof by contradiction necessary? | Gowers's Weblog
AL Says:
March 7, 2021 at 8:47 pm | Reply
For me, the thought that drives the choice of using proof by contradiction resembles that of opting to use the 1-Pr[none of …] instead of the direct Pr[at least one of…]. The reasoning is usually quite similar — the direct proof has too many options to consider, whereas the indirect proof doesn’t. Hence, proof by contradiction is useful when the direct method requires the consideration of too many options.
For the Sake of Argument – Math Solution Says:
March 10, 2022 at 11:33 am | Reply
[…] In fact (!), proving √2 is irrational does NOT require proof by contradiction, as you have claimed; you can do it by finding the continued fraction of √2. […]
can't stop thinking about My ex Says:
November 5, 2023 at 9:53 am | Reply
can’t stop thinking about My ex

When is proof by contradiction necessary? | Gowers's Weblog
Anonymous Says:
February 16, 2024 at 6:28 pm | Reply
You are right. If done that way, then there is no contradiction:
* There are two possible cases.
* In either case there is a sequence $f(x_n )\to S$
* Calculation shows that S must be finite.

The proof by contradiction eliminates one of the two cases, whereas what you did considers both cases and then constructively shows which applies.