Results 1 to 15 of 15

Math Help - Proof of p implies (q implies p)

  1. #1
    Junior Member
    Joined
    Dec 2009
    Posts
    28

    Proof of p implies (q implies p)

    How do I prove this?
    p\rightarrow (q \rightarrow p)?
    I did the truth table, and I understand it, but I don't understand the proof in Cauman's book First order logic. Actually, I don't see how it makes sense.
    Here's what she did:


    How do I get q \rightarrow p just by two premises I introduced and repeated one of them?

    Please help.
    Thank you.
    Attached Thumbnails Attached Thumbnails Proof of p implies (q implies p)-screenshot.png  
    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
    Time to trot out emakarov's standard question in these sorts of situations: what inference rules are you allowed to use, and what are you calling them?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2010
    Posts
    28
    Hey,

    If you are assuming p and q in the proof, then you can prove p (because you are assuming it!). So, from p and q you can prove p in particular. Using conditional proof we can discharge one of our assumptions, in this case either p or q. So discharge q. Thus we have a proof of q -> p from p. Then you apply conditional proof again to get a proof of p -> (q -> p) from no assumptions.

    Hope this helps.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2009
    Posts
    28
    PREM in proof stands for premise, REPEAT is repeating a premise, CP stands for conditional proof.
    There are other rules, but I would really like to understand this proof first and then try to find others.

    Do I need to explain any of the rules above?

    Thank you very much for your help and sorry for my English.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    How does your conditional proof work? What is its schema?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Dec 2009
    Posts
    28
    This is conditional proof:


    I will look into it further.
    Thank you all.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    So, lines 2 and 3 appear to be a "sub-proof", as in the Fitch-style proof. You temporarily assume q. You can inject outside assumptions into a subproof, which gives you line 3. Then, because of the CP schema, you can now conclude q -> p. Line 4 is now back to the same proof-level as line 1. Then you just use CP again to get the conclusion. Does that help?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Jul 2009
    Posts
    107
    Quote Originally Posted by harriette View Post
    PREM in proof stands for premise, REPEAT is repeating a premise, CP stands for conditional proof.
    There are other rules, but I would really like to understand this proof first and then try to find others.

    Do I need to explain any of the rules above?

    Thank you very much for your help and sorry for my English.
    How do we know that REPEAT is a rule??
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    How do we know that REPEAT is a rule??
    The OP has the derivation of p -> (q -> p) where the right column seems to list the rules applied at each step, and REPEAT is one of them. Why are you asking?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Jul 2009
    Posts
    107
    Quote Originally Posted by emakarov View Post
    The OP has the derivation of p -> (q -> p) where the right column seems to list the rules applied at each step, and REPEAT is one of them. Why are you asking?
    I meant to say how do we prove that REPEAT is a rule??
    Follow Math Help Forum on Facebook and Google+

  11. #11
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    That's usually an axiom schema; that is, it's not usually something you have to prove. It's usually assumed. In this case, it's definitely assumed you can just do that.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Jul 2009
    Posts
    107
    Quote Originally Posted by Ackbeet View Post
    That's usually an axiom schema; that is, it's not usually something you have to prove. It's usually assumed. In this case, it's definitely assumed you can just do that.
    I hardly know of any axiom schema that uses the rule REPEAT as one of its axioms.

    Anyway we can prove De Morgans ,can we not??

    What kind of truth table will validate REPEAT as a tautology?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Jul 2010
    Posts
    28
    Alex,

    Repeat isn't an axiom, it's a rule of inference, much like modus ponens. We cannot state modus ponens as an axiom (assuming we have no other rules of inference), because we wouldn't be able to draw any inferences from it. Of course, MP has an associated axiom, i.e. p -> [(p -> q) -> q], but then so does repeat, i.e. p -> p (which is clearly tautologous).

    The rule of repeat usually isn't even stated as a rule, it is given as part of the definition of a proof, i.e. a proof from \Gamma to \phi is a finite sequence of formulas such that each member of the sequence is either an axiom, a member of \Gamma (REPEAT), or derived from other previous members of the sequence by means of some rule (which, in hilbert style presentations is simply MP).

    Hope this helps.
    Sam

    Correction: MP is an axiom of the proof-theory, but it's not a logical axiom. But in the proof-theory it's also an axiom that \Gamma implies phi for all phi in \Gamma.
    Last edited by sroberts; December 24th 2010 at 04:10 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Banned
    Joined
    Jul 2009
    Posts
    107
    Quote Originally Posted by roberts View Post
    Alex,

    Repeat isn't an axiom, it's a rule of inference, much like modus ponens. We cannot state modus ponens as an axiom (assuming we have no other rules of inference), because we wouldn't be able to draw any inferences from it. Of course, MP has an associated axiom, i.e. [p -> (p -> q)] -> q, but then so does repeat, i.e. p -> p (which is clearly tautologous).

    The rule of repeat usually isn't even stated as a rule, it is given as part of the definition of a proof, i.e. a proof from \Gamma to \phi is a finite sequence of formulas such that each member of the sequence is either an axiom, a member of \Gamma (REPEAT), or derived from other previous members of the sequence by means of some rule (which, in hilbert style presentations is simply MP).

    Hope this helps.
    Sam

    Correction: MP is an axiom of the proof-theory, but it's not a logical axiom. But in the proof-theory it's also an axiom that \Gamma implies phi for all phi in \Gamma.
    You mean p->p ,is REPEAT??
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Junior Member
    Joined
    Jul 2010
    Posts
    28
    No, I mean p -> p is an axiom which stands to the /rule/ of repeat just as p -> [(p -> q) -> q] stands to the /rule/ of modus ponens.

    Sam

    (In my previous post I stated MP's associated axiom wrongly; that's now been corrected.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. HK < G implies HK = KH
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 5th 2011, 12:38 AM
  2. [SOLVED] Proof that x^2 = 1 implies x = 1 or x = -1
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 19th 2010, 11:22 AM
  3. proof isomorphism implies elementary equivalence
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 27th 2009, 03:35 AM
  4. Replies: 2
    Last Post: September 22nd 2009, 05:56 AM
  5. Replies: 6
    Last Post: January 21st 2009, 02:13 PM

Search Tags


/mathhelpforum @mathhelpforum