How to prove $(p \to q) \equiv (\neg q \to \neg p)$ by using natural deduction?

Question

I know that most of us know the contrapositive $$(p \to q) \equiv (\neg q \to \neg p)$$ but how can I prove this by using natural deduction?

Answer 1

Hint

See Natural Deduction for the rules.

A) $p \to q \vdash \lnot q \to \lnot p$

1) $p \to q$

2) $\lnot q$ --- assumed [a]

3) $p$ --- assumed [b]

4) $q$ --- by $\to$-elim

5) $\bot$ --- from 2) and 4) by $\lnot$-elim

6) $\lnot p$ --- from 3) and 5) by $\lnot$-intro, discharging [b]

6) $\lnot q \to \lnot p$ --- from 2) and 6) by $\to$-intro, discharging [a].

---

For the other part, we need Double Negation or LEM.

Answer 2

I use '~' for '$\lnot$' and '->' for '$\rightarrow$' in the following. I don't know how to fill in the dots, so you'll have to do that. Some systems say that when you have a contradiction under the scope of the hypothesis $\lnot$$\alpha$ you can infer $\lnot$$\lnot$$\alpha$. Some say that under that hypothesis you can infer $\alpha$. Some say that you can infer that ($\lnot$$\alpha$$\rightarrow$($\beta$$\land$$\lnot$$\beta$)), where ($\beta$$\land$$\lnot$$\beta$) indicates the contradiction. Then you can infer $\alpha$ from that. Some say you have to have something like ($\lnot$$\alpha$$\rightarrow$$\beta$) as well as ($\lnot$$\alpha$$\rightarrow$$\lnot$$\beta$), and only then can you infer $\alpha$. This makes for a good problem to suggest where natural deduction systems generally tend to differ the most. You'll also have to write the proof analysis.

If (p -> q)
    If ~q
         If ~~p
            .
            .
            .
            p
            q
            Contradiction
        .
        .
        .
       ~p 
   (~q -> ~p)

((p$\rightarrow$q)$\rightarrow$($\lnot$q$\rightarrow$$\lnot$p))

If (~q -> ~p)
     If p
         If ~q
            ~p
            Contradiction
        .
        .
        .
        q
   (p -> q)

(($\lnot$q$\rightarrow$$\lnot$p)$\rightarrow$(p$\rightarrow$q))

Now, can you complete a proof?