# Difficulty understanding proof by contradiction

Here's my understanding of proof by contradiction based on what I've read and I've been taught.

We show $$\neg P \implies (c \land \neg c)$$ is always true. This is done by assuming $$\neg P$$ is true. Then, we realize that $$(c \land \neg c)$$ is logically equivalent to $$F$$ so we've just shown that $$\neg P \implies F$$ is always true. But, examining the $$\implies$$ truth table, we realize that $$\neg P$$ must be false to ensure $$\neg P \implies F$$ is always true. Therefore, we conclude that $$\neg P$$ is false, and thus $$P$$ is true.

The conundrum I have is that our analysis is based on the assumption that $$\neg P$$ is true. Then later we conclude that $$\neg P$$ is false. So why do we accept that $$\neg P$$ is false even though we assume $$\neg P$$ is true?

We are not assuming $$\lnot P$$ is true.What we are trying to do is to prove $$\lnot P\implies F$$. To prove that, we show that if P is true, F. Therefore we have shown that $$\lnot P\implies F$$ is true. Hence $$\lnot F \implies P$$ is true. Since $$\lnot F$$ is true, P is true.

• Exactly. When we say "Assume S is true; then ... ", what we mean is "Let us examine the consequences that follow from the assumption that S is true." Commented May 3, 2020 at 3:08

The proof by contradiction is based on the fact that if the conclusion of a valid argument is false, then necessarily, the premisse of this argument is False.

If the implication $$A \implies B$$ is true and $$B$$ false, we conclude that $$A$$ is false.

If we start with a hypothesis $$H$$ and using a valid argument, we get a false conclusion like $$q\wedge \lnot q$$, then we are sure that $$H$$ is false.

If the premisse of a valid argument is true, the conclusion cannot be false.

If my dog is in the bathroom, I will hear him bark there.

I do not hear him bark there.

Hence he is not in the bathroom.

Nothing more profound than that.

Suppose you've proved $$\lnot P\to F$$. \begin{align*} \text{Then:}\;\;\; &1.\qquad \lnot P\to F\\[4pt] &2.\qquad \lnot P\to (P\land\lnot P)\\[4pt] &3.\qquad \lnot P\to P\\[4pt] &4.\qquad P\to P\qquad\text{(tautologically)}\\[4pt] &5.\qquad (P\lor\lnot P)\to P\\[4pt] &6.\qquad T\to P\\[4pt] &7.\qquad P\\[8pt] \text{Or even simpler:}\;\;\; &1.\qquad \lnot P\to F\\[4pt] &2.\qquad \lnot F\to\lnot (\lnot P)\qquad\text{(contrapositive)}\\[4pt] &3.\qquad T\to P\\[4pt] &4.\qquad P \end{align*} Thus, once you've proved $$\lnot P\to F$$, you can prove $$P$$ (it's not an assumption).