Section Progress:

11.1 Proof by Cases

5 easy rules: &Elim, &Intro, ~Elim, vIntro, and Reit

So far we've learned five formal proof rules.

Now you have to do some reasoning:

We cover these two rules last because they are more complicated and harder to grasp. Each gets its own chapter: in this chapter we cover vElim and in the next we cover ~Intro. Each of these rules has an informal proof method that goes with it. So these two chapters do double duty, covering both the informal method and the formal rule.

vElim and Proof by Cases: how to reason from a disjunction (formally and informally)

Remember, Elim rules are for when you already have a connective and want to reason from it. So vElim is for when you have a v and want to use or eliminate it.

Proof by cases is just the name for informally reasoning from a disjunction.

To see how it works, try to figure out what number c is.

There's more than one way to prove your answer, but we want to focus on the way that uses a disjunction. Look at the 3-by-3 box in the middle. It needs 3 and 6. That means a = 3 or 6, and b = 3 or 6. You can immediately tell that means c = 9 (because 9 is only other number needed by that row).

But what if someone doesn't see that? How can you walk them through it, step-by-step? That's what proof by cases is for: walking someone through a proof that starts with a disjunction. Here's how it looks:

Proof by cases: we know a = 3 or 6. Case 1: assume a = 3. Since we also know b = 3 or 6, and a ≠ b, then b = 6. Since 9 is the last number needed for that row, that means c = 9. Case 2: assume a = 6. Then b = 3, and again c = 9. So we know that c = 9 in either case. Done.

Every disjunction gives you two or more possibilities, at least one of which must be true. We know, for example, that a = 3 or a = 6: one of those two possibilities must be true. When you only know a disjunction, you cannot just assert one of the disjuncts: we can't just infer that a = 3 (after all, it could be 6 and not 3).

But what we can do is temporarily assume a = 3, and see what follows. That is the key idea behind proof by cases. Because if we can show that some conclusion follows if a = 3 and it also follows if a = 6, then we know that the conclusion follows from the disjunction itself.

Basically, we don't even have to know which one it is, whether a = 3 or a = 6, since the conclusion, c = 9, follows whichever it is.

Guidelines: whenever you do proof by cases in an informal proof, (1) start with "Proof by cases" and (2) restate the disjunction you are using. Inside the proof, (3) create a case for each disjunct of that disjunction. To do that, explicitly write "Case 1: assume ..." and "Case 2: assume ..." You have to (4) prove the same conclusion follows in each case. Then (5) write "So we know that [the conclusion] in either case. Done."

Here's the specific plan we want you to follow to do proof by cases.

Step 1: When you start an informal proof from a disjunction, you must start by saying "proof by cases", to clarify for your audience what you are doing.

Step 2: Next, restate the disjunction you are using to structure the proof around.

Step 3: Then you need to create a case for every disjunct in the disjunction. To do that, explicitly write "Case 1: assume ..." and "Case 2: assume ..."

Step 4: You have to prove the same conclusion follows in each case. For example, once you can show that the conclusion follows in the first case, you stop and end that temporary assumption, and you move on to the second case.

Step 5: After you've shown that the conclusion can be derived in every case, write "So we know that [the conclusion] follows in every case. Done." (or something similar).

Let's see if you've got it. Here's an argument you might remember from the beginning of Chapter 1:

  1. One or more of these people is guilty: Pia, Quinn and Raquel.
  2. No one else was involved.
  3. Pia never works without Quinn. So if Pia is guilty, so is Quinn.
  4. Raquel never works alone.

The first premise is a disjunction, so we can use proof by cases to prove this. First, see if you can figure this out:

Now see if you can create an informal proof of that that Quinn is guilty, following our guidelines.

Sometimes proof by cases can get quite complicated, which is why it is helpful to be clear about the structure of your proof. For example, sometimes you'll use one disjunction to structure the proof, and you encounter another disjunction inside the proof by cases. That happened in the third case of this proof, when you figured out that if Raquel is guilty, so is Pia or Quinn. There are two ways to handle that situation.

First, if the inference is fairly obvious, like it was here, you can just explain what that entails.

The second option is to use proof by cases again, inside the first proof by cases. Since proof by cases is how we reason from a disjunction, this longer approach will always work. The important thing is to keep yourself from getting confused and mixing up cases. For example, make sure to call them "sub-case 1" and "sub-case 2" for the inner disjunction, so that you don't confuse them with case 1 and 2.

11.1 Proof by Cases