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