Proof by cases and contradiction. Is this valid?

Question

Say i have a hypothesis of the following form: $P \lor Q$ and a conclusion $\neg A$. I try a proof by contradiction; so I assume $A$. Now what I am trying to do is break the hypothesis into cases, so:

• Case 1: I assume $P$ is true. This leads to a contradiction, so i conclude $\neg A$.
• Case 2: I assume $Q$ is true. This, however, does not lead to a contradiction.

In one of the cases I reached a contradiction and in the other I did not. Does this mean that the theorem is invalid as the conclusion is not reached even if the hypothesis is true (case 2) or is this a valid theorem?

Answer 1

assuming $A$, you should reach: $\lnot(P \lor Q)= (\lnot P) \land (\lnot Q)$; by De Morgan's laws

Answer 2

You're confusing a proof by contradiction with a proof by contraposition.

Suppose we are trying to prove $(P\lor Q)\to\neg A$, as you have indicated.

By contradiction: If $(P\lor Q)\to\neg A$ is generally true, then it is a tautology (it has only true truth values). Thus, a proof by contradiction would be to consider $\neg[(P\lor Q)\to\neg A]$ and up with a contradiction (a statement that has only false truth values).

By contraposition: Note that, in general, $p\to q\equiv \neg q\to\neg p$. Thus, we would want to prove $\neg(\neg A)\to\neg(P\lor Q)$. That is, given $A$, show that $\neg P\land\neg Q$ follows.