Skip to main content
$$\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}}$$

# 3.4: Indirect Proofs

$$\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}}$$

Instead of proving $$p \Rightarrow q$$ directly, it is sometimes easier to prove it indirectly. There are two kinds of indirect proofs: proof by contrapositive, and proof by contradiction.

## Proof by Contrapositive

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:

Prove: $$p \Rightarrow q$$

Proof: We will prove the contrapositive of the stated result.

That is, we will prove $$\overline{q} \Rightarrow \overline{p}$$.

Assume $$q$$ is false, . . .

.

.

.

. . . Therefore $$p$$ is false.

Thus $$\overline{q} \Rightarrow \overline{p}$$.

Therefore, by contraposition, $$p \Rightarrow q.$$

Lemma $$\PageIndex{1}$$

Let $$n$$ be an integer. Show that if $$n^2$$ is even, then $$n$$ is also even.

Proof:

Proof by contrapositive: We want to prove that if $$n$$ is odd, then $$n^2$$ is odd. Let $$n$$ be an odd integer, then $$n=2t+1$$ for some integer $$t$$ by definition of odd. By algebra $n^2 = 4t^2+4t+1 = 2(2t^2+2t)+1.$ Since $$\mathbb{Z}$$ is closed under addition & multiplication, $$2t^2+2t$$ is an integer.  Hence $$n^2$$ is odd by definition of odd.

Thus if $$n$$ is odd, then $$n^2$$ is odd.

Therefore, by contraposition, for all integers $$n$$ if $$n^2$$ is even, then $$n$$ is  even.

Note: Lemma $$\PageIndex{1}$$ will be used in the proof that $$\sqrt{2}$$ is irrational, later in this section.

Example $$\PageIndex{1}\label{eg:indirectpf-01}$$

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.

## Proof by Contradiction

Another indirect proof is 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 not.  That is, suppose $$p$$ is true and $$q$$ is false. Then

. . .

.

.

a contradiction!!

Thus our assumption that $$p$$ is true and $$q$$ is false cannot be true.

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 not.  That is, suppose $$r$$ is false. Then . . .

.

.

a contradiction!!

Thus our assumption that $$r$$ is false cannot be true.

Therefore, $$r$$ must be true.

Example $$\PageIndex{2}\label{eg:indirectpf-02}$$

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{3}\label{eg:indirectpf-03}$$

Show that if $$x^2<5$$, then $$|x|<\sqrt{5}$$.

note: if no set of numbers is specified, the default is the set of real numbers.

Solution

Assume $$x^2<5$$. We want to show that $$|x|<\sqrt{5}$$. Suppose, on the contrary, we have $$|x|\geq\sqrt{5}$$.

By definition, $$|x|=x$$  or  $$|x|=-x$$.

So either $$x\geq\sqrt{5}$$, or $$-x\geq\sqrt{5}$$.

The second case, $$-x\geq\sqrt{5}$$ is the same as $$x\leq-\sqrt{5}$$ (by multiplying both sides by negative 1).

If $$x\geq\sqrt{5}$$, then $$x^2\geq5$$, by algebra; note: since x is a positive number the inequality sign does not change.

If $$x\leq-\sqrt{5}$$, we again have $$x^2\geq5$$, by algebra; note: since x is a negative number the inequality sign reverses.

In either case, we have both $$x^2\geq5$$ and $$x^2<5$$ which is a contradiction.

Hence $$|x|<\sqrt{5}$$.

$$\therefore$$ if $$x^2<5$$, then $$|x|<\sqrt{5}$$.

hands-on exercise $$\PageIndex{1}\label{he:indirectpf-01}$$

Prove that if $$x^2\geq49$$, then $$|x|\geq7$$.

Example $$\PageIndex{4}\label{eg:indirectpf-04}$$

Prove $[(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 $$p\Rightarrow q$$ true, we must have $$q$$ true.  That gives us $$q$$ is true and $$q$$ is false, a contradiction! Thus it cannot be that $$[(p\Rightarrow q) \wedge p] \Rightarrow q$$ is false.  Therefore, $$[(p\Rightarrow q) \wedge p] \Rightarrow q$$ is always true, hence it is a tautology.

Example $$\PageIndex{5}\label{eg:indirectpf-05}$$

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$$ by definition of rational. Since $$x$$ is rational, we also have $x = \frac{p}{q}$ for some integers $$p$$ and $$q$$, where $$q\neq0$$ by defintion of rational. It follows by substitution that $\frac{m}{n} = x+y = \frac{p}{q} + y.$ Hence by algebra, $y = \frac{m}{n}-\frac{p}{q} = \frac{mq-np}{nq},$ where $$mq-np$$ and $$nq$$ are both integers because $$\mathbb{Z}$$ is closed under addition and multiplication. Also $$nq\neq0$$ by the Zero Product Property. This makes $$y$$ rational by definition of rational.  Now we have  $$y$$ is rational and $$y$$ is irrational (by assumption). This is a contradiction! Thus, $$x+y$$ cannot be rational, it must be irrational.

$$\therefore$$ if $$x$$ is rational and $$y$$ is irrational, then $$x+y$$ is irrational.

hands-on exercise $$\PageIndex{2}\label{he:indirectpf-02}$$

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.

Lemma $$\PageIndex{2}$$

We will use this lemma (along with Lemma 3.4.1) for the proof that $$\sqrt{2}$$ is irrational.

Lemma 3.4.2 Given a rational number, x, x can be written as a fraction $$\frac{m}{n}$$ where $$m,n \in \mathbb {Z}$$ , $$n \neq 0$$ and $$\frac{m}{n}$$ is in lowest terms.

Proof:

Given a rational number, x, x can be written as a fraction $$\frac{a}{b}$$ where $$a,b \in \mathbb {Z}$$ ,$$b \neq 0$$ by definition of rational number.

If $$\frac{a}{b}$$ is not in lowest terms, then $$a$$ and $$b$$ have a common factor.  Divide out that common factor to get an equivalent fraction, $$\frac{c}{d}.$$

If $$\frac{c}{d}$$ is not in lowest terms, then $$c$$ and $$d$$ have a common factor.  Divide out that common factor to get an equivalent fraction, $$\frac{f}{g}.$$

If $$\frac{f}{g}$$ is not in lowest terms, then $$f$$ and $$g$$ have a common factor.  Divide out that common factor to get an equivalent fraction, $$\frac{j}{k}.$$

Continue this process until the numerator and denominator do not have any common factors.  Rename the numerator as $$m$$ and the denominator as $$n.$$

Now $$x=\frac{m}{n}$$ and $$\frac{m}{n}$$ is in lowest terms.
$$\therefore$$ a rational number can be written as a fraction in lowest terms.

## The $$\sqrt{2}$$ is irrational.

Prove that $$\sqrt{2}$$ is irrational.

Proof:

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 lowest terms) by Lemma 3.4.2. Squaring both sides and cross-multiplying yields $2n^2 = m^2.$ Since $$\mathbb{Z}$$ are closed under multiplication,  $$n^2$$ is an integer and thus $$m^2$$ is even by the definition of even. Consequently, by Lemma 3.4.1, $$m$$ is also even. Then we can write $$m=2s$$ for some integer $$s$$ by the definition of even. By substitution and algebra, the equation above becomes $2n^2 = m^2 = (2s)^2 = 4s^2.$ Hence, $n^2 = 2s^2.$  Since $$\mathbb{Z}$$ are closed under multiplication,  $$s^2$$ is an integer and thus $$n^2$$ is even by the definition of even. Consequently, by Lemma 3.4.1, $$n$$ is also even. Even numbers are divisible by 2, by the definition of divides. We have shown that both $$m$$ and $$n$$ are divisible by 2. This contradicts the assumption that $$m$$ and $$n$$ do not share any common divisor. Thus is is not possible for $$\sqrt{2}$$ to be rational.

Therefore, $$\sqrt{2}$$ must be irrational.

hands-on exercise $$\PageIndex{3}\label{he:indirectpf-03}$$

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{6}\label{eg:indirectpf-6}$$

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$$. **Need to show those calculus steps.**

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 see $$f'(x)=2x+4$$.  Setting $$f'(x)=0$$ we get $$x=-2$$. Since $$f"(x)=2$$, thus $$f"(-2)=2$$,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?

## Proving a Biconditional Statement

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{7}\label{eg:indirectpf-7}$$

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$$ by definition of odd. Then by algebra  $n^2 = (2t+1)^2 = 4t^2+4t+1 = 2(2t^2+2t)+1,$ where $$2t^2+2t$$ is an integer since $$\mathbb{Z}$$ is closed under addition and multiplication. Thus, $$n^2$$ is odd. So, if $$n$$ is odd, then $$n^2$$ is odd.  By contraposition, if $$n^2$$ is even, then $$n$$ is even.

($$\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$$ by definition of even. Then $n^2 = (2t)^2 = 4t^2 = 2\cdot 2t^2,$ where $$2t^2$$ is an integer since $$\mathbb{Z}$$ is closed under multiplication. Hence, $$n^2$$ is even. if $$n$$ is even, then $$n^2$$ is even.

$$\therefore \, n^2$$ is even if and only if $$n$$ is even.

hands-on exercise $$\PageIndex{4}\label{he:indirectpf-04}$$

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 direct proof. If so, the direct proof is the more direct way to write the proof.

## Exercises

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) A proof by contrapositive (this one is done - see proof of Lemma 3.4.1)

(b) A proof by contradiction.

Remark

The two proofs are very similar, but the wording is slightly different, so be sure you present your proof clearly.

exercise $$\PageIndex{2}\label{ex:indirectpf-02}$$

Let $$n$$ be an integer. Prove that if $$n^2$$ is a multiple of 3, then $$n$$ must also be a multiple of 3. Use

(a) A proof by contrapositive.

(b) 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. Prove 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. Prove 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. Prove 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$$. Prove 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.

(See example 3.4.4.)

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.

(See example 3.4.4.)

• Was this article helpful?