3.4: Indirect Proofs

 

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