In a proof by contradiction, how do we know the assumption is the cause of the contradiction?

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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.

Answer 4

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.

Answer 5

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.