Results 1 to 6 of 6

Math Help - another derivation

  1. #1
    Junior Member
    Joined
    Jan 2008
    From
    Waipahu, HI
    Posts
    37

    another derivation

    The problem:

    Show that the set \{\neg(p\rightarrow q), \neg(q\rightarrow r)\} is inconsistent.

    The hint is to show that \neg(q\rightarrow r)\vdash q and \neg(p \rightarrow q)\vdash \neg q

    And of course the hint totally makes sense but I just cannot do it! I feel like I've played around all day with the three axioms and MP and tried using the deduction theorem and deriving things from the empty set and trying to reverse engineer the derivation and UGH! I don't understand how to do these things, is there like a method to figuring it out or is it just reverse engineering and trial-and-error or what?

    Any help or hints or anything will be MUCH appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765
    Here is an outline that uses Deduction Theorem (DT). I assume that (not p) is an abbreviation for (p -> false). If negation is a primitive connective (i.e., not an abbreviation for anything), then some steps below need to be adjusted.

    Code:
    (1) not q        assumption
    (2) q            assumption
    (3) false        (1), (2), MP
    (4) r            (3), EFQ
    (5) q -> r       (2), (4), DT; close assumption (2)
    (6) not (q -> r) assumption
    (7) false        (5), (6), MP
    (8) not (not q)  (1), (7), DT; close assumption (1)
    (9) q            (8), DNE (double-negation elimination)

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2008
    From
    Waipahu, HI
    Posts
    37
    We aren't using truth values because with our notation, \vdash means that there is a formal derivation only, while \models means that it's a logical consequence (using truth values). So like the \vdash means you can play around with the shape of the formula only. (At least, in my understanding but obviously I'm a n00b!)

    Also how can you assume q and not q? I think the only thing we are allowed to assume is \neg(q\rightarrow r) and then put that in the axioms somehow. Also we don't have the ability to get rid of double negations either.

    I'm sorry! Is there something that I'm just not understanding?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    You understand that we do not have your particular text material.
    However, as I read the question here is my take.
     \neg \left( {p \to q} \right) \equiv p \wedge \neg q
    By simplification \neg q.
    Likewise,  \neg \left( {q \to r} \right) \equiv q \wedge \neg r
    By simplification q.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765
    We aren't using truth values
    I am not talking about truth values either. Everything I wrote above is about derivations.

    Since you mentioned the three axioms, MP and the Deduction Theorem, I assume you are using Hlbert-style derivations (see in particular the three axioms -- are they the same that you are using?). Hilbert system is easy to study but hard to use in practice. To construct a complete derivation of the required formula is pretty hard, so I am describing how to build it in theory without actually building it.

    In particular, DT is very convenient, but note that this is not a primitive inference rule. It is an algorithm describing how to construct a derivation of \Gamma\vdash p\to q from \Gamma,p\vdash q. By looking into the proof, one can actually build the required derivation in every concrete instance, but this is rarely done.

    Similarly for DNE: this is not a primitive rule, but for each formula p there is a derivation of \neg\neg p\to p. This derivation can be incorporated into bigger derivations.

    Also how can you assume q and not q?
    By using DT. By assuming q and deriving r I mean deriving q\vdash r. Then you apply the DT to obtain a derivation of \vdash q\to r, where the assumption q is no longer present (it is said to be closed).

    Applications of DT can be nested. You can have the following sequence: (1) assume p, (2) assume q, (3) derive p, q\vdash r, (4) apply DT to get p\vdash q\to r, (5) continue this derivation to get p\vdash r', (6) apply DT to get \vdash p\to r'.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jan 2008
    From
    Waipahu, HI
    Posts
    37
    Okay, that makes a lot more sense. I was definitely confused when you said something about not p being the same as p --> false. Those are the axioms that we're using! It's so much easier to find other sources online now that I know the name. For some reason we haven't mentioned the name Hilbert at all in the book, but from what I've looked at so far, that's what it is. It's really helpful to know that you can use nested DTs too. Thank you so much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Derivation and Jordan derivation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 8th 2011, 09:22 PM
  2. [SOLVED] Help on log derivation
    Posted in the Calculus Forum
    Replies: 5
    Last Post: November 19th 2010, 02:04 PM
  3. Help with derivation
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 19th 2010, 06:12 AM
  4. Second derivation
    Posted in the Calculus Forum
    Replies: 1
    Last Post: January 29th 2009, 09:58 AM
  5. Could use some Derivation help, please
    Posted in the Calculus Forum
    Replies: 12
    Last Post: April 12th 2008, 06:58 AM

Search Tags


/mathhelpforum @mathhelpforum