Can any proof by contrapositive be rephrased into a proof by contradiction?

1.6k Views Asked by At

From my understanding,

Proof by contrapositive: Prove $P \implies Q$, by proving that $\neg Q \implies \neg P$ since they are logically equivalent.

Proof by contradiction: Prove $P \implies Q$ by showing that $P \wedge \neg Q$ yields an absurdity and hence false. So $\neg (P \wedge \neg Q)$ is equivalent to $\neg (\neg (P \implies Q))$ and $P \implies Q$ by double negation so showing that $\neg (P \wedge \neg Q)$ proves $P \implies Q$.

If the absurdity derived during the procedure for a proof by contradiction is $P \wedge \neg Q \implies\neg P$, we have essentially already proven $P \implies Q$ by contrapositive since $\neg Q \implies \neg P$ is precisely the required condition for proof by contrapositive. But $(P \wedge \neg Q) \implies \neg P$ is also a contradictory statement which means that $P \implies Q$ must be true.

Now the question is this. Is this proof by contradiction still a valid form of proof even though its a proof by contrapositive in disguise? To me, this proof by contradiction also seems to be a valid proof as it does seem to satisfy the conditions(if they are correct) for proof by contradiction.

Additionally, if you have a contrapositive proof, so you have shown that $\neg Q \implies \neg P$, is it possible to rephrase this in a proof by contradiction by supposing that $P \wedge \neg Q$ instead of just $\neg Q$.

If this is the case, what is the point in distinguishing proof by contradiction from proof by contrapositive?

edit: My thought is that proof by contrapositive is a direct proof while proof by contradiction, in this case, depends on the validity of the double negation law which apparently isn't valid in intuitionistic logic.

1

There are 1 best solutions below

0
On

Yes it is valid... it doesn't really matter if it's something else 'in disguise', just that is it correct. And deriving $\lnot P$ from $P\land\lnot Q$ is certainly leads to a contradiction that implies $\lnot (P\land \lnot Q)$ is true, which implies that $P\to Q$ is true. One thing to note (that I think you have noticed based on your second question) is that you have an additional assumption of $P$ open and available for use when you derive $\lnot P,$ unlike in the case of just deriving $\lnot Q\to \lnot P$ by assuming $\lnot Q$ and deriving $\lnot P.$

So the second question amounts to whether it is admissible to assume $P$ in a proof of $\lnot Q\to \lnot P.$ It is, and the easiest way to see this is reasoning semantically and using the completeness/soundness theorem. If $P\vdash \lnot Q\to \lnot P$ then every interpretation in which $P$ is true has $Q$ true, which means precisely the same thing as $\vdash P\to Q,$ so we have $\vdash \lnot Q\to \lnot P.$

As a result, proof by contrapositive is essentially a special case of what you're calling proof by contradiction, where the contradiction takes the special form $\lnot P$ contradicting with $P.$

I think the reason you might have seen framing contrapositive proofs as proofs by contradiction discouraged is for style reasons. Unless the outstanding assumption of $P$ is used (unnecessarily), the part of the proof outside the inner proof of $\lnot Q\to \lnot P$ is just boilerplate that can be omitted. It is also more informative to call it a proof by contrapositive since that is a special case of contradiction.

(As Derek indicates in the comments, proof by contrapositive is not intuitionistically valid, so it doesn't have anything to do with this.)