Section Progress:

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.

⊥: a tautological contradiction. Keyboard symbols: #.

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:

Contradiction Principle: only a contradiction can entail a contradiction.

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:

1. A
2. B
Thus,
3. ~C

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
2. ~P
Thus,
3. ~Q

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
2. Q
Thus,
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.

13.2 Contradiction Principle