Conditional and Indirect Proof

Consider this example:

If it rains we’ll either go to the movies or stay home and watch basketball.  But you’re sick of basketball, so if it rains we’ll go to the movies.  

This can be done fairly quickly using IMP and AS to set up a DS, finishing with IMP to return us to the horseshoe in the conclusion:

 

1. R ⊃ (M v B)

2. ~B / R ⊃ M

3. ~R v (M v B)     IMP 1

 

4. (~R v M) v BU      AS 3

 

5. B v (~R v M)      CM 4

 

6. ~R v M      DS 2,5

 

7. R ⊃ M      IMP 6

 

That’s not too hard, but it’s fairly unintuitive; you have to know to just manipulate the squiggles by rules, specifically to change the horseshoe to a wedge in order to change it back. Once you’ve done it several times, you can get used to it. But there is a very intuitive strategy known as Conditional Proof (CP) that you can use when you notice that the statement you need to derive is a conditional statement, as the conclusion of this one is: If it rains we’ll go to the movies.

 

Conditional Proof (CP) proceeds by letting you make an assumption, which is like saying to yourself, “OK, so what if it does rain, what will happen?,” as long as at the end of your musings from this assumption, you remember to sum it all up with a reference back to the fact that you began from that assumption. Here, you’d say:

 

Well if it does rain, then we’ll either go to the movies or watch basketball. But since you’re sick of watching basketball, that’s not really an option.  So there’s really only the one option: if it rains we’ll go to the movies.

 

We need a new element of notation to accommodate this. To indicate an assumption is being made, we do two things: 1) Indent the assumed line,or, if the website you’re working on won’t save the indentation, place a vertical line, |, in front the lines that are subject to the assumption, and 2) justify it by the notation “ACP,” which means “Assumption for a Conditional Proof.”

 

 

1. R ⊃ (M v B)

2. ~B / R ⊃ M

|      3. R     ACP       We are assuming R, to see what it results in.

| 4. M v B       MP 3,1 Very obvious

| 5.  M            CM, DS 2,4 Also very easy to spot

6.  R > M       CP 3-5

 

We’re done, because the assumption R, led to the consequent we wanted it to lead to, M, at line 5. That’s what this line 6 says (“R leads to M,” or “If R then M”). In this particular example, we barely saved any time in comparison to the other approach (in fact we only did because of putting the DS and CM on the same line), but in many cases, you’ll be done with the proof if you use CP faster than you’d even suspect how to get started without it.

 

Here’s another example, which we can approach in either of these two ways again.

 

If Imus goes off the air, then if Sharpton is a guest on Bill Maher’s Real Live, they will disagree with each other. Sharpton is a guest on Real Live. So if Imus goes off the air, Sharpton and Maher will disagree with each other.

Here’s the non-CP way to do it:

1. I ⊃ (S ⊃ D)

2. S / I ⊃ D

3. ~I v (S  ⊃ D)    IMP   1

4.  ~I v (~S v D)    IMP 3

5. (~I v ~S) v D     AS 4

6. (~S v ~I) v D     CM  5

7. ~S v (~I v D)     AS 6

8. ~~S       DN 2

9. ~I v D     DS 7, 8

10. I ⊃ D      IMP 9

 

And here’s the CP approach:

1. I ⊃ (S ⊃ D)

2. S / I ⊃ D

| 3. I     ACP

| 4. S ⊃ D    MP 1,3

| 5. D     MP 2, 4

6. I ⊃ D       CP 3-5

 

Before we look at the next one, it’s time to talk about how you know what to assume, what to introduce by the line “ACP.” The answer is always easy to find, because it is always the antecedent of the conditional sentence that you want to generate. (It is not always the antecedent of the conclusion, because sometimes you can use this approach to get a line that will help you get the conclusion a little later; but 90% of the time, when you use CP, it will in fact be to generate a conditional statement which is the conclusion.)

So, you should be able to tell what the antecedent would be for CP proofs if these statements were the proposed conclusions:

a) B ⊃ (V v H)

b) (B v Y) ⊃ G

c) [(D ≡ F) v T] ⊃ (F . R)

d) C ⊃ (D ⊃ ( F ⊃ T))

Always the antecedent of the line you’re trying to generate. The whole antecedent, but only the antecedent. (Once in a while, for fun, you might try assuming the negation of the consequent instead, since by TRAN, you can always turn that into the antecedent later!)

Now, you don’t use CP unless you are clear on another point, besides knowing what to bring in as your ACP assumption. The other thing you have to know is where you are going, what to shoot for, if you will. But that’s easy to know too, it’s always the consequent of the conditional that you are trying to generate. (Though, if you take me up on trying to do one by assuming the negation of the consequent of the desired conditional, you’d then be aiming for the negation of the antecedent, so that, at the very end, you could flip it with TRAN.)

Let’s look at another example before we introduce the possibility of multiple CPs:

If you’re the Vice President and your aide is found guilty of lying to federal investigators, then if you don’t go on the record to distance yourself from him, you’ll be under a cloud on the cover of Time. (Let’s pretend we’re talking to Mr. Cheney, so that “you” refers to the right person): Your aide, Scooter, was found guilty of just that, and you didn’t distance yourself from him. So, if you’re the Vice-President, you’re going to be under a cloud on the cover of Time.

1. (V . G) ⊃ (~R ⊃ U)

2. G . ~R / V ⊃ U

What to do? The conclusion is a conditional, so we assume its antecedent, and work until we can get its consequent:

| 3. V    ACP

| 4. G     2   SM

| 5. V . G    3,4 CN

| 6. ~R ⊃ U    MP 1,5

| 7. ~R      CM    SM 2

| 8. U       MP 6, 7 That’s the consequent we want so, we’re done!

9. V ⊃ U      CP 3-8 That’s how to say “we’re done.”

 

 

9 Conditional Proof examples

Using CP more than once in a proof

Being clear on how to determine what the assumption should be, and on what the goal of the CP sequence is (i.e., when to quit it) are crucial. And they are not complicated things to see; they are usually both staring you in the face: the antecedent and the consequent of the conditional statement that you need to produce. This is why it is actually much easier than it looks at first, to do a CP inside another CP, and maybe to even do another one inside of that one. If example d) above were a conclusion:

C ⊃ (D ⊃ ( F ⊃ T))

The ACP line for this would be C, and we’d be finished when we arrived at the line D ⊃ (F ⊃T).

But one way to get D ⊃ (F ⊃T) is to assume D and work until the line F ⊃ T results.

And, since F ⊃ T is also a conditional statement, it could be possible to assume F and work until T showed up.

That is, we could say, “alright, let’s assume C, and let’s assume D, and let’s assume F, and see what happens.” In a few steps, we find that T happens, so we say “so F makes T happen, and that happened because we assumed D, and that happened because we’d assumed C!”

Here’s what it would look like:

| 2. C    ACP

| | 3. D    ACP

| | | 4. F    ACP

| | | 5…

| | | 6…

| | | 7. T

| | 8. F ⊃ T    CP 4-7

| 9. D ⊃ (F ⊃ T)    CP 3-8

10. C ⊃ ( D ⊃ (F ⊃ T))    CP 2-9

 

 

 

Try that in a proof:

 

If Hyperion and Starbucks are both closed, then if you insist on having coffee, you’re going to go to MacDonald’s but you’ll wish you hadn’t. If Hyperion is closed, then Starbucks is too. So, if Hyperion is closed, if you insist on having coffee, you’re going to wish you hadn’t.

 

1. (H . S) ⊃ [C ⊃ (M . W)]

2. H ⊃ S                / H ⊃ (C ⊃ W)

|3.  H     ACP Why “H”? Because it’s the conclusion’s antecedent.

 

| | 4.  C      ACP Why “C”? Because it’s the antecedent of the consequent of the conditional you’re after: ||C > W, the consequent of the conclusion.

 

| | 5.   S        MP 2,3

| | 6.  H . S      CN 3,5

| | 7.  C ⊃ (M . W)       MP 1,6

| | 8.  M  . W     MP 7, 4

| | 9.  W        CM, SM 8

|10.   C ⊃ W      CP 4-9 This is the end of the second sequence begun with an “ACP”

11.    H ⊃ (C ⊃ W)       CP 3-10 This is the end of the first sequence begun with an “ACP”

 

Moral: when the consequent of the conditional is a conditional, then you do a CP within a CP. Two CP’s means you wind up with two horseshoe statements: p > (q > r).

It also is possible that you might do more than one CP but do them independently of each other, in order to generate two distinct conditional statements. When is that likely to happen? How about when the statement you need is a triple bar statement, e.g., when the conclusion is a triple bar statement? Then you might do this:

 

| p      ACP

|.

|.

|.

|  q

p > q    CP

| q    ACP

|.

|.

|.

| p

q ⊃ p    CP

(p ⊃ q) . (q ⊃ p)    CN

p ≡ q    EQ

 

 

 

Here are some exercises you can try:

 

1.

1. F ⊃ E

2. (F ∙ E) ⊃ R / F ⊃ R

 

 

2.

1. G ⊃ T

2. (T v S) ⊃ K / G ⊃ K

 

 

3.

1. (G v H) ⊃ (S . T)

2. (T v U) ⊃ (C . D) / G ⊃ C

 

 

4.

1. A ⊃ ~(A v E) / A ⊃ F

 

 

5.

1. H ⊃ (I ⊃ N)

2. (H ⊃ ~I) ⊃ (M v N)

3. ~N / M

 

 

6.

1. M ⊃ (K ⊃ L)

2. (L v N) ⊃ J / M ⊃ (K ⊃ J)

 

 

And here are some word problems:

1. If high tech products are exported to Russia, domestic industries will benefit. If the Russians can effectively use high tech products, their standard of living will improve. So if high tech products are exported there, and they can effectively use them, their standard of living will improve and domestic industries will benefit.

 

2. A doctor must disconnect a dying patient from a respirator only if the fact that patients are self-determining implies that the doctor must follow the patient’s orders. If a dying patient refuses treatment, the doctor must disconnect the patient from a respirator and the patient will die peacefully. Patients are self-determining, so if a dying patient refuses treatment, the doctor must follow the patient’s orders.

 

3. If astronauts attempt interplanetary space travel, heavy shielding will be required to protect them from solar radiation. If massive amounts of either fuel or water are carried, the spacecraft must be very large. Therefore if heavy shielding is required to protect them from solar radiation only if massive amounts of fuel are carried, then if astronauts attempt interplanetary space travel, the spacecraft must be very large.

 

 

 

Indirect Proof

 

That same idea -of indenting to indicate that we’re making an assumption-is used in another very useful strategy for writing formal proofs, one known as Indirect Proof. This has a very old lineage, being known in medieval times as Reductio ad absurdum, which means showing that a position leads to an absurdity. Here’s how it goes in general:

 

You assume the negation of the conclusion you are trying to prove. From that assumption, you derive a self-contradictory statement. But, as Modus Tollens shows us, if we then deny that that self-contradictory statement is true (i.e., we say that that statement can’t be true), then the antecedent (the assumption) that led to it must be false. Hence the conclusion we are interested in must be true, since it and the now-disproven assumption are negations of one another.

 

Instead of writing “ACP” as the justification, we’ll write “AIP” since the assumption is for an Indirect Proof:

 

1. (S v T) ⊃ ~S   / ~S

|2. ~~S      AIP

|3. ~(S v T )      MT 1,2

| 4. ~S . ~T      DM 3

| 5. ~S       SM 4

| 6. S       DN 2

| 7. S . ~S       CN 5,6

8. ~S      IP 2-7

As this shows, once a self-contradiction is shown, the convention for writing an Indirect Proof is to then quit the indented sequence and write just the conclusion, followed by the justification “IP.” This means that the Indirect Proof has been accomplished: by showing that the assumption led to a self-contradiction, one has shown that the assumption was false, and hence that its negation (the conclusion) is true.

Indirect Proof is foolproof. It always works. That doesn’t mean it’s always a good choice as a strategy, but if you are looking at a set of premises and a conclusion and you just have no idea what to do, you can go into IP mode, and something will start happening. The one trick is to make sure you really do what you are supposed to do: negate the conclusion as your assumption. That means the whole conclusion, no matter how long or compound the statement may be. Then you’ll have to do some work rewriting that negated statement, by rules like DM or IMP and DIST.

 

Here’s an example:

1. R ⊃ B

2. R ⊃ (B ⊃ F)

3. B ⊃ (F ⊃ H)    / R ⊃ H

 

Now, since this has a conditional for its conclusion, CP is the smarter choice, but we’re going to walk through it with IP to exhibit how it can apply.

 

|4. ~ (R ⊃ H)      AIP

|5. ~( ~R v H)      IMP 4

| 6. ~~R . ~H      DM 5

| 7. R . ~H      DN 6

| 8. R       SM 7

| 9. B      MP 1,8

| 10. F ⊃ H      MP 9,3

| 11. ~H       CM, SM 7

| 12. ~F      MT 11,10

| 13. B ⊃ F      MP 8,2

| 14. F       MP 9, 13

| 15. F . ~F      CN 14,12

16. R ⊃ H      IP 4-15

 

As you see, it took lines 5, 6, and 7 to make the information in the negated conditional available and useable, but once it is opened up, and you can break it down into pieces, you can begin taking other lines apart. If you keep your eyes open for it, you’ll eventually encounter some statement (let’s call it “p”) and some other statement, “~p,” which conjoin to make a self-contradiction. Any self contradiction is fine. It need not even be a simple statement and its contradictory; it could be a compound statement conjoined to its contradictory-like H v M on the one hand, and ~(H v M) on the other.

 

9.5 Indirect Proof

 

Here are some more exercises. Decide whether CP or IP is the better choice.

1

1. (K ⊃ K) ⊃ R

2. (R v M) ⊃ N / N

 

 

2.

1. (C . D) ⊃ E

2. (D . E) ⊃ F / (C . D) ⊃ F

 

 

3.

1. H ⊃ (L ⊃ K)

2. L ⊃ (K ⊃ ~L) / ~H v ~L

 

 

4.

1. S ⊃ (T v ~U)

2. U ⊃ (~T v R)

3. (S . U) ⊃ ~R / ~S v ~U

 

 

 

5.

1. ~A ⊃ (B . C)

2. D ⊃ ~C / D ⊃ A

 

 

 

 

6.

1. [C ⊃ (D ⊃ C)] ⊃ E /E

 

 

 

 

7.

1.(R . S) ≡ (G . H)

2. R ⊃ S

3. H ⊃ G / R ≡ H

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>