using the elimination rule in natural deduction

Question

Prove that

$$(A ∧ B) \to C ⊢ A \to (B \to C)$$

Am I using the conjuction elimination rule correctly? Or am I assuming too much?

1. $(A ∧ B) \to C$ (Given)
2. $A \to C , B -> C$ (∧E 1)
3. $A \to( B \to C)$ ($\to$I 2) (QED)

Answer 1

(1) The Conjunction Elimination Rule

In a standard natural deduction system, the Conjunction Elimination Rule states that

$$\frac{\varphi \wedge \psi}{\varphi} \frac{\varphi \wedge \psi}{\psi} \tag{$\wedge$E}$$

Which means we are allowed to apply it in sentences with a conjunction as its logical structure.

But you are not allowed to apply this rule in the above case. The sentence you have above is not a conjunction, but an implication. You are not using conjunction elimination correctly.

---

(2) Your Answer

In order to prove this statement, it suffices to see the logical form of your goal: $$A \to (B \to C)$$ this suggests that in order to prove this statement, we first assume $A$ as hypothesis, and eventually assume $B$ too, in order to obtain C:

1. $(A ∧ B) \to C$, P

   2. $A$, H

      3. $B$, H
      4. $A \wedge B$, 2, 3 $\wedge$I
      5. $C$, 1, 4 $\to$E (Modus Ponens)
      6. $B \to C$, 3-5 $\to$I
      7. $A \to (B \to C)$, 2-6 $\to$I

Keep working!