I want to prove $P$ is true (by contradiction). What happens if I deduce $Q$ from $\lnot P$, knowing $\lnot Q$, then replace $Q$ with $P$?

Question

I have a quick question about reasoning by contradiction.

Suppose I want to prove that a proposition $P$ is true (by contradiction). I will suppose that $\neg P$ is true and I will try to deduce that a proposition $Q$ is true, knowing that $\neg Q$ is true. I will conclude by saying that $P$ is true.

My question is the following: is this point of view works if I replace $Q$ by $P$ ?

If yes, it seems a bit strange to me... do you have an example where we can do that ?

Thank you.

Answer 1

Well... you could....

Okay, you actually bring up a subtle point.

When you assume $\lnot P$ and conclude $Q$ that you know is false, it doesn't have to be that you know $Q$ is false. It's that you know $Q$ together with $\lnot P$ can't be true.

Let's suppose... bear with me.... this is purely hypothetical.

You need to prove $n$ is even. And somehow there is a number $w = n-7$. (Since it will turn out that $n$ is even it will turn out that $w$ is odd... but we don't KNOW either of those yet. We have no idea if $n$ or $w$ are even or odd.)

You assume that $n$ is odd. And somehow you manage to prove, god knows how, that if $n$ is odd then $w$ is odd. But that means $n-7$ is odd but if $n$ is odd then $n-7$ is even. That's a contradiction. SO $n$ is even.

But note $w$ being odd isn't a contradiction! In fact as it turns out $w$ was odd! The contradiction wasn't "$w$ is odd". The contradiction was "$n$ is odd and $w=n-7$ is also odd".

.....

So assuming $\lnot P$ and reaching the conclusion $P$......

Well, you don't know that $P$ is false (and if you actually did this it would mean $P$ is true!) so concluding $P$ is not the contradiction.

But concluding $P$ is true WHILE assuming $P$ is also false, is the contradiction.

So.... $P$ must be true.

That is a valid proof by contradiction.

Answer 2

An interpretation of your question is equivalent to asking whether $$((\lnot P)\to P)\to P\tag{$\Sigma$}$$ is a tautology.

Indeed, suppose otherwise; that is, $$\lnot (((\lnot P)\to P)\to P)\tag{1}$$ is true. Then we have both $$(\lnot P)\to P\tag{2}$$ and $$\lnot P\tag{3}$$ from $(1)$. Then $(2)$ gives either: $$\lnot\lnot P,\tag{4$i$}$$ i.e., $$P,\tag{5}$$ and so $(5)$ contradicts $(3)$; or, $$P,\tag{4$ii$}$$ which also contradicts $(3)$.

Hence $(\Sigma)$ is a tautology.

Answer 3

It actually happens all the time, especially when $P$ is naturally expressed as the negation of something.

Here's a less weird example than fleablood's. Let $P$ be "$3 \cdot k \ne 4$", where $k$ is a natural number (in other words, we're proving $4$ is not divisible by $3$). Here's a proof:

Assume $\neg P$, i.e. $3 \cdot k = 4$. There are two cases to consider:

1. if $k \le 1$, then $3 \cdot k \le 3 \cdot 1 = 3$, and $3 < 4$, so $3 \cdot k \ne 4$ (i.e. $P$).
2. if $k \ge 2$, then $3 \cdot k \ge 3 \cdot 2 = 6$, and $6 > 4$, so $3 \cdot k \ne 4$ (i.e. $P$ again).

Thus, assuming $\neg P$, we deduce $P$. We conclude $P$ is true.