How a proof by contradiction works

So, we want to show that p is true.

In a proof by contradiction, we start out by saying:

• "Suppose not. That is, suppose that p is not true.
• Instead, ¬p is true."

We then show that this leads to a contradiction, a statement like (q ∧ ¬q)

That is, we show that ¬p→(q ∧ ¬q), where (q ∧ ¬q) is some contradiction

But, how does this allow us to conclude that p is true?

Well, we know that (q ∧ ¬q) is always false. Thus if we show that ¬p→(q ∧ ¬q), we have shown that ¬p→F.

That is, we have shown that (¬p→F) is a true statement.

And we know that a→b is equivalent to writing ¬a ∨ b

• For justification, see first line of table 7 on p. 25
  • We use a,b instead of p,q to avoid confusion with the p and q we are already using).
• Or, check it by a truth table:  

  a	b	a→b	¬a	b	¬a ∨ b
  T	T	T	F	T	T
  T	F	F	F	F	F
  F	T	T	T	T	T
  F	F	T	T	F	T

Thus if (¬p→F) is true, then (¬(¬p ) ∨ F) is true, i.e. ( p ∨ F) is true

By the identity law ( p ∨ F) ≡ p we have that p is true.

• The identity law is the first line of table 6 on p. 24.

By now, you should see that these tables on p. 24 and 25 are pretty handy. If you haven't read through the textbook sections that surround these tables, now would be a good time to do that.

Some links to discussions of proof by contradiction:

• by Larry Cusik at CSU Fresno
• by Henry Cohn at Microsoft Research (on pitfalls of proof by contradiction)
• from delphiforfun website (describes the connection with modus tollens)

P. Conrad, 04/09/2008