6.9: Proof by Contradiction

Last updated
Save as PDF

Page ID: 88415

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Fact \(\PageIndex{1}\)

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

\begin{equation*} s \rightarrow t \; \Leftrightarrow \; (s \land \neg t) \rightarrow e \text{.} \end{equation*}

Proof: First, \(s\rightarrow t\) is false precisely when \(s\) is true and \(t\) is false. On the other hand, \((s \land \neg t) \rightarrow e\) is false precisely when \(s \land \neg t\) is true, and \(s \land \neg t\) is true precisely when \(s, \neg t\) are both true, i.e. when \(s\) is true and \(t\) is false.

Procedure \(\PageIndex{1}\): Proof by contradiction

To prove \(P \Rightarrow Q\text{,}\) devise a false statement \(E\) such that \((P \land \neg Q) \Rightarrow E\text{.}\)
To prove \((\forall x)(P(x) \Rightarrow Q(x))\text{,}\) devise a predicate \(E(x)\) such that \((\forall x)(\neg E(x))\) is true (i.e. \(E(x)\) is false for all \(x\) in the domain), but \((\forall x)\bigl[(P(x) \land \neg Q(x)) \Rightarrow E(x)\bigr]\text{.}\)

Note \(\PageIndex{1}\)

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

Example \(\PageIndex{1}\)

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 & \; \Rightarrow \; a^2 = 2 b^2, \\ & \; \Rightarrow \; a^2 \text{ even}, \\ & \; \Rightarrow \; a \text{ even}, \\ & \; \Rightarrow \; a = 2m, \text{ some } m, \\ & \; \Rightarrow \; 2 b^2 = a^2 = 4m^2, \\ & \; \Rightarrow \; b^2 = 2m^2, \\ & \; \Rightarrow \; b^2 \text{ even}, \\ & \; \Rightarrow \; 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 \(( (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 \(\PageIndex{1}\)

Attempt Exercises 6.12.11–6.12.13.