Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$$

share|improve this question
    
You mean the Deduction Theorem, not the "induction theorem". And +1 for stating your axioms. –  Henning Makholm Jan 8 '12 at 3:43
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
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... –  Egor Tensin Jan 8 '12 at 2:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.