1
$\begingroup$

Consider we have the following statement to prove: $P \implies Q \wedge R$. For a proof by contradiction, we assume $P \wedge (\neg Q \lor \neg R)$.

How would one go about this? Typically to prove a statement of the form $(A \lor B) \implies C$, we show $A \implies C$ and then $B \implies C$. Do we break down such a proof by contradiction into such cases?

Mainly:

  1. Does it suffice to reach separate contradictions by considering the cases $P \wedge \neg Q$ and $P \wedge \neg R$ separately?

  2. Must one also consider the case when $(P \wedge \neg Q)$ and $(P \wedge \neg R)$ are both assumed to hold "simultaneously"?

Many thanks in advance for your help.

$\endgroup$
6
  • $\begingroup$ If you want to derive a contradiction (if any) from $P \wedge (\neg Q \lor \neg R)$, you have to consider the two cases forming the disjunction. $\endgroup$ – Mauro ALLEGRANZA Jan 26 '20 at 9:54
  • $\begingroup$ @MauroALLEGRANZA, yes that I know - I meant it 'loosely' i.e. in the context of the proof technique. Thank you for pointing it out - removed the sentence for clarity. $\endgroup$ – Xandru Mifsud Jan 26 '20 at 9:55
  • $\begingroup$ @MauroALLEGRANZA, so if I understood correctly, you first show contradiction of $P \wedge \neg Q$ independent of $P \wedge \neg R$, and then similarly for $P \wedge \neg R$ independent of $P \wedge \neg Q$. $\endgroup$ – Xandru Mifsud Jan 26 '20 at 9:57
  • $\begingroup$ See Proof by cases: if you show that (P∧¬Q) implies a contra and that (P∧¬R) implies a contra, it is fine. $\endgroup$ – Mauro ALLEGRANZA Jan 26 '20 at 9:58
  • 1
    $\begingroup$ Thanks @MauroALLEGRANZA, your last comment clarifies the matter for me. Please, how can I mark it as solved by you? $\endgroup$ – Xandru Mifsud Jan 26 '20 at 10:00
0
$\begingroup$

If we want to derive a contradiction (if any) from $P ∧ (¬Q∨¬R)$, we have to consider the two cases forming the equivalent disjunction:

$(P ∧ ¬Q) ∨ ( P ∧ ¬R)$.

See Proof by cases: if we show that $(P∧¬Q)$ implies a contradiction and that $(P∧¬R)$ implies a contradiction, it is done.

$\endgroup$
2
  • $\begingroup$ You should have said or, not and. $\endgroup$ – Ben W Jan 28 '20 at 20:13
  • $\begingroup$ @BenW --- NO. Se the Wiki entry regarding Didjunction Elim linked above: if we have $P \to R$ and $ \to R$, we can conclude that $R$ follows from $P \lor Q$. $\endgroup$ – Mauro ALLEGRANZA Jan 28 '20 at 20:18

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.