$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.3: Indirect Proofs

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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.
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.

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{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{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.