Seeks Guidance on Proving Peirce's Law

[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

 

[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?

 

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

 

[cogito]

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

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?

 

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

 

[cogito]

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.

Can you only use the introduction and elimination rules?

 

[feralius]

Can you only use the introduction and elimination rules?

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

 

[cogito]

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

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)

 

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

 

[selfAdjoint]

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

 

[PhiloLearner]

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

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

 

[PhiloLearner]

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

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

 

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

 

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

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

 

[honestrosewater]

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.

Bah, rules schmules. 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?

 

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

 

[honestrosewater]

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.

Okay, SD+ sounds like what I'm used to (the system in Copi & Cohen's Intro with some minor changes).

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.

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.

 

[PhiloLearner]

A more elegant way to use SD

Okay, SD+ sounds like what I'm used to (the system in Copi & Cohen's Intro with some minor changes).

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

 

[honestrosewater]

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.

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.