Natural deduction (Logic) proof help

Question

I'm very new to natural deduction and have been stuck trying to prove this argument all day:

$A\to ¬B,$

$¬B\to ¬C,$

Therefore, $C\to ¬A$.

I've been told I need to use modus tollens on the first premise, but I am not sure what to use it on/what to assume, as I thought using modus tollens on premise 1 would yield $B$, which I don't need, instead of $\lnot A.$

Thank you.

Answer 1

Assuming the availability of Modus Tollens rule, we have :

1) $A \to \lnot B$ --- premise

2) $\lnot B \to \lnot C$ --- premise

3) $C$ --- assumed [a]

4) $\lnot C$ --- assumed [b]

5) $\lnot \lnot C$ --- from 3) and 4) by $\lnot$elim followed by $\lnot$-intro (also called Double Negation introduction), discharging [b]

6) $\lnot \lnot B$ --- from 5) and 2) by MT

7) $\lnot A$ --- from 6) and 1) by MT

8) $C \to \lnot A$ --- from 3) and 7) by $\to$-intro, discharging [a].

---

Note : without MT the proof is quite simple :

1) $A \to \lnot B$ --- premise

2) $\lnot B \to \lnot C$ --- premise

3) $C$ --- assumed [a]

4) $A$ --- assumed [b]

5) $\lnot B$ --- from 4) and 1) by $\to$-elim

6) $\lnot C$ --- from 5) and 2) by $\to$-elim

7) $\lnot A$ --- from 4) with 3) and 6) by $\lnot$-elim followed by $\lnot$-intro, discharging [b]

8) $C \to \lnot A$ --- from 3) and 7) by $\to$-intro, discharging [a].

Answer 2

If you have Hypothetical Syllogism in your tool box, the proof becomes far more direct.

Hypothetical Syllogism (HS) is a valid argument form in which two premises are conditionals, and the rule is that, whenever instances of "$\displaystyle P\to Q$", and "$\displaystyle Q \to R$", appear on lines of a proof, "$\displaystyle P\to R$" can be placed on a subsequent line.

In your argument, we then have

$(1) \;\;A\to \lnot B,\qquad$ (premise)

$(2) \;\;\lnot B \to \lnot C,\,\quad$ (premise)

$(3) \;\;A\to \lnot C,\qquad$ HS, $(1), (2)$

$(4) \;\;C \to \lnot A,\qquad$ contraposive of $(3).$

---

Note that instead of relying on the equivalence of an implication $p\to q$ with its contrapositive, $\lnot q \to \lnot p$, we can proceed from $(3)$ to

$(4) \;\;\quad C \quad$ assumption

$(5) \;\;\quad \lnot\lnot C\quad$ double negation on $(4)$

$(6) \;\;\quad \lnot A\quad$ ($3$, $5$, modus tollens)

$(7) \;\; C\to \lnot A \quad$ ($4-6$)