1 of 2

15.4 Advanced Reductio

Reductio is such a useful technique because it gives us another sentence to work from: the new temporary assumption.

In BOOL if we don’t  have any premises at all, then reductio is the only possible way to get started.

To prove a tautology in BOOL (no premises), you always start with reductio.

When we don’t have any premises, the conclusion must be a logical truth. Since we’re talking about the truth-functional logic of BOOL, the conclusion must be a tautology.

Here’s a classic example: the excluded middle, namely Pv~P.

Since you already know the 5-step plan, we’ll let you figure it out for yourself. Just remember to start with a reductio!

If you figured that out, great work! If not, we’ll talk about the key ideas here and you can go back and try it again.

Don’t fool yourself that just reading about the solution is enough.

Don’t fool yourself that just reading about the solution is enough. Even if you got the proof the first time, re-solving past proofs is critical practice for deeper understanding and long-term retention.

The reductio assumption is ~(Pv~P). That gives us the key pattern of negation around disjunction, so we know we can do the 5-step plan.

That’s why we assumed P on line 2; build the disjunction on line 3, and eventually got ~P on line 5.

At line 6 there are several ways to continue. Maybe you wanted to do the 5-step plan again, on the second disjunct.

If so, that’s great: if you have a reliable tool and you know how to use it, then you have acquired a lot of skill.

In BOOL, don’t assume what you already know.

But in the proof we required you to find the shortcut. Here’s a tip: in BOOL, you don’t need to assume what you already know.

Why assume ~P on line 6, if you already know ~P on line 5? You can just do vIntro now!

If you didn’t solve the proof before, go back and do it now.

This proof is a template for proving many tautologies, since most tautologies in BOOL are wide-scope disjunctions.

The plan is: start a reductio; do the 5-step plan as many times as you need to; find a way to prove a contradiction with the results to finish the reductio.

Let’s see if you can do it. Prove this tautology: Pv~(Q&P)

This one was a little trickier, because the shortcut wouldn’t work. We had to do the 5-step plan a second time.

The 5-step plan lets us extract information out of the reductio assumption, and then we have to use that new information to complete the reductio.

Basically, the 5-step plan lets us extract information out of the reductio assumption, and then we have to use that new information to complete the reductio.

The information we get out is ~P on line 5 and Q&P on line 9. The last thing you have to do to solve the proof is notice that if you bring down P from Q&P, you get a contradiction with ~P.

Remember what you do with conjunctions: &Elim!

Sometimes the information you get out of the 5-step plan is even more complicated. You might then have to do proof by cases, or some other creative combination. But the overall plan is the same.