Shantila's Inside Logic #5+

Sequents

From now on, instead of writing the cumbersome phrase

Given assumption(s) P, Q.. we can derive S

I will say simply

P,Q,... } S

using the symbol } to abbreviate the cumbersome phrase. For example, exercise (e) in the practice exercises 5.1 says

e. Given assumption ~~Q, we can derive Q.

This now can be written simply as:

e. ~~Q } Q

We will call any expression containing the new symbol a sequent. From now on, let us also adopt the policy of stating the sequent that we want to prove at the top of every proof. So, for example, in doing exercise 5.1(c) above, we first write the sequent being proved, then we write out the proof, which goes as follows.

c. P>Q, Q>R, ~~P } R

Let us break down this proof line by line. The three premises are simply introduced on lines 1, 2, and 3, one line for each premise:

We are trying to derive R from these three assumptions, using our Rules line by line. How can we do this? Let's try reasoning "backwards" based on what we are trying to derive. We are trying to derive R. Notice that R appears in line 2, as part of Q>R -- so if we can get Q, then we know we can use the rule MP to get R. Well, how can we get Q? Well look at line 1, it has P>Q, so if we can get P then we can use MP, this time to get Q. So how are we going to get P? Well, here is where the new rule DN helps. Line 3 has ~~P. So on line 4 we know we can use DN to write P:

and (as we envisioned we could do) we now use MP twice to get R on a line by itself:

And we are done! Be sure to keep in mind what the goal is when you are doing a proof -- in this case, the goal was to get R on a line by itself, based only on the assumptions 1,2,3. And we did that, using the Rules as we did in lines 4, 5, and 6.

Notice that every line in a derivation actually represents a sequent, since each line tells us that the sentence on the line can be derived from the assumptions for that line; recall that the assumptions for the line are listed as the numbers on the left on that line. Line 6 in the proof (just given) corresponds exactly to the sequent we wanted to prove. That sequent was

P>Q, Q>R, ~~P } R

and correspondingly line 6 tells us that from the statements on lines 1, 2, and 3 (namely, P>Q, Q>R, ~~P) we can derive R.

The numbers on the left in a proof are the Assumptions that the line "depends" upon in that proof. And what number(s) we have to write on the left is determined by the Rule that we use on that line. Every statement of a Rule will tell you how to determine what to put on the left. For Rule A, we just list the number of that very line (it is sort of trivial). We have two other rules so far. For MP, we always will use two (and only two) previous lines, and the numbers on the left will be all the assumptions for both of those two lines. For example, look again at line 5 in the proof just given. This line uses Rule MP together with the earlier lines 1 and 4. Now what are the assumptions of those lines 1 and 4? Well, look back and see: for 1 we can see it is just 1 itself; and for 4 it is 3, so the numbers we put on the left at line 5 are 1,3. For DN, we only use one earlier line (not two, as with MP) and the Rule DN says that the assumptions for the new line are simply all those of the one earlier line that we use.

There is no substitute for practice in using the Rules correctly, by proving sequents in the Practice exercises. If my explanations here are hard to follow, don't try to figure out everything at once. Simply practice doing proofs and come back and read the material later and it probably will make more sense because of your own experience in constructing proofs.

*Practice

5.4 Here is a list of some of the sequents we have proved so far using the three rules A, MP, and DN. You should prove each of these again. At this point you should keep practicing until you are able to prove each of these sequents with ease. (Yes, there will be a test!) To repeat, it is advisable to do each of these several times, until you are confident that you understand how to apply each of the rules in our system so far.

1 P>Q, P } Q

2 P>Q, Q>R, P } R

3 P>Q, Q>R, R>S, P } S

4 P>Q, P } ~~Q

5 P>Q, ~~P } Q

6 ~P } ~~~P

7 P>Q, Q>R, ~~P } R

8 P>~~Q, Q>R, ~~P } ~~R

9 ~~Q } Q

5.5 The following sequent is valid, and it can be proved. But the "proof" given below is phony! (a) Please explain what is wrong with this proof. (b) Give a good proof of this sequent.

P>~~Q, P } Q [phony proof]