EF Proof by contradiction

Section 6.9 Proof by contradiction

Fact 6.9.1.

For any logically false statement \(e \text{,}\) we have

\begin{equation*} s \lgccond t \; \lgcequiv \; (s \lgcand \lgcnot t) \lgccond e \text{.} \end{equation*}

Proof.

First, \(s\lgccond t \) is false precisely when \(s \) is true and \(t \) is false. On the other hand, \((s \lgcand \lgcnot t) \lgccond e \) is false precisely when \(s \lgcand \lgcnot t \) is true, and \(s \lgcand \lgcnot t \) is true precisely when \(s, \lgcnot t \) are both true; that is, when \(s \) is true and \(t \) is false.

Procedure 6.9.2. Proof by contradiction.

To prove \(P \lgcimplies Q \text{,}\) devise a false statement \(E \) such that \((P \lgcand \lgcnot Q) \lgcimplies E \text{.}\)
To prove \((\forall x)\bbrac{P(x) \lgcimplies Q(x)} \text{,}\) devise a predicate \(E(x) \) such that \((\forall x)\bbrac{\lgcnot E(x)} \) is true (that is, \(E(x) \) is false for all \(x \) in the domain), but \((\forall x)\bigl[\bbrac{P(x) \lgcand \lgcnot Q(x)} \lgcimplies E(x)\bigr] \text{.}\)

Note 6.9.3.

Usually \(E \) is taken to be some variation of \(C \lgcand \lgcnot C \text{,}\) for some statement \(C \text{.}\) (See the Law of Contradiction, recorded as Basic Tautology 4 in Example 1.4.1.)

Worked Example 6.9.4.

Prove that \(\sqrt{2} \) is irrational.

Solution.

We want to prove the quantified conditional with domain the real numbers: for all \(x \text{,}\) if \(x^2 = 2 \) and \(x \gt 0 \) then \(x \) is not rational.

Suppose that \(x \) is a real number such that \(x^2 = 2 \) and \(x \gt 0 \text{.}\) By contradiction, also assume that \(x \) is rational. We want this extra assumption to lead to a false statement. Now, \(x \) rational means \(x = a/b \) for some integers \(a,b \text{.}\) We may assume \(a,b \) are both positive, since \(x \gt 0 \text{.}\) We may also assume \(a,b \) have no common factors (that is, fraction \(a/b \) is in lowest terms). Then,

\begin{align*} x^2 = 2 \amp \; \lgcimplies \; a^2 = 2 b^2, \\ \amp \; \lgcimplies \; a^2 \text{ even}, \\ \amp \; \lgcimplies \; a \text{ even}, \\ \amp \; \lgcimplies \; a = 2m, \text{ some } m, \\ \amp \; \lgcimplies \; 2 b^2 = a^2 = 4m^2, \\ \amp \; \lgcimplies \; b^2 = 2m^2, \\ \amp \; \lgcimplies \; b^2 \text{ even}, \\ \amp \; \lgcimplies \; b \text{ even}. \end{align*}

But if both \(a,b \) are even, then \(a \) and \(b \) are both divisible by \(2 \text{.}\) We have arrived at our contradiction: \(a,b \) have no common factor but \(a,b \) have a common factor of \(2 \text{.}\) That is, we have shown the following.

For all \(x \text{,}\) if \(\bbrac{ (x^2 = 2 \text{ and } x \gt 0) \text{ and } x \text{ not irrational}} \) then (there exist positive integers \(a,b \) such that \(x = a/b \) and \(a,b \) have no common divisor and \(a,b \) have a common divisor).