Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 8.3.6 Proving an Implication Using Contradiction

Suppose that we want to prove a claim of the form: p → q

Sometimes the easiest way to do that is by contradiction. We assume its negation (¬(p → q)) and derive a contradiction.

The form ¬(p → q) isn’t very easy to work with. Let’s massage it a bit:

[1] ¬(p → q)

[2] ¬(¬p ∨ q) Disjunctive Syllogism [1]

[3] ¬¬p ∧ ¬q De Morgan [2]

[4] p ∧ ¬q Double Negation [3]

Now it’s clearer what we should do: Assume both p and ¬q. Derive a contradiction. Of course, we could resolve that contradiction by giving up p. But we won’t. We’ll stick to p. That means that q must be true. In other words p → q.

In this example, we’ll assume the axioms of plane geometry, including that, through any two distinct points, there is exactly one straight line.

Prove that, if two distinct straight lines intersect, then they do so at only one point.

The proof is by contradiction. Assume that two lines L1 and L2 are distinct and that they intersect at two or more different points. Call two of those points p and r. Then those two points are on both L1 and L2. But there is exactly one straight line through those two points. This contradicts the hypothesis that L1 and L2 are distinct.