0

I am taking an introduction to proving class right now and I am confused on how to do a proof by contradiction. If I am trying to prove an implication $(p \to q)$ would it take the form: suppose $p \to \lnot q$ (steps in between) therefore $p \to \lnot p$ therefore $p \to q$.

Can someone recommend some example proofs so I can get a better feel for how to do a proof by contradiction

Shaun
  • 44,997
Will
  • 37
  • 3
    Hi, welcome to Math SE. Since $p\to q$ means $\neg p\lor q$, it's the negation of $p\land\neg q$, so that's what you must assume when trying a proof by contradiction. It's no good assuming $p\to\neg q$; that's a different claim, $\neg p\lor\neg q$. What are you trying to prove, by the way? – J.G. Oct 08 '23 at 21:36
  • Are you sure you don't mean to assume $p\land \lnot q$? – Ted Shifrin Oct 08 '23 at 21:37
  • 1
    You must not suppose $p \to \lnot q.$ You must suppose $\lnot(p \to q),$ i.e. $p \land\lnot q$, and derive some falsity, like $p\land\lnot p.$ (Note that $p\to\lnot p$ is not a falsity.) – Anne Bauval Oct 08 '23 at 21:38
  • https://math.stackexchange.com/search?q=proof+by+contradiction – Anne Bauval Oct 08 '23 at 21:44
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – CrSb0001 Oct 08 '23 at 21:45
  • I understand now thank you – Will Oct 08 '23 at 22:13

1 Answers1

1

When attempting to prove an implication $p \to q$, there are several approaches one could use:

$1.$ Assume $p$ and then derive $q$ in order to infer the conditional $p \to q$ via conditional proof.

$2.$ Assume $p$. Then, under the assumption of $p$, assume $\neg q$ and derive a contradiction. Consequently, by reductio ad absurdum, you may infer $q$ is true under the assumption of $p$. Then, by conditional proof, you may infer $p \to q$.

$3.$ Assume the negation of $p \to q$, that is, assume $p \wedge \neg q$, and derive a contradiction. Consequently, by reductio ad absurdum, you may infer $\neg (p \wedge \neg q)$, which is $p \to q.$ This approach is similar to no. $2$ above.

$4.$ Prove the contrapositive of $p \to q$, which is the logically equivalent formula $\neg q \to \neg p$. You can do this in a fashion that is analogous to any of the approaches outlined above. For example, similar to no. $1$, assume $\neg q$ and then derive $\neg p$ in order to infer the conditional $\neg q \to \neg p$ via conditional proof.

RyRy the Fly Guy
  • 5,950
  • 1
  • 11
  • 27