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*}

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, i.e. 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 (i.e. \(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 (i.e. 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).

Checkpoint 6.9.5.

Attempt Exercises 6.12.11–6.12.13.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: