Understanding the logic behind proof by contradiction.

Question

I'm having some trouble grasping the validity of the logical underpinnings of the proof by contradiction method.

The following is the basic structure I've been presented with:

To prove a statement $P$, assume $\lnot P$. From $\lnot P$, derive some statement $R$ that is contradictory to some known fact or assumption we made in the proof. Thus, the contradiction $C: R \land\lnot R$ is true. Thus, $\lnot P \implies C$ is t true. However, since $C$ is a contradiction and always false, it must be that $\lnot P$ is false, thus $P$ is true.

My questions are as follows:

1. I thought that the definition of a contradiction is something that is always false. Thus, how can we say that $C$ is ever true? Is it the case that the proof exists within its own logical "universe" as it were?
2. If we are able to say that $C$ is true and thus $\lnot P \implies C$ is true, how are we then able to say that $\lnot P \implies C$ remains true when we then say that $C$, being a contradiction, must be false? I would think that $C$ being false would abrogate the validity of the implication as well.

Answer 1

1. The contradiction $C$ is only true under the premise $\neg P$. That is, the implication $\neg P \Rightarrow C$ is true. We cannot conclude from this that $C$ is true, unless we know $\neg P$ is true. However, $\neg P$ is only taken as a premise, not an axiom or truth.

2. The implication $\neg P \Rightarrow C$ does not tell us anything about the truth value of $C$, unless we know that $\neg P$ is true. We know that if $\neg P$ were true, then $C$ would be true. This is different from saying $\neg P$ is true and thus $C$ is true. The implication "$A\Rightarrow B$" can hold true even if $B$ does not hold true - in fact, the only way this happens is if $A$ is false. In our case, $A$ is $\neg P$, so $A$ being false means $\neg P$ is false, so $P$ is true.

Answer 2

You are actually almost there!

Yes, you are right, a contradiction cannot be true. And that is exactly the key here!

That is, if we can show that a contradiction would be true if $\neg P$ were true, then we are in big trouble if in fact $\neg P$ would be true. So, we can conclude that $\neg P$ cannot be true, meaning that $\neg P$ is False, and therefore (at least in classical logic) $P$ is true.

Answer 3

Not a direct answer to your question but maybe this helps in understanding the legitimacy of proof by contradiction.

In an informal sense, the statement $\phi \to \psi$ is true if $\phi$ is false, regardless of $\psi$.

Thus, if $C$ is contradiction, then $C \to R$ is true for any choice of $R$. $\quad$ (1)

---

Now, suppose $P$ is a statement such that you can derive $C$ from $\neg P$. We want to show that this implies $P$ is true.

We do this as follows.

We know that $P \vee \neg P$ is true. $\qquad (*)$

Case 1. $P$ is true. It is clear that $P \to P$.

Case 2. $\neg P$ is true. $\neg P \to C$ and $C \to P$, by (1).

Thus, in either case we get that $P$ is true.

---

Note that $(*)$ may seem obvious but there are models of logic which don't assume $P \vee \neg P$ to be a tautology. However, they do have a problem with proof by contradiction as well.