Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

bluebrandon Group Title

prove using the Hilbert System {not q} ⊢ (p→q)→(not p)

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm supposed to use the 3 axioms of the Hilbert System and Modus Ponens to prove this

    • 2 years ago
  2. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Using the Hilbert Axioms. We state our given: \[ \neg q \vdash (p\to q)\to\neg p \]Using the fourth (or third primary axiom): \[ (\neg p\to \neg q)\to(q \to p) \]We contraposition the first clause, since they are equivalent statements, by the above logical axiom: \[ \neg q \vdash (\neg q\to \neg p)\to\neg p \]Since\[ \neg p\to \neg p \]By a simple reduction, then: \[ \neg q \to \neg p \]QED.

    • 2 years ago
  3. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I think I need to assume (not q) and use that with the Hilbert System to come to the conclusions that (p→q)→(not p)

    • 2 years ago
  4. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    sorry if the way I wrote that made it confusing

    • 2 years ago
  5. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Oh, all right, sorry, that's not all too difficult, let me retype the above:

    • 2 years ago
  6. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    It's essentially the same proof, just that we assume only the first given to denote the second. We assume: \[ \neg q, (p\to q) \]To be true, along with the three logical actions in the Hilbert system. We begin: \[ (p\to q)\to (\neg q \to \neg p) \]By (3): \[ \left ( \lnot \phi \to \lnot \psi \right) \to \left( \psi \to \phi \right) \]So: \[ (\neg q \to \neg p)\to \neg p\wedge \neg q\to \neg p \]Consequentially: \[ \neg q \vdash (p\to q) \to \neg p \]QED.

    • 2 years ago
  7. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    are you assuming p->q at the beginning?

    • 2 years ago
  8. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, you have to, otherwise nothing follows.

    • 2 years ago
  9. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Because we would then have no relation between instance \(p\) and \(q\).

    • 2 years ago
  10. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    well the only assumption I think I can make is not q

    • 2 years ago
  11. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    and I can only use things I can derive from the 3 axioms or modus ponens

    • 2 years ago
  12. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    for example I could use axiom 1 to write ((~q) ->(p->(~q))

    • 2 years ago
  13. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    and use that like an assumption

    • 2 years ago
  14. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    at least this is my understanding of the hilbert proof system

    • 2 years ago
  15. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    This is my first time using it

    • 2 years ago
  16. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yeah, I only used axioms, the third axiom states the manipulation above, and there needs to be some relation for p, q, otherwise we can only imply \(q\to q\), or some other singly-defined tautology.

    • 2 years ago
  17. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I don't understand how you went from (p→q)→(¬q→¬p) to the end

    • 2 years ago
  18. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I can get to this point by manipulating the axioms

    • 2 years ago
  19. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    how can you get the end to be just (not p)

    • 2 years ago
  20. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    and I've never seen an ^ in any Hilber proofs before

    • 2 years ago
  21. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    You can take the first axiom (or a conjunction/disjunction operator, I don't know if you're allowed to use these, but that's what my proof contains): An explicit-axiom proof would look like this, for \[ (p\to q)\to (\neg q \to \neg p) \]Thus, MP: \[ \frac{\neg q\to\neg p,\neg q}{\therefore \neg p} \]

    • 2 years ago
  22. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I don't know what a conjunction/disjunction operator is. the only thing I have available to me are these axioms A1 (A -> (B->A)) A2 ((A -> (B->C)) -> ((A->B)->(A->C))) A3 (((~A) -> (~B)) -> (B->A)) and modus ponens hich states if we have A->B and A we can infer B

    • 2 years ago
  23. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Well, yeah, I've already proven it using only those.

    • 2 years ago
  24. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    sorry for not responding, I had to catch a bus

    • 2 years ago
  25. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    hmm maybe I'm confused about how you wrote it then

    • 2 years ago
  26. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    It's all right... but I've already shown the proof with only those 3.. I can re-write it wholly, if you wish...

    • 2 years ago
  27. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    well can you explain how you use each axiom at each step? From the examples I've been provided it seems like you need to start with an assumption like (~q) or one of the axioms with values substituted into it

    • 2 years ago
  28. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm a little confused how you begin with (p→q)→(¬q→¬p)

    • 2 years ago
  29. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    actually that is axiom 3 isn't it with A=¬p and B=¬q

    • 2 years ago
  30. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    We assume: \[\neg q, (p\to q) \]To be true, along with the three logical actions in the Hilbert system. We begin: As given by Axiom (3) which states: \[ \left ( \lnot \phi \to \lnot \psi \right) \to \left( \psi \to \phi \right) \]Then: \[ (p\to q)\to (\neg q \to \neg p) \](Since, we can replace it the logical inverses of each operator) So, by the above: \[ \frac{\neg q\to\neg p,\neg q}{\therefore \neg p} \]And we're done.

    • 2 years ago
  31. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, it is.

    • 2 years ago
  32. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    The Hilbert System allows one to replace any single instance \(\phi\) with whatever other instance we wish, so long as it holds true.

    • 2 years ago
  33. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    could you please explain where this part comes from? ¬q→¬p,¬q

    • 2 years ago
  34. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    We know by our previous deduction that: \[ \neg q\to \neg p \]Since we have: \[ \neg q \]Therefore: \[ \neg p \](Modus Ponens)

    • 2 years ago
  35. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    can you apply modus ponens to the end of a statement like that?

    • 2 years ago
  36. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    From what I've seen they only apply modus ponens to the whole thing

    • 2 years ago
  37. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Well, the statement I gave IS Modus Ponens (MP). We're simply taking our final logical deduction given by our previous.

    • 2 years ago
  38. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    but we are only applying it to (¬q→¬p) rather than the whole (p→q)→(¬q→¬p) can we assume (¬q→¬p) based on (p→q)→(¬q→¬p)?

    • 2 years ago
  39. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    or are you getting the assumption that (¬q→¬p) from somewhere else?

    • 2 years ago
  40. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    No, the assumption is reached by the previous statement. I think it's easier to write it out. We have that (p implies q) implies (not q implies not p). Therefore, by our assumption, we can therefore say that, for anything that holds in (p implies q), such will also hold in (not q implies not p). With this, we give the statement that not p is true based upon the fact that not q is true as the statement previously given follows.

    • 2 years ago
  41. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Treat \(p \to q\) as our premise, and \(\neg q \to \neg p\) as our conclusive statement. Because we can say that, if \(\Gamma\vdash a\to b \), then, by MP: \[ \frac{\Gamma\vdash a}{\Gamma \vdash b} \]

    • 2 years ago
  42. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    so you are assuming (p→q) to infer that (¬q→¬p) then

    • 2 years ago
  43. LolWolf Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yep.

    • 2 years ago
  44. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I don't think I can use (p→q) as an assumption though. I think the only thing I can use as an assumption is (¬q) unless I can derive (p→q) from one of the axioms

    • 2 years ago
  45. bluebrandon Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    OK so I completely understand your solution now. But I need to write an explicit proof so I can't just convert (¬¬p→¬¬q)→(¬q→¬p) to (p→q)→(¬q→¬p). I need o show I can get the (¬¬p→¬¬q) with the axioms as well. Can you help me out with that please?

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.