Results 1 to 7 of 7

Math Help - Deduction Theorem Help

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    6

    Deduction Theorem Help

    x
    Last edited by chebyshev1; August 17th 2010 at 11:58 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Are you doing the Henkin proof? If so, isn't it true that the sentence

    \neg\forall x\,P(x)\iff\exists x\,\neg P(x)

    is a first order validity? I suppose you can prove this if you really need to - the natural deduction rules are strong enough to get it.

    So my question is, why do you need to prove this? In the Henkin construction, at least, you usually just take these statements as axioms. At least, the book Language, Proof, and Logic does it that way. What book are you using?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Well, you know that you're proving a conditional. So, the first thing to do is assume the antecedent:

    Assume: Ex ~Fx. Show: ~Ax Fx.

    But ~Ax Fx is a negation. So, you'd probably consider proof by contradiction:

    Assume: Ax Fx.

    Now do the rest...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2010
    Posts
    6
    x
    Last edited by chebyshev1; August 17th 2010 at 11:58 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    EDIT: Forget what I said about biconditional; I was looking at the wrong thing.

    Note: I don't have that book, so my remarks may need some adjustment to meet the exact particulars of that book.

    I showed you how to start. Do you not see how to go on from there?

    /

    And just to be clear: You should understand that the deduction theorem is not a theorem IN the system you're working with but rather is a theorem ABOUT the system you're working it.

    The deduction theorem (a META-theorem ABOUT the system we're working in) is:

    For all formulas P and Q, if

    P |- Q then |- (P -> Q).

    (We can write "|- (P -> Q)" as "|- P -> Q".)

    And the other direction:

    If |- P -> Q then P |- Q

    is basically modus ponens.

    So we get:

    P |- Q if and only if P |- P -> Q

    And I showed you how to get started using it for your example.
    Last edited by MoeBlee; August 17th 2010 at 11:45 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Aug 2010
    Posts
    6
    x
    Last edited by chebyshev1; August 17th 2010 at 11:59 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    I noticed that the actual exercise doesn't ask you also to show that "second half". (See the edited version of my previous post.)

    But we can do it anyway.

    You've ALMOST got the right idea. But we don't show a contradiction between Ax Fx and ~Ax Fx. We ALREADY KNOW that it is a contradiction; it doesn't do us any good. Rather, we find a contradiction between Ax Fx and Ex ~Fx.

    But first, finish the rest of the "first half" I started.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Natural Deduction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 9th 2011, 03:15 AM
  2. Deduction theorem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2010, 09:39 AM
  3. Deduction with Stoke's Theorem
    Posted in the Calculus Forum
    Replies: 7
    Last Post: May 16th 2010, 03:18 AM
  4. natural deduction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 24th 2010, 11:47 AM
  5. Store Deduction
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: January 19th 2007, 12:46 PM

Search Tags


/mathhelpforum @mathhelpforum