Proof by contradiction, status of initial assumption after the proof is complete.

Question

First of all I'd like to say that I have looked for the answers to my specific question and have not found it in the existing topics.

The question is fairly simple. Say, we need to prove statement P by the method of contradiction. Assuming that $\lnot P$ holds, using the list of statements proven earlier to hold or derived by us during the proof, we arrive to P being $true$.

$$\lnot P \to A_1 \to\ ... \ \to A_n \to P$$ $$\lnot P \to P \iff \lnot(\lnot P) \lor P \iff P $$

We can therefore add P to the list of our proven statements, because it was derived. Most of the proofs contain something in the lines of "the obtained contradiction proves that our initial assumption ($\lnot P$) was wrong and so $P$ holds".

What I don't understand is, if the initial assumption ($\lnot P$) is thus proven to be false, then why can we be sure that anything derived from it holds (in particular, that P holds)? On the other hand, if it cannot be derived then the assumption ($\lnot P$) can in fact be true.

Can someone explain why this type of argument cannot be used?

Answer 1

The basic assumption is that we reason in a consistent logical system. What we want to derive is not necessarily that $P$ holds, we just want to show that the assumption $\neg P$ leads to a contradiction and, as we assume the logical system to be consistent, it cannot have contradictions. This shows that $\neg P$ is wrong.

Then, if we further assume that tertium non datur holds, i.e. that for any given statement $P$ the statement $P\lor \neg P$ holds, it follows that $P$ must be true.

Again, just to reiterate: Proof by contradiction just has to yield any contradiction under the assumption of $\neg P$ to prove $P$. However, such reasoning is only sound if the logical calculus in which you're reasoning has something like TND or a contradiction rule and is consistent.

Answer 2

We are not deriving $P$ from the assumption $\lnot P$. What we are doing is that we are deriving a contradiction from the assumption $\lnot P$. The contradiction can be something like $P \land \lnot P$, or it could be something else which contradicts an already proven statement.

The fact that we have arrived at a contradiction in turn implies that our initial assumptions have to be false. This is how we derive that $\lnot P$ must be false and hence $P$ must be true.

To reiterate, we are not proving $P$ with $\lnot P$ as an assumption. We are using the assumption to arrive at a contradiction which then implies $P$.

Answer 3

What I don't understand is, if the initial assumption ($\lnot P$) is thus proven to be false, then why can we be sure that anything derived from it holds (in particular, that P holds)? On the other hand, if it cannot be derived then the assumption ($\lnot P$) can in fact be true.

When you introduce an assumption $P$ in a proof, you do not need to first prove that it is true. You simply want see what conclusions could be drawn from $P$ if it were true.

Having introduced the assumption $P$, if you can then derive $Q$ without introducing any other assumptions, you can then conclude that $P \implies Q$

On the other hand, if you can then derive a contradiction of the form $Q\land \neg Q$ without introducing any other assumptions, you can then conclude $\neg P$.

As to the status of the initial assumption (your initial question here), in both cases, after you have written down your conclusion, you may refer to the conclusion in subsequent lines of your proof. You may not, however, refer to the initial assumption ($P$ in this case) or any subsequent lines prior to the resulting conclusion. In a sense, those lines will have been deactivated after forming your conclusion. We say that the initial assumption has then been discharged.

Such assumption-conclusion blocks, may, of course, be nested within one another as sub-proofs. The above rules will apply for each of these blocks individually.