1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I had this discussion with a classmate yesterday. In a proof by contradiction, you assume the give hypothesis like usual. In addition to that, you assume the opposite of what you would like to prove. Somewhere along the line after that you should reach a contradiction. $\endgroup$ – fullyhip Mar 8 '15 at 19:43
  • $\begingroup$ after assuming A, according to your hypothesis, P and Q must be false. So, the theorem is invalid $\endgroup$ – mohlee Mar 8 '15 at 19:43
  • $\begingroup$ @MauroALLEGRANZA Doesn't it seem like OP is confusing proof by contradiction as opposed to proof by contraposition? That's what it seems like to me. $\endgroup$ – Daniel W. Farlow Mar 8 '15 at 20:04
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In other words in both cases i should reach a contradiction. More generally when i make a proof by contradiction all exhaustive cases should reach a contradiction? $\endgroup$ – notmyrealname Mar 8 '15 at 19:47
  • $\begingroup$ yes in the case that assumption is $(P \lor Q)$. if the assumption was $(P \land Q)$ you should reach a contradiction in one $\endgroup$ – user 1 Mar 8 '15 at 19:48
  • $\begingroup$ note that $(R\Rightarrow S) $ equals $ (\lnot S \Rightarrow \lnot R)$ $\endgroup$ – user 1 Mar 8 '15 at 19:56
  • $\begingroup$ in your case take $S$ as ¬A and $R$ as P V Q $\endgroup$ – user 1 Mar 8 '15 at 19:59
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.