In deductive logic, we may make the following step:

( {Γ,P}⊨Q & {Γ,P}⊨¬Q ) ⇒ {Γ}⊨¬P

I've been trying to find examples of a proof that this inference follows, but I've struggled with my search. If anyone could point me in the right direction, or show me the proof, it would be much appreciated.

I would be particularly interested in a proof that doesn't use a deduction theorem to prove that a reductio as a logically permissible inferential step.

  • 1
    I don't believe the PSE is the right site for this particular question; rather, perhaps the Mathematics Stack Exchange?
    – Mr Pie
    Apr 30, 2018 at 0:31
  • 1
    I strongly disagree. Logic is as much a branch of Philosophy as metaphysics. Apr 30, 2018 at 10:09
  • I would say you are not writing the problem correctly. It seems you are using a conditional as if the consequent is the conclusion. That is you seem to express what follows the arrow is the conclusion which is not correct. There is another SYMBOL for that and it's not the arrow. As written one can take it as you wrote exactly one long premise.
    – Logikal
    Apr 30, 2018 at 18:47
  • 1
    Assuming you work with natural deduction, Malamud's notes have a proof on p.3, it uses the ⊥ formation rule.
    – Conifold
    Apr 30, 2018 at 21:51

1 Answer 1


You are using , i.e. the semantical consequence relation. Thus, we have to provide a semantical proof.

We have that {Γ,P} ⊨ Q and {Γ,P} ⊨ ¬Q.

This means that a truth valuation v that satisfies every formula in Γ and P also satisfies both Q and ¬Q.

But, according to the rules of semantics, there is no such truth valuation (because the semantical specification says : v ⊨ ¬A iff not v ⊨ A).

Consider now a valuation v that satisfies every formula in Γ; by the above consideration, we must have : v ⊨ ¬P, and this means :

Γ ⊨ ¬P.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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