# Peirce's Law

1. Oct 4, 2004

### feralius

If someone out there could provide some guidance on this, I would greatly appreciate it!

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 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!

Bobby

2. Oct 4, 2004

### cogito

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?

3. Oct 4, 2004

### feralius

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. :/

4. Oct 4, 2004

### cogito

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
5. Oct 5, 2004

### feralius

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.

6. Oct 5, 2004

### cogito

Can you only use the introduction and elimination rules?

7. Oct 5, 2004

### feralius

Yep! That's pretty much it. The intro and elim rules of SD. Sorry I had not seen your response earlier. :)

8. Oct 5, 2004

### cogito

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

and

3. ~(P & ~Q)

9. Oct 5, 2004

### feralius

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.

10. Oct 10, 2004

Staff Emeritus
Couldn't you just do it with truth tables if all else failed?

11. Jun 24, 2005

### PhiloLearner

Truth-table method is a decision procedure, not a method of proof.

12. Jun 24, 2005

### PhiloLearner

The fastest proof of Peirce's Law is to prove the contrapositive ¬P→¬((P→Q)→P)

13. Jun 24, 2005

### honestrosewater

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.

PhiloLearner,
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.

14. Jun 24, 2005

### AKG

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

15. Jun 24, 2005

### honestrosewater

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?

16. Jun 24, 2005

### AKG

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:

Repitition
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.

17. Jun 24, 2005

### honestrosewater

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.

18. Jun 25, 2005

### PhiloLearner

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. 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

19. Jun 25, 2005

### honestrosewater

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.