4
$\begingroup$

How do I prove $$\Gamma, A, B \vdash C \Rightarrow \Gamma, A \wedge B \vdash C$$? It makes sense to me in general (like, if we want to show $C$ is derivable from $A \wedge B$, we have to show it's derivable assuming $A$ and also $B$) but I'm stuck constructing a formal proof. The deduction theorem ($\Gamma \vdash A \wedge B \supset C$) seem to bring me no closer to some kind of axiom.

I'm presented with the whole bunch of axioms: $$A \supset (B \supset A)$$ $$(A \supset (B \supset C)) \supset ((A \supset B) \supset (A \supset C))$$ $$A \supset (B \supset A \wedge B)$$ $$A \wedge B \supset A$$ $$A \wedge B \supset B$$ $$(A \supset C) \supset ((B \supset C) \supset (A \vee B \supset C))$$ $$A \supset A \vee B$$ $$B \supset A \vee B$$ $$(A \supset B) \supset ((A \supset \neg B) \supset \neg A)$$ $$\neg\neg A \supset A$$ $$\textbf{F} \supset A$$ $$A \supset \textbf{T}$$

  • 1
    You mean the _Deduction Theorem_, not the "induction theorem". And +1 for stating your axioms.2012-01-08

1 Answers 1

3

This is very easy: you just write out the same proof, except where you write in

  • (hypothesis) $A$

in the first proof, you replace it with the sequence

  • (hypothesis) $A \land B$
  • (axiom) $A \land B \to A$
  • (modus ponens) $A$

and similarly for $B$.

  • 0
    So the road to derive $A, B$ from $A \wedge B$ would be $A \wedge B, A \wedge B \supset A, A, A \wedge B \supset B, B$! I think I've missed the point that $A, B, A \wedge B$ were just elements of the formal proof, which I could operate on. I wish I could delete the question as being trivial, anyway...2012-01-08