3
$\begingroup$

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?

$\endgroup$

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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." $\endgroup$ Commented May 3, 2020 at 3:08
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .