Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 3 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|cite|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

Your Answer


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.