13.2 Contradiction Principle
Hopefully the examples from the last section helped you see that reductio is a natural proof method. But it might not be intuitive to you why it is valid.
In this section we revisit the topic of contradictions to show why reductio is valid.
Since we'll be talking about contradictions a lot, it will be helpful to add a symbol to BOOL that stands for a contradiction. We'll use this symbol: ⊥.
Syntactically, ⊥ is a sentence, not a connective. As a sentence of BOOL, it can appear in complex sentences, such as P&⊥ or ~⊥.
Semantically, it is a tautological contradiction. That means that its truth table is all Fs. Recall that the truth table for every atomic sentence is T and F. That means that ⊥ cannot be an atomic sentence, since it is all Fs. Think of it as shorthand for a complex sentence like P&~P.
For a mnemonic, think of ⊥ as an upside-down T: a contradiction is like the inverse of truth. Unfortunately the ⊥ symbol is very common in logic but uncommon to find on a keyboard, so we must decide on a way to write it with a keyboard. Sometimes logicians use an underscore-vertical line-underscore like this: _|_, but that is rather bit laborious. So we will just write #, which is the closest single key to the intersecting lines of ⊥.
Here's how to handle truth tables with ⊥. If we want to truth table P&⊥, there is just one atomic, P. (We said you can think of ⊥ as shorthand, but don't actually replace it with another sentence.)
If you conjoin ⊥ with any sentence, you still get a contradiction.
Now try this one: Qv⊥.
Disjoining a sentence with ⊥ just returns the same truth function as the sentence.
Now let's see how contradictions behave in arguments. You already know one weird fact about contradictions and validity: a contradiction entails anything.
R is just a random sentence here, that has nothing to do with these premises, but all of these arguments are valid:
- P&~P ⇒ R
- Q&~Q ⇒ R
- ⊥ ⇒ R
That means any contradiction entails itself:
- P&~P ⇒ P&~P
- Q&~Q ⇒ Q&~Q
- ⊥ ⇒ ⊥
And a contradiction entails every other contradiction:
- P&~P ⇒ Q&~Q
- P&~P ⇒ ⊥
- ⊥ ⇒ P&~P
Here's the key question:
If something is a not a contradiction, then it is possibly true. In order for that to entail a contradiction, the contradiction would have to be true whenever it is true. But a contradiction is never true. So a non-contradiction can never entail a contradiction: there would always be a counterexample to validity, where the premise it true but the contradiction false.
This fact is important enough to give it a name. We'll call it the contradiction principle: only a contradiction can entail a contradiction.
The contradiction principle can help us understand why reductio is a valid proof method.
Let's say we have three sentences that entail a contradiction: A, B, C ⇒ ⊥. What the contradiction principle tells us is that A, B, and C make a contradictory set, because they must be contradictory to entail a contradiction. If they could all be true at once, then there would be a counterexample and they wouldn't actually entail the contradiction.
Next, let's say what we know A and B are true. Since A, B and C can't all be true together, that means C is false, and thus ~C is true.
Of course, the same holds for any other grouping. If we know that A and C are true, then B must be false and ~B true.
Here's how this helps us understand reductio. Let's say we are given an argument like this:
If we can prove this by reductio, that means we can assume C and show that A, B, C ⇒ ⊥. Now we can see why that means the argument really is valid: if A, B, C ⇒ ⊥, then whenever A and B are true, ~C must be true too, which is just what validity says.
So if reductio ever seems mysterious, go back and think about the contradiction principle again.
Here's an example. Let A = If Q, then P. Let B = ~P. And let C = Q.
1. If Q, then P
To do a reductio, we assume Q and show that a contradiction results. Indeed it does: Q and premise 1 entail P, and that contradicts premise 2. Since Q is inconsistent with those premises, ~Q must be true whenever they are.
We singled out C to be negated just because the argument gave us A and B as premises. You can see that the other groupings also give valid arguments: for example, A and C here entail ~B.
1. If Q, then P
3. ~~P (or you could just write P here)
When we do a reductio, we assume ~P, and we already know that creates a contradiction with the premises. So ~~P follows from if Q, then P and Q.