44
$\begingroup$

In a proof by contradiction, how do we know the assumption is the cause of the contradiction? And not just the result of some other property more fundamental to numbers?

In other words, how can we be sure we arrived at the contradiction because of the proposition $P$ we assumed, and not because of some other proposition $Q$ we are not even aware of?


The answer that comes in mind is "Well, if there were some proposition $Q$ causing the contradiction, then it should also manifest in the event of $ \neg P$."

Is it this straightforward or there's more to it? What if the proposition $Q$ can only manifest in the event of $P$, and not at all in the event of $\neg P$?

Sorry if this is nonsense - just trying to clear out some confusions.

$\endgroup$
  • 13
    $\begingroup$ If you don't truly know if the the proposition Q is true, maybe you shouldn't be using it in your proof in the first place. $\endgroup$ – Doughnut Pump Oct 6 '17 at 22:35
  • 5
    $\begingroup$ If you read Wikipedia Proof by contradiction you see that the proof method depends on the Law of the excluded middle and that is one reason it is objectionable by some mathematicians. Your question is a very important one which is easily "swept under the rug". You are justified in questioning the method. $\endgroup$ – Somos Oct 7 '17 at 1:00
  • 4
    $\begingroup$ @Somos: Proof by contradiction does not rely on the law of the excluded middle: it only requires the law of noncontradiction. The invocation of the law of the excluded middle that is often associated with a proof by contradiction is about proving a proposition from its double negation. $\endgroup$ – Hurkyl Oct 7 '17 at 4:44
  • 1
    $\begingroup$ Athough what Hurkyl said above is true for some definitions of "proof by contradiction", the typical variant that mathematics students encounter in textbooks and classes are actually of the form "$\neg A \to \bot \vdash A$", which does require LEM (the law of excluded middle) to justify fully. Hence I think the link I've provided will give a fuller answer to your question. $\endgroup$ – user21820 Oct 7 '17 at 7:37
  • 1
    $\begingroup$ @Somos In both cases, you are often going to have difficulty checking the correctness of a given statement (if you could just "check" the correctness of the statement you are trying to prove, why would you need to prove it?). You can only check that each statement you are making is properly justified by the assumptions you have made. $\endgroup$ – Morgan Rodgers Oct 7 '17 at 22:05
35
$\begingroup$

In mathematics, we deduce theorems from axioms, so we end up knowing that the theorems are true in any situation where the axioms are true. We get no information about situations where some of the axioms are false.

Now suppose we prove a theorem T by contradiction; we assume not-T and, by means of this assumption plus our axioms, we arrive at a contradiction. Then we know that either not-T is false or (at least) one of our axioms is false. That knowledge is exactly the same as knowing that if the axioms are true, then not-T must be false and therefore T must be true. If, on the other hand, some of the axioms are false, then we get no information.

So the information we get from the proof by contradiction is the same as what we'd get from a direct proof: As long as the axioms are true, we know T; if some axioms are false, all bets are off.

$\endgroup$
  • $\begingroup$ I'm not fully sure I understand what you mean by 'false' axioms. Isn't an axiom by definition true, and so all statements deduced from them are also true in the system formed by the axioms? I'm not sure I understand what is a 'false' axiom. $\endgroup$ – Stephen Oct 6 '17 at 22:56
  • 4
    $\begingroup$ @Stephen One of the usual axioms about the natural numbers is that $0$ is not the immediate successor of anything. If someone were to take theorems about the natural numbers and claim that they're also true about the real numbers, I'd tell him that he's wrong because that axiom, true of the natural numbers, is false of the real numbers. More generally, axioms are (barring errors) true in the situation that they're intended to describe, but they can be false in other situations. $\endgroup$ – Andreas Blass Oct 6 '17 at 23:28
  • 4
    $\begingroup$ Would it be more correct to say that the axioms are inconsistent than to say that they're false? $\endgroup$ – templatetypedef Oct 7 '17 at 1:14
  • 6
    $\begingroup$ @templatetypedef No. Consistent axioms, like the standard axioms about $\mathbb N$, can be false when one attempts to apply them to other contexts like $\mathbb R$. If the axioms were inconsistent, they'd be false in all situations. $\endgroup$ – Andreas Blass Oct 7 '17 at 1:32
  • 1
    $\begingroup$ @yo' I assume that by "we do not know" you mean something like "we cannot prove, on the basis of those same axioms," so that your comment is justified by Gödel's second incompleteness theorem. If we consider other means of knowing things, the justification is a lot weaker. For example, a clear intuition of the cumulative hierarchy may well allow us to know that ZFC is consistent. $\endgroup$ – Andreas Blass Oct 7 '17 at 13:36
6
$\begingroup$

This post explains the intuitive justification that the technique of proof by contradiction is valid. Hence I think it addresses one aspect of your question. But I wish to point out an additional aspect that closely resembles your question. Suppose we have the following proof structure:

  If $P$:

    If $Q$:

      ...

      Contradiction.   [Suppose we can deduce this. Is it 'because of' $Q$ or $P$?]

    $\neg Q$.   [Is this a valid deduction? I will explain below why it is!]

It is valid to deduce $\neg Q$ under the outer assumption of $P$, as shown above. Why? As explained in the linked post, all our deductive rules are designed to be truth-preserving, namely that every sentence we can deduce is true in its context (including the assumptions it is under). Therefore we cannot deduce a contradiction except in an impossible context. Now in the above proof structure it must be that it is impossible for both $P$ and $Q$ to be true, but from the given structure we cannot determine which is not true. This is exactly like what you are asking in your question! Nevertheless, the last deduction above is valid because under assumption that $P$ is true, it is impossible for $Q$ to be true too and hence $Q$ must be false.

It could very well be that $Q$ is actually true but $P$ is the false nonsense that allows you to deduce a contradiction under the assumptions of both $P$ and $Q$. Despite that, whatever we said above is still correct! Why? Well if $P$ is false, then what we can deduce under assumption that $P$ is true is irrelevant, because we are not deducing a sentence that is false under no assumptions.

For programmers, you can think of each sentence as an assert statement, and each "If" context-header as an if-construct. The very fact that our deductive rules are truth-preserving implies that every proof we write following our deductive rules is one that does not make any assertion error. Thus if we manage to prove a contradiction somewhere, it implies that when you run the proof as a program it will never reach that assert statement! So let us look at the above proof structure again. The only way you can reach the last statement is if $P$ is true, in which case $Q$ must be false since we cannot reach the "Contradiction" assertion. So when we reach $\neg Q$ we are indeed correct to assert it. The other possible situation is that $P$ is false, in which case we never even run all the statements under it, so it does not matter that we have made some assertions under it!

Finally, I want to just point out that it is not always the case that only one of our assumptions is the 'cause' when we can deduce a contradiction. Consider the following valid proof structure:

  If $P$:

    If $\neg P$:

      Contradiction.   [Who 'caused' this?]

    $\neg \neg P$.

$\endgroup$
  • $\begingroup$ This was helpful. My knowledge in logic is quite limited though, so a quick one; isn't ¬¬$P$ $ $ just $ $ $P$? $\endgroup$ – Stephen Oct 7 '17 at 23:25
  • $\begingroup$ @Stephen: In classical logic, yes. But in other logics, like minimal logic or intuitionistic logic, that might or might not be the case. $\endgroup$ – hoffmale Oct 8 '17 at 5:33
  • $\begingroup$ @Stephen For a quick example of why it's not instantly obvious that $\neg \neg P = P$: "I'm not unhappy to see you" isn't the same thing at all as "I'm happy to see you". $\endgroup$ – Patrick Stevens Oct 8 '17 at 7:09
  • $\begingroup$ @Stephen: As hoffmale said, they are equivalent in classical logic, since negation simply flips the truth value, so double negation does nothing. In any case, that last example was merely to show that a contradiction can be 'caused' by the current assumptions being impossible in conjunction, rather than necessarily being due to some single wrong assumption. That's why I think my answer best addresses your question, since we often do proof by contradiction within some context under some other assumptions, yet it's valid to conclude the negation of the innermost assumption. $\endgroup$ – user21820 Oct 8 '17 at 11:01
  • $\begingroup$ @Stephen: You may be interested in this post about some statements that can't have a boolean truth value (scroll to the part about Quine's paradox). In most modern foundations for mathematics, such statements are impossible to make, and so that is why we can still afford to have LEM in modern mathematics. But if we want to permit this kind of statements, then we can't have LEM for them. $\endgroup$ – user21820 Oct 8 '17 at 11:14
3
$\begingroup$

A proof by contradiction relies on the fact that ($P$ and not-$Q$) is the negation of ($P$ implies $Q$). The law of the excluded middle, along with the law of noncontradiction, gives that exactly one of these two statements is true, so if ($P$ and not-$Q$) leads to a contradiction it must be a false statement, and therefore ($P$ implies $Q$) is true. Note that if you obtain a contradiction that is unrelated to your assumption of ($P$ and not-$Q$) then you have shown that the universe you are working in is inherently contradictory, we usually like to think that that is not the case.

I would like to mention that the idea that the "law of the excluded middle" is controversial is... perhaps overrepresented in some parts of the internet compared to the opinions you would encounter among mathematicians. I would challenge you to try to, on your own, come up with a mathematical statement such that neither the statement nor its negation is true (or where both are true). I won't hold my breath.

$\endgroup$
  • $\begingroup$ You misrepresent the most common view against the law of the excluded middle, which is not that it is not true, but rather that it should not be considered provable. Good arguments for this include that (1) LEM is usually not necessary (most theorems can be proven constructively); (2) even if that fails, any classical statement using LEM can be translated into a constructive statement that is proven without LEM, or simply proven with an additional hypothesis that LEM holds; (3) LEM is undesirable in logic because, unlike the other laws of inference, it is not simply "true by definition". $\endgroup$ – 6005 Oct 7 '17 at 16:24
  • $\begingroup$ I still like your first paragraph and the second one correctly points out that mathematicians are not bothered by such considerations about the underlying logic. (+1) $\endgroup$ – 6005 Oct 7 '17 at 16:26
  • 1
    $\begingroup$ @6005 I'm not intending to represent that as the common argument, though I see how it comes across that way. But yeah, really just trying to say that whether using LEM is the logically appropriate way to approach a proof is more a question for philosophers and logicians. (I would also say that the other answers support this). Mathematicians (in most areas of mathematics) are happy to take the fact that it is true a sufficient justification for using it. $\endgroup$ – Morgan Rodgers Oct 7 '17 at 17:12
  • $\begingroup$ @MorganRodgers You are assuming that every "mathematical statement" is either true or false or both. What if it is neither true or false? How do you eliminate that possibility? $\endgroup$ – Somos Oct 8 '17 at 13:23
  • 1
    $\begingroup$ @MorganRodgers Please read this MSE question. $\endgroup$ – Somos Oct 8 '17 at 16:19
1
$\begingroup$

In other words, how can we be sure we arrived at the contradiction because of the proposition $P$ we assumed, and not because of some other proposition $Q$ we are not even aware of?

Let's consider the possibilities for $Q.$ I will assume the Law of the Excluded Middle, because I do not know enough about logic systems without it to say whether proof by contradiction works in any of them.

I also assume that the proof is set in some axiomatic system $A,$ since I do not know how to do proofs outside of any axiomatic system.

So we either have that $Q$ is always true under $A,$ or $Q$ is not always true under $A.$

Case 1

If $Q$ is always true under $A,$ and $Q$ leads to a contradiction, then $A$ is an inconsistent system. It really is not suitable for any kind of proof, including proof by contradiction.

Case 2

If $Q$ is not always true under $A,$ then either $Q$ is entailed by the axioms $A$ together with the assumption $P$ (but not by $A$ alone) or $Q$ is not entailed by the axioms $A$ together with the assumption $P.$ Let's split this case into two sub-cases.

Case 2a

If $Q$ is not entailed by the axioms $A$ together with the assumption $P,$ then $Q$ represents an unwarranted assumption that we made. This makes the proof invalid even if its conclusion is true. Our human fallibility makes it possible for such things to happen. It is possible to introduce such an assumption into a direct proof as well, making it equally invalid.

Case 2b

If $Q$ is entailed by the axioms $A$ together with the assumption $P$ but not by $A$ alone, then $P$ indeed is necessary in order to arrive at the contradiction, and the theorem is provable. But if $Q$ really is instrumental in making some of the steps in the proof, and we were not aware of this fact, then I think again we have an invalid proof of a true conclusion. Again, this is a possible result of human fallibility that can also happen in direct proofs.

Conclusion

Taking all the cases together, there really are only two ways for a proof by contradiction to go wrong. One is if we are working with an inconsistent set of axioms, which is very bad news altogether. The other is if we have an unjustified step somewhere in the proof.

An example of an "unjustified step" occurred famously in Andrew Wiles's first announcement that he had proved Fermat's Last Theorem. Someone (actually, I think multiple people) found a mistake in the proof he presented. After he made a considerable additional effort, he was finally able to present a proof without that mistake, and this proof was accepted.


Some comments under the original question raised the issue of how we check the intermediate steps of a proof by contradiction, claiming that it is easier to check the steps in a direct proof since their conclusions are all true.

Things that we want to prove typically have the form $S\implies T,$ for which a direct proof typically involves assuming $S$ and then showing that $T$ follows. In the intermediate steps of the proof, we have some facts that depend on $S,$ which we cannot "check" by simply observing that they are true; we can check them by verifying the logic in every step leading up to that part of the proof, or we can check them by coming up with an alternative proof showing that they follow from $S.$

We may also introduce some known facts (which do not depend on $S$) in the course of the proof, which we can check simply by verifying that they are true facts.

A third possibility is that we derive something from $S$ that we could have known to be true without assuming $S.$ This is wasteful; we could improve the proof by simply introducing these facts as known without showing a logical derivation from $S.$

The same things happen in proof by contradiction. We will have some steps that we can check only by checking every step in the logic leading up to them or by devising an alternative proof, we may have known facts that we can check more easily, and we may even have wasted effort by deriving something from our (false) assumption that we could have simply brought in as a known fact.

$\endgroup$
  • $\begingroup$ In your particular sense, yes a conditional statement may be difficult to check if the condition is rarely (or never) satisfied. But if you interpret proofs as games (see the comments under it), every use of LEM invokes an oracle. If the proof is purely intuitionistic, then the Refuter can be constructively satisfied by the Prover's justification. If LEM is used, then it falls apart because the Prover is claiming a disjunction without having justified either. In this precise sense a direct proof is interactively checkable. See also BHK. =) $\endgroup$ – user21820 Oct 9 '17 at 4:38
0
$\begingroup$

It is not that by $P\Rightarrow \bot$ (the symbol $\bot$ denotes contradiction) we assume $\neg P$ just because it seems there is something "wrong" with $P$. It is more that we cannot avoid it anyway.

Either the contradiction arises from $P$ and it would be reasonable to assume $\neg P$, or the contradiction remains when removing $P$, but then the already existing inconsistent axiom system suffices to prove $\neg P$ (as well as $P$) using the principle of explosion. So in either way, adding $\neg P$ is reasonable $-$ or at least not more inconsistent as the axiom system itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.