3.3: Indirect Proofs
- Page ID
- 8395
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Instead of proving \(p \Rightarrow q\) directly, it is sometimes easier to prove it indirectly. There are two kinds of indirect proofs: the proof by contrapositive, and the proof by contradiction.
The proof by contrapositive is based on the fact that an implication is equivalent to its contrapositive. Therefore, instead of proving \(p \Rightarrow q\), we may prove its contrapositive \(\overline{q} \Rightarrow \overline{p}\). Since it is an implication, we could use a direct proof:
Assume \(\overline{q}\) is true (hence, assume \(q\) is false).
Show that \(\overline{p}\) is true (that is, show that \(p\) is false).
The proof may proceed as follow:
Proof: We want to prove the contrapositive of the stated result.
Assume \(q\) is false, . . .
.
.
.
. . . Therefore \(p\) is false.
Example \(\PageIndex{1}\label{eg:indirectpf-01}\)
Let \(n\) be an integer. Show that if \(n^2\) is even, then \(n\) is also even.
- Solution
-
Proof by contrapositive: We want to prove that if \(n\) is odd, then \(n^2\) is odd. If \(n\) is odd, then \(n=2t+1\) for some integer \(t\). Hence, \[n^2 = 4t^2+4t+1 = 2(2t^2+2t)+1\] is odd. This completes the proof.
Example \(\PageIndex{2}\label{eg:indirectpf-02}\)
Show that if \(n\) is a positive integer such that the sum of its positive divisors is \(n+1\), then \(n\) is prime.
- Solution
-
We shall prove the contrapositive of the given statement. We want to prove that if \(n\) is composite, then the sum of its positive divisors is not \(n+1\). Let \(n\) be a composite number. Then its divisors include 1, \(n\), and at least one other positive divisor \(x\) different from 1 and \(n\). So the sum of its positive divisors is at least \(1+n+x\). Since \(x\) is positive, we gather that \[1+n+x > 1+n.\] We deduce that the sum of the divisors cannot be \(n+1\). Therefore, if the sum of the divisors of \(n\) is precisely \(n+1\), then \(n\) must be prime.
Example \(\PageIndex{3}\label{eg:indirectpf-03}\)
Let \(x\) be a real number. Prove that if \(x^3-7x^2+x-7=0\), then \(x=7\).
- Solution
-
Assume \(x\neq7\), then \[x^3-7x^2+x-7 = x^2(x-7)+(x-7) = (x^2+1) (x-7) \neq 0.\] Thus, if \(x^3-7x^2+x-7=0\), then \(x=7\).
hands-on exercise \(\PageIndex{1}\label{he:indirectpf-01}\)
Let \(x\) be a real number. Prove that if \((2x^2+3)(x+5)(x-7)=0\), then either \(x=-5\), or \(x=7\).
hands-on exercise \(\PageIndex{2}\label{he:indirectpf-02}\)
Let \(x\) and \(y\) be two real numbers. Prove that if \(x\neq0\) and \(y\neq0\), then \(xy\neq0\).
Another indirect proof is the proof by contradiction. To prove that \(p \Rightarrow q\), we proceed as follows:
Suppose \(p\Rightarrow q\) is false; that is, assume that \(p\) is true and \(q\) is false.
Argue until we obtain a contradiction, which could be any result that we know is false.
How does this prove that \(p\Rightarrow q\)? Assuming that the logic used in every step in the argument is correct, yet we still end up with a contradiction, then the only possible flaw must come from the supposition that \(p\Rightarrow q\) is false. Consequently, \(p\Rightarrow q\) must be true.
This is what a typical proof by contradiction may look like:
Proof: Suppose \( p \Rightarrow q\) is false. Then \(p\) is true and \(q\) is false. Then
. . .
.
.
.
. . . which is a contradiction. Therefore, \( p \Rightarrow q\) must be true.
There is a more general form for proving a statement \(r\), which needs not be an implication. To prove the proposition \(r\) by contradiction, we follow these steps:
Suppose \(r\) is false.
Argue until we obtain a contradiction.
Proof: Suppose \(r\) is false. Then . . .
.
.
.
. . . which is a contradiction. Therefore, \(r\) must be true.
Example \(\PageIndex{4}\label{eg:indirectpf-04}\)
Show that if \(x^3-7x^2+x-7=0\), then \(x=7\).
- Solution
-
Assume \(x^3-7x^2+x-7=0\), we want to show that \(x=7\). Suppose \(x\neq7\), then \(x-7\neq0\), and \[0 = x^3-7x^2+x-7 = x^2(x-7)+(x-7) = (x^2+1)(x-7)\] would have implied that \(x^2+1=0\), which is impossible. Therefore, we must have \(x=7\).
Example \(\PageIndex{5}\label{eg:indirectpf-05}\)
Show that if \(P\) is a point not on a line \(L\), then there exists exactly one perpendicular line from \(P\) onto \(L\).
- Solution
-
Suppose we can find more than one perpendicular line from \(P\) onto \(L\). Pick any two of them, and denote their intersections with \(L\) as \(Q\) and \(R\). Then we have a triangle \(PQR\), where the angles \(PQR\) and \(PRQ\) are both \(90^\circ\). This implies that the sum of the interior angles of the triangle \(PQR\) exceeds \(180^\circ\), which is impossible. Hence, there is only one perpendicular line from \(P\) onto \(L\).
Example \(\PageIndex{6}\label{eg:indirectpf-06}\)
Show that if \(x^2<5\), then \(|x|<\sqrt{5}\).
- Solution
-
Assume \(x^2<5\), we want to show that \(|x|<\sqrt{5}\). Suppose, on the contrary, we have \(|x|\geq\sqrt{5}\). Then either \(x\geq\sqrt{5}\), or \(x\leq-\sqrt{5}\). If \(x\geq\sqrt{5}\), then \(x^2\geq5\). If \(x\leq-\sqrt{5}\), we again have \(x^2\geq5\). In either case, we have a contradiction. Hence \(|x|<\sqrt{5}\).
hands-on exercise \(\PageIndex{3}\label{he:indirectpf-03}\)
Prove that if \(x^2\geq49\), then \(|x|\geq7\).
Example \(\PageIndex{7}\label{eg:indirectpf-07}\)
Prove that the logical formula \[[(p\Rightarrow q) \wedge p] \Rightarrow q\] is a tautology.
- Solution
-
Suppose \([(p\Rightarrow q) \wedge p] \Rightarrow q\) is false for some statements \(p\) and \(q\). Then we find
- \((p\Rightarrow q) \wedge p\) is true, and
- \(q\) is false.
For the conjunction \((p\Rightarrow q) \wedge p\) to be true, we need
- \(p\Rightarrow q\) to be true, and
- \(p\) to be true.
Having \(p\) true and \(q\) false would make \(p\Rightarrow q\) false. This directly contradicts what we have found. Therefore, the logical formula \([(p\Rightarrow q) \wedge p] \Rightarrow q\) is always true, hence it is a tautology.
Example \(\PageIndex{8}\label{eg:indirectpf-08}\)
Prove, by contradiction, that if \(x\) is rational and \(y\) is irrational, then \(x+y\) is irrational.
- Solution
-
Let \(x\) be a rational number and \(y\) an irrational number. We want to show that \(x+y\) is irrational. Suppose, on the contrary, that \(x+y\) is rational. Then \[x+y = \frac{m}{n}\] for some integers \(m\) and \(n\), where \(n\neq0\). Since \(x\) is rational, we also have \[x = \frac{p}{q}\] for some integers \(p\) and \(q\), where \(q\neq0\). It follows that \[\frac{m}{n} = x+y = \frac{p}{q} + y.\] Hence, \[y = \frac{m}{n}-\frac{p}{q} = \frac{mq-np}{nq},\] where \(mq-np\) and \(nq\) are both integers, with \(nq\neq0\). This makes \(y\) rational, which contradicts the assumption that \(y\) is irrational. Thus, \(x+y\) cannot be rational, it must be irrational.
hands-on exercise \(\PageIndex{4}\label{he:indirectpf-04}\)
Prove that \[\sqrt{x+y} \neq \sqrt{x}+\sqrt{y}\] for any positive real numbers \(x\) and \(y\).
- Hint
-
The words “for any” suggest this is a universal quantification. Be sure you negate the problem statement properly.
Example \(\PageIndex{9}\label{eg:indirectpf-09}\)
Prove that \(\sqrt{2}\) is irrational.
- Solution
-
Suppose, on the contrary, \(\sqrt{2}\) is rational. Then we can write \[\sqrt{2} = \frac{m}{n}\] for some positive integers \(m\) and \(n\) such that \(m\) and \(n\) do not share any common divisor except 1 (hence \(\frac{m}{n}\) is in its simplest term). Squaring both sides and cross-multiplying yields \[2n^2 = m^2.\] Thus, 2 divides \(m^2\). Consequently, 2 must also divide \(m\). Then we can write \(m=2s\) for some integer \(s\). The equation above becomes \[2n^2 = m^2 = (2s)^2 = 4s^2.\] Hence, \[n^2 = 2s^2,\] which implies that 2 divides \(n^2\); thus, 2 also divides \(n\). We have proved that both \(m\) and \(n\) are divisible by 2. This contradicts the assumption that \(m\) and \(n\) do not share any common divisor. Therefore, \(\sqrt{2}\) must be irrational.
hands-on exercise \(\PageIndex{5}\label{he:indirectpf-06}\)
Prove that \(\sqrt{3}\) is irrational.
Very often, a proof by contradiction can be rephrased into a proof by contrapositive or even a direct proof, both of which are easier to follow. If this is the case, rewrite the proof.
Example \(\PageIndex{10}\label{eg:indirectpf-10}\)
Show that \(x^2+4x+6=0\) has no real solution. In symbols, show that \(\nexists x\in\mathbb{R},(x^2+4x+6=0)\).
- Solution
-
Consider the following proof by contradiction:
Suppose there exists a real number \(x\) such that \(x^2+4x+6=0\).
Using calculus, it can be shown that the function $f(x)=x^2+4x+6$
has an absolute minimum at \(x=-2\). Thus, \(f(x) \geq f(-2) = 2\) for
any \(x\). This contradicts the assumption that there exists an \(x\)
such that \(x^2+4x+6=0\). Thus, \(x^2+4x+6=0\) has no real solution.A close inspection reveals that we do not really need a proof by contradiction. The crux of the proof is the fact that \(x^2+4x+6 \geq 2\) for all \(x\). This already shows that \(x^2+4x+6\) could never be zero. It is easier to use a direct proof, as follows.
Using calculus, we find that the function \(f(x)=x^2+4x+6\) has an
absolute minimum at \(x=-2\). Therefore, for any \(x\), we always have
\(f(x) \geq f(-2) = 2\). Hence, there does not exist any \(x\) such that
\(x^2+4x+6=0\).Do you agree that the second proof (the direct proof) is more elegant?
Recall that a biconditional statement \(p\Leftrightarrow q\) consists of two implications \(p\Rightarrow q\) and \(q\Rightarrow p\). Hence, to prove \(p\Leftrightarrow q\), we need to establish these two “directions” separately.
Example \(\PageIndex{11}\label{eg:indirectpf-11}\)
Let \(n\) be an integer. Prove that \(n^2\) is even if and only if \(n\) is even.
- Solution
-
(\(\Rightarrow\)) We first prove that if \(n^2\) is even, then \(n\) must be even. We shall prove its contrapositive: if \(n\) is odd, then \(n^2\) is odd. If \(n\) is odd, then we can write \(n=2t+1\) for some integer \(t\). Then \[n^2 = (2t+1) = 4t^2+4t+1 = 2(2t^2+2t)+1,\] where \(2t^2+2t\) is an integer. Thus, \(n^2\) is odd.
(\(\Leftarrow\)) Next, we prove that if \(n\) is even, then \(n^2\) is even. If \(n\) is even, we can write \(n=2t\) for some integer \(t\). Then \[n^2 = (2t)^2 = 4t^2 = 2\cdot 2t^2,\] where \(2t^2\) is an integer. Hence, \(n^2\) is even, which completes the proof.
hands-on exercise \(\PageIndex{6}\label{he:indirectpf-07}\)
Let \(n\) be an integer. Prove that \(n\) is odd if and only if \(n^2\) is odd.
Summary and Review
- We can use indirect proofs to prove an implication.
- There are two kinds of indirect proofs: proof by contrapositive and proof by contradiction.
- In a proof by contrapositive, we actually use a direct proof to prove the contrapositive of the original implication.
- In a proof by contradiction, we start with the supposition that the implication is false, and use this assumption to derive a contradiction. This would prove that the implication must be true.
- A proof by contradiction can also be used to prove a statement that is not of the form of an implication. We start with the supposition that the statement is false, and use this assumption to derive a contradiction. This would prove that the statement must be true.
- Sometimes a proof by contradiction can be rewritten as a proof by contrapositive or even a direct proof. If this is true, rewrite the proof.
exercise \(\PageIndex{1}\label{ex:indirectpf-01}\)
Let \(n\) be an integer. Prove that if \(n^2\) is even, then \(n\) must be even. Use
- A proof by contrapositive.
- A proof by contradiction.
- Remark
-
The two proofs are very similar, but the wording is slightly different, so be sure you present your proofs clearly.
exercise \(\PageIndex{2}\label{ex:indirectpf-02}\)
Let \(n\) be an integer. Show that if \(n^2\) is a multiple of 3, then \(n\) must also be a multiple of 3. Use
- A proof by contrapositive.
- A proof by contradiction.
exercise \(\PageIndex{3}\label{ex:indirectpf-03}\)
Let \(n\) be an integer. Prove that if \(n\) is even, then \(n^2=4s\) for some integer \(s\).
exercise \(\PageIndex{4}\label{ex:indirectpf-04}\)
Let \(m\) and \(n\) be integers. Show that \(mn=1\) implies that \(m=1\) or \(m=-1\).
exercise \(\PageIndex{5}\label{ex:indirectpf-05}\)
Let \(x\) be a real number. Prove by contrapositive: if \(x\) is irrational, then \(\sqrt{x}\) is irrational. Apply this result to show that \(\sqrt[4]{2}\) is irrational, using the assumption that \(\sqrt{2}\) is irrational.
exercise \(\PageIndex{6}\label{ex:indirectpf-06}\)
Let \(x\) and \(y\) be real numbers such that \(x\neq0\). Prove that if \(x\) is rational, and \(y\) is irrational, then \(xy\) is irrational.
exercise \(\PageIndex{7}\label{ex:indirectpf-07}\)
Prove that \(\sqrt{5}\) is irrational.
exercise \(\PageIndex{8}\label{ex:indirectpf-08}\)
Prove that \(\sqrt[3]{2}\) is irrational.
exercise \(\PageIndex{9}\label{ex:indirectpf-09}\)
Let \(a\) and \(b\) be real numbers. Show that if \(a\neq b\), then \(a^2+b^2 \neq 2ab\).
exercise \(\PageIndex{10}\label{ex:indirectpf-10}\)
Use contradiction to prove that, for all integers \(k\geq1\), \[2\sqrt{k+1} + \frac{1}{\sqrt{k+1}} \geq 2\sqrt{k+2}.\]
exercise \(\PageIndex{11}\label{ex:indirectpf-11}\)
Let \(m\) and \(n\) be integers. Show that \(mn\) is even if and only if \(m\) is even or \(n\) is even.
exercise \(\PageIndex{12}\label{ex:indirectpf-12}\)
Let \(x\) and \(y\) be real numbers. Show that \(x^2+y^2=0\) if and only if \(x=0\) and \(y=0\).
exercise \(\PageIndex{13}\label{ex:indirectpf-13}\)
Prove that, if \(x\) is a real number such that \(0<x<1\), then \(x(1-x)\leq\frac{1}{4}\).
exercise \(\PageIndex{14}\label{ex:indirectpf-14}\)
Let \(m\) and \(n\) be positive integers such that 3 divides \(mn\). Show that 3 divides \(m\), or 3 divides \(n\).
exercise \(\PageIndex{15}\label{ex:indirectpf-15}\)
Prove that the logical formula \[(p\Rightarrow q) \vee (p\Rightarrow \overline{q})\] is a tautology.
exercise \(\PageIndex{16}\label{ex:indirectpf-16}\)
Prove that the logical formula \[[(p\Rightarrow q) \wedge (p\Rightarrow \overline{q})] \Rightarrow \overline{p}\] is a tautology.