Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of the Deduction Principle

  1. Jul 12, 2006 #1


    User Avatar
    Staff Emeritus
    Gold Member

    Let [tex]\varphi[/tex] and [tex]\psi[/tex] both be formulae, and let [tex]\Gamma[/tex] be a set of formulae.

    If [tex]\Gamma \cup \{\varphi\} \models \psi[/tex], then [tex]\Gamma \models (\varphi \rightarrow \psi)[/tex]

    This is the principle by which the rule of inference known as Conditional Introduction is justified, but I cannot seem to find a proof for it, though the claim in the text is that it is an easy proof. Does anybody know what the proof is?
  2. jcsd
  3. Jul 12, 2006 #2
    It pretty much follows from the definition of [tex]\models[/tex]. Suppose [tex]\Gamma \cup \{\varphi\} \models \psi[/tex]. Then every truth assignment that satisfies [tex]\Gamma \cup \{\varphi\}[/tex] must also satisfy [tex]\psi[/tex].
    Last edited: Jul 12, 2006
  4. Jul 12, 2006 #3


    User Avatar
    Staff Emeritus
    Gold Member

    I can see intuitively why it's true, I'd just like to know how to write out the actual proof for purposes of demonstration. I guess the real question is just if there is some special method that has to be used to demonstrate that one argument implies another, or if we can just treat each as a conditional, in which case the proof seems to be a simple, one-step case of exportation:

    1. [tex](\gamma \wedge \varphi) \rightarrow \psi[/tex]
    2. [tex]\therefore \gamma \rightarrow (\varphi \rightarrow \psi)[/tex]
    3. [tex]\gamma \rightarrow (\varphi \rightarrow \psi)[/tex] 1. Exp.

    Can it really be that simple, or do I also have to demonstrate how [itex]\Gamma \cup \{\varphi\} \models \psi[/itex] is equivalent to [itex](\gamma \wedge \varphi) \rightarrow \psi[/itex] and so on?
    Last edited: Jul 12, 2006
  5. Jul 12, 2006 #4
    You mean a syntactic proof? [itex]\models[/itex] is a semantic notion, so the following semantic proof will suffice:

    Suppose [itex]\Gamma \cup \{\varphi\} \models \psi[/itex] but not [itex]\Gamma \models (\varphi \rightarrow \psi)[/itex]. Then there is some truth assignment [itex]\tau[/itex] that satisfies [itex]\Gamma[/itex] and [itex]\varphi[/itex] but not [itex]\psi[/itex]. But [itex]\Gamma \cup \{\varphi\} \models \psi[/itex], so [itex]\tau[/itex] satisfies [itex]\Gamma[/itex], [itex]\varphi[/itex] and [itex]\psi[/itex]. That is a contradiction, hence [itex]\Gamma \models (\varphi \rightarrow \psi)[/itex].
    Last edited: Jul 12, 2006
  6. Jul 12, 2006 #5


    User Avatar
    Staff Emeritus
    Gold Member

    Well gee, that's even simpler. Thanks.
  7. Jul 14, 2006 #6
    i should point out that the deduction thoerem is an iff statement.
  8. Jul 14, 2006 #7
    another way of proving this thoerem is as follows:
    suppose a1,...,an|=b
    then we either have the premise as true and the conclusion b as true, or the conclusion false.
    the first case is trivial.
    for the second part, suppose an is true then a1,...an-1 is false and an->b is either true or false depending on b, either way we get a1,...,an-1|=an->b
    now if an is false then a1,...,an-1 is either false or true but the cocnlusion is always true, cause an->b is always true.
    so either way we get a1,...,an-1|=an->b
  9. Jul 31, 2006 #8
    As wave said, |= is a semantic notion. However, whenever I've heard of the deduction theorem, it's been about the deductive strength of a system. I.e. what you said but with |- instead of |=.

    How hard this is to prove will depend upon the deductive rules and/or axioms of the system in question.
  10. Aug 1, 2006 #9


    User Avatar
    Gold Member

    You can formalize the metaproof if that's what you want. Here are the parts that I felt like writing out, which seem to be the parts wave skipped. Since you need two implication symbols, I let [itex]\rightarrow[/itex] be the one from the original object language.

    1. [tex]\forall \tau, \phi, \psi \ [(\tau(\phi \rightarrow \psi) = F) \ \Leftrightarrow \ (\tau(\phi) = T \ \wedge \ \tau(\psi) = F)][/tex] -- from definition of truth-valuation.
    2. [tex]| \exists \tau, \Phi, \phi, \psi \ [((\tau(\Phi) = T \ \wedge \ \tau(\phi) = T) \ \Rightarrow \ \tau(\psi) = T) \ \wedge \ (\tau(\Phi) = T \ \wedge \ \tau(\phi \rightarrow \psi) = F)][/tex] -- theorem to prove written out in terms of truth-valuations, negated for Reductio, and simplified.
    3. [tex]| \exists \tau, \Phi, \phi, \psi \ [(\neg(\tau(\Phi) = T \ \wedge \ \tau(\phi) = T \ \wedge \ \tau(\psi) = F) \ \wedge \ (\tau(\Phi) = T \ \wedge \ (\tau(\phi) = T \ \wedge \ \tau(\psi) = F)][/tex] -- to first conjunct: double negation, distribute inner negation, swap 'not equal to true' for 'equal to false'; to second conjunct: substitute formula from (1).

    There's your plain-as-day contradiction.
    Last edited: Aug 1, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Proof of the Deduction Principle
  1. Need deduction to help (Replies: 1)