Peirce's Law [Archive] - Physics Forums

View Full Version : Peirce's Law

feralius

Oct4-04, 05:51 PM

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!

Bobby

cogito

Oct4-04, 07:32 PM

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

Oct4-04, 08:24 PM

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

Oct4-04, 09:21 PM

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

Oct5-04, 01:45 PM

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

Oct5-04, 05:30 PM

feralius

Oct5-04, 06:32 PM

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

Oct5-04, 06:44 PM

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

Oct5-04, 08:21 PM

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

Oct10-04, 07:37 PM

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

PhiloLearner

Jun24-05, 12:35 PM

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

Jun24-05, 12:45 PM

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

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

honestrosewater

Jun24-05, 09:09 PM

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

Jun24-05, 09:48 PM

honestrosewater

Jun24-05, 10:34 PM

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

AKG

Jun24-05, 10:52 PM

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

Jun24-05, 11:04 PM

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

Jun25-05, 03:26 AM

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

honestrosewater

Jun25-05, 06:00 AM

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