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
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.