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

Peirce's Law

  1. Oct 4, 2004 #1
    If someone out there could provide some guidance on this, I would greatly appreciate it! :biggrin:

    I am asked to 'proove' that Peirce's Law is a theorem in SD by providing a derivation.

    [(A > B)>A]>A

    Looks easy, no? Well I am totally :confused: And of course, a search of examples on the internet was absolutely no help. So, if someone could give me a hint as to at least how to start, that would be great!

  2. jcsd
  3. Oct 4, 2004 #2
    Start with the Law of the Excluded middle and proceed by disjunction elimination. Alternatively, negate Pierce's law and proceed to derive a contradiction. What's the problem?
  4. Oct 4, 2004 #3
    I believe I will have to go the negation route, as the Law of the Excluded Middle isn't mentioned our book or class (go figure).

    I really wish this sort of thing came naturally to me. :/
  5. Oct 4, 2004 #4
    Does your logic teacher allow you to enter (P v ~P) at the beginning of a derivation? If so, then that is probably how you should begin this proof. If not, haven't you learned how to derive (P v ~P) from no premises? Are you allowed to use the DeMorgan equivalences in your derivation, or do you have to prove those too?
    Last edited: Oct 4, 2004
  6. Oct 5, 2004 #5
    Anyone by chance know of any website where I can find this derivation worked out? I really would like to understand it for a test I have coming up next week. Any help would be greatly appreciated. The only thing I can figure out up to this point is that I must do it with indirect proof.
  7. Oct 5, 2004 #6
    Can you only use the introduction and elimination rules?
  8. Oct 5, 2004 #7
    Yep! That's pretty much it. The intro and elim rules of SD. Sorry I had not seen your response earlier. :)
  9. Oct 5, 2004 #8
    Do you know how to derive sentences that are DeMorgan equivalents of one another? For instance, if you are given:

    1. (P > Q)

    Do you know how to derive

    2. ~P v Q


    3. ~(P & ~Q)
  10. Oct 5, 2004 #9
    I believe therein lies the problem. DeMorgen's was so little touched on in class, and the book that we have does not explain that at all (I have looked). In fact, the book provides plenty of EASY derivations, and leaves the hard ones in the exercises. Of course I am not too proud to admit that perhaps the problem lies with me :-X I do tend to get lost in the derivations.

    To answer your question, off the top of my head, no. That bothers me - seems like it would be an easy derivation to perform.
  11. Oct 10, 2004 #10


    User Avatar
    Staff Emeritus
    Gold Member
    Dearly Missed

    Couldn't you just do it with truth tables if all else failed?
  12. Jun 24, 2005 #11
    Truth-table method is a decision procedure, not a method of proof.
  13. Jun 24, 2005 #12
    The fastest proof of Peirce's Law is to prove the contrapositive ¬P→¬((P→Q)→P) :smile:
  14. Jun 24, 2005 #13


    User Avatar
    Gold Member

    Well, if anyone cares:
    1)) (A -> B) -> A [conditional proof]
    2)) ~(A -> B) v A [1, (P -> Q) <=> (~P v Q)]
    3)) ~(~A v B) v A [2, (P -> Q) <=> (~P v Q)]
    4)) (~~A & ~B) v A [3, (~(P v Q)) <=> (~P & ~Q)]
    5)) (A & ~B) v A [4, ~~P <=> P]
    Now you just need to distribute A, and the rest should be clear.

    I don't see how the contrapositive is faster- am I missing something?
    1)) ~A [conditional proof]
    2)) ~A v B
    3)) A -> B
    4)) (A -> B) & ~A
    5)) ~~((A -> B) & ~A)
    6)) ~(~(A -> B) v ~~A)
    7)) ~(~(A -> B) v A)
    8)) ~((A -> B) -> A)
    9) ~A -> ~((A -> B) -> A)
    This is the same length as the one above and seems less straightforward.
  15. Jun 24, 2005 #14


    User Avatar
    Science Advisor
    Homework Helper

    honestrosewater, your proof seems to use a replacement rule my book calls "Implication" (the rule that (P --> Q) can be interchanged with (~P v Q)), which is not a rule of SD.

    Code (Text):
    1  | | ((A > B) > A)             Assumption
       | |--------------------------
    2  | | | ~A                      Assumption
       | | |------------------------
    3  | | | | A                     Assumption
       | | | |----------------------
    4  | | | | | ~B                  Assumption
       | | | | |--------------------
    5  | | | | | A                   3 Repitition
    6  | | | | | ~A                  2 Repitition
    7  | | | | B                     4, 5-6 Negation Elimination
    8  | | | (A > B)                 3, 7 Conditional Introduction
    9  | | | A                       1, 8 Conditional Elimination
    10 | | | ~A                      2 Repitition
    11 | | A                         2, 9-10 Negation Elimination
    12 | ((A > B) > A) > A           1, 11 Conditional Introduction
  16. Jun 24, 2005 #15


    User Avatar
    Gold Member

    Bah, rules schmules. :tongue2: I guess I need to get used to SD (so far it seems to make things harder). Does it not have any replacement (equivalence) rules?

    Can you prove the contrapositive in fewer steps?
  17. Jun 24, 2005 #16


    User Avatar
    Science Advisor
    Homework Helper

    SD would make things harder generally, since SD+ contains all the rules of SD plus:

    Inference Rules:
    1. Hypothetical Syllogism
    2. Disjunctive Syllogism
    3. Modus Tollens

    and 10 replacement rules such as Implication, DeMorgan's, Double Negation, Transposition (which tells you that (A --> B) and (~B --> ~A) are interchangeable), Distributivity, Associativity, etc. I've only taken one course in logic, so hopefully SD+ is a standard derivation system, and what I've said above makes sense beyond the context of my course textbook.

    So no, SD has no replacement rules. It has:

    Negation Intro.
    Negation Elim.
    Conjunction Intro.
    Conjunction Elim.
    Conditional Intro.
    Conditional Elim.
    Disjunction Intro.
    Disjunction Elim.
    Equivalence Intro.
    Equivalence Elim.

    I'm not sure if you can prove the contrapositive in fewer steps, mind you, the contrapositive does not immediately yield the desired theorem since transposition is not a rule of SD (of course, all the rules of SD+ are derivable from SD). Another 6 lines would be necessary to take the contraposition to the desired statement. Also, I'm not sure if the proof I gave was the shortest one in SD for the theorem, it's just the first thing that came to my head.

    | ~A
    | | ((A > B) > A)
    | |=====================
    | | | A
    | | |====================
    | | | | ~B
    | | | |==================
    | | | | A
    | | | | ~A
    | | | B
    | | (A > B)
    | | A
    | | ~A
    | ~((A > B) > A)
    (~A > ~((A > B) > A))

    The proof (well, my proof) of the contraposition is 12 lines, just like the one I gave for the original.
  18. Jun 24, 2005 #17


    User Avatar
    Gold Member

    Okay, SD+ sounds like what I'm used to (the system in Copi & Cohen's Intro with some minor changes).
    That's funny that both yours and mine (the first ones we thought of, at least) were the same length both ways. I'll look for shorter proofs later.
  19. Jun 25, 2005 #18
    A more elegant way to use SD

    Derivation system SD is more elegant than other systems of natural deduction such as that of Copi's, thanks to F.B.Fitch. :smile: Now there is a trend of using SD system in logic books as the only system of natural deduction.

    To make the system more elegant, my professor reduces the number of SD rules to eight, deleting the rules of biconditional and the rule of reiteration.

    BTW, the idea of subderivaion can be used without using vertical lines in proofs. See my demonstration below:

    ├(A → ~B) → (B → ~A)

    1) A → ~B               (Assumption) Discharged
    2) B                  (Assumption) Discharged
    3) A                 (Assumption) Discharged
    4) ~B                1, 3, →E
    5) B & ~B              2, 4, &I
    6) ~A                3-5, ~I
    7) B → ~A              2-6, →I
    8) (A → ~B) → (B → ~A)      1-7, →I
  20. Jun 25, 2005 #19


    User Avatar
    Gold Member

    By 'more elegant' do you just mean 'has less rules', or is there something more? I don't mind redundancy in the rules if it makes things easier. I use replacement rules so often, I'm interested to see how I fare without them. I'm just now writing down the SD rules.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook