Proof by Contradiction

So far, we have looked exclusively at proofs by construction where our goal is to construct an object, e.g., an evaluation trace that provides evidence that a proposition holds. However, in some cases, it is not feasible to construct such evidence directly. This is particularly true when we to prove that an object does not obey some property of interest. Indeed, as we've seen from our study of mathematical logic, reasoning about the negation of a property can be subtly tricky!

In these situations, we can employ a different proof technique, proof by contradiction, to show the proposition of interest. Proving a proposition $P$ by contradiction proceeds as follows:

For the sake of contradiction, assume that $\neg P$ , i.e., the negation of the goal proposition, is true.
From this assumption, derive additional facts until we can exhibit a logical contradiction.
If we are able to derive a contradiction, we know that it must be because we assumed $\neg P$ holds. Thus, it must be the case that $\neg P$ does not hold and therefore $P$ holds instead.

Note that in terms of our formal natural deduction rules, this final step invokes the law of the excluded middle:

Definition (Law of the Excluded Middle)

For any proposition $P$ , exactly one of $P$ or $\neg P$ is provable.

We saw this briefly when we reasoned about set inclusion proofs involving the empty set. However, reasoning via contradiction is pervasive throughout mathematics. A classical example of contradiction proof is showing that $2$ is irrational. Recall that the definition of a rational number.

Definition (Rational Number)

A number $n$ is considered rational whenever there exists numbers $a$ and $b$ such that $n = \frac{a}{b}$ .

In other words, a number is rational if it can be expressed as a fraction.

In contrast, an irrational number is precisely a number that is not rational! By "negating" the definition of rational number, we see that we must show that there is no way to decompose the number into a fraction. But that means that we have to show that every possible fractional decomposition does not work, a much harder task than exhibiting a single fractional decomposition!

Instead of this route, we can use a proof by contradiction. We will assume that $2$ is irrational and then follow our nose until we arrive at a contradiction.

Take the time to read and scrutinize this classic proof! It is especially important to understand the details of a proof by contradiction because one misstep or unstated assumption can lead to a contradiction that may not be real.

Proof (Irrationality of square root of two)

Claim: $2$ is irrational.

Proof. Assume for the sake of contradiction that $2$ is rational. By the definition of rational, there exists $a$ and $b$ such that $2 = \frac{a}{b}$ . Furthermore, assume that $\frac{a}{b}$ is simplified, i.e., $a$ and $b$ have no common factors. Now consider the following algebraic manipulation:

$2 = b 2 = (b 2)^{2} = 2 b^{2} = \frac{a}{b} a a^{2} a^{2}$

Observe that $a^{2}$ must be even because it is divisible by 2 (precisely because it is equal to $2 b^{2}$ ). Because the square of an even number is also even, $a$ must be even as well. Therefore, $a = 2 m$ for some integer $m$ . Substituting back for $a$ yields:

$2 b^{2} = 2 b^{2} = b^{2} = (2 m)^{2} 4 m^{2} 2 m^{2}$

Now observe that $b^{2}$ must be even as well because it is divisible by 2 as well and thus $b$ is even. However, we have now established that both $a$ and $b$ are even. This is a contradiction because we assumed they had no factors in common, but, in fact, they do---the common factor is 2.

Thus, our original assumption that $2$ is rational is incorrect; $2$ must be irrational, instead.

Reading Exercises

Check 1: Empty Set Inclusion (‡)

Prove the following set equality using a proof by contradiction:

Claim

For any sets $S$ and $T$ , $S - (T \cup S) = \emptyset$ .

CSC 208: Discrete Structures

Proof by Contradiction

Reading Exercises

Check 1: Empty Set Inclusion (‡)