1

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.
user601846
  • 111
  • 1
    When you obtain a 'proof by contradiction' you have obtained a way to produce a proof that starts from excluded middle $\neg Q$ and then obtain the implication, by taking the contrapositive of $\neg P\implies Q$, of $\neg Q\implies P$. – MoonLightSyzygy Jan 05 '20 at 14:31

3 Answers3

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.

kccu
  • 20,808
  • 1
  • 22
  • 41
  • I guess by point of confusion is that it seems like we are establishing the truth of $\lnot P \implies C$ under the premise that $\lnot P$ is true, then using the truthfulness of $\lnot P \implies C$ to establish the fallaciousness of $\lnot P$. In other words, if $\lnot P \implies C$ being true is dependent on $\lnot P$ being assumed true, how can it then be used to show that $\lnot P$ is false? – user601846 Jan 06 '20 at 01:40
  • Ah, but the implication $\neg P \Rightarrow C$ is not dependent on $\neg P$ being true. Rather, if we assume $\neg P$ then we conclude $C$. Hence we have established $\neg P \Rightarrow C$. We have "discharged" the assumption $\neg P$ at this point. – kccu Jan 06 '20 at 02:55
  • Thank you. I had to go read a bit about the introduction rule for implication to really understand, but your comment pointed me in the right direction. – user601846 Jan 06 '20 at 12:28
1

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.

Bram28
  • 100,612
  • 6
  • 70
  • 118
0

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.

Aryaman Maithani
  • 15,771