Loading [MathJax]/jax/element/mml/optable/BasicLatin.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

3.4: Indirect Proofs

( \newcommand{\kernel}{\mathrm{null}\,}\)

 

Instead of proving pq 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 pq, we may prove its contrapositive ¯q¯p. Since it is an implication, we could use a direct proof:

Assume ¯q is true (hence, assume q is false).

Show that ¯p is true (that is, show that p is false).

The proof may proceed as follow:

Prove: pq

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

That is, we will prove ¯q¯p.

Assume q is false, . . .

.

.

.

. . . Therefore p is false.

Thus ¯q¯p.

Therefore, by contraposition, pq.

Lemma 3.4.1

Let n be an integer. Show that if n2 is even, then n is also even.

Proof:

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

Thus if n is odd, then n2 is odd.

Therefore, by contraposition, for all integers n if n2 is even, then n is  even.

Note: Lemma 3.4.1 will be used in the proof that 2 is irrational, later in this section.

Example 3.4.1

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 pq, we proceed as follows:

Suppose pq 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 pq? 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 pq is false. Consequently, pq 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, pq 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 3.4.2

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. This implies that the sum of the interior angles of the triangle PQR exceeds 180, which is impossible. Hence, there is only one perpendicular line from P onto L.

Example 3.4.3

Show that if x2<5, then |x|<5.

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

Solution

Assume x2<5. We want to show that |x|<5. Suppose, on the contrary, we have |x|5.

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

So either x5, or x5

The second case, x5 is the same as x5 (by multiplying both sides by negative 1).

If x5, then x25, by algebra; note: since x is a positive number the inequality sign does not change.

If x5, we again have x25, by algebra; note: since x is a negative number the inequality sign reverses.

In either case, we have both x25 and x2<5 which is a contradiction.

Hence |x|<5.

 if x2<5, then |x|<5.

hands-on exercise 3.4.1

Prove that if x249, then |x|7.

Example 3.4.4

Prove [(pq)p]q is a tautology.

Solution

Suppose [(pq)p]q is false for some statements p and q. Then we find

  • (pq)p is true, and
  • q is false.

For the conjunction (pq)p to be true, we need

  • pq to be true, and
  • p to be true.

Having p true and pq true, we must have q true.  That gives us q is true and q is false, a contradiction! Thus it cannot be that [(pq)p]q is false.  Therefore, [(pq)p]q is always true, hence it is a tautology.

Example 3.4.5

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=mn for some integers m and n, where n0 by definition of rational. Since x is rational, we also have x=pq for some integers p and q, where q0 by defintion of rational. It follows by substitution that mn=x+y=pq+y. Hence by algebra, y=mnpq=mqnpnq, where mqnp and nq are both integers because Z is closed under addition and multiplication. Also nq0 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.

 if x is rational and y is irrational, then x+y is irrational.

hands-on exercise 3.4.2

Prove that x+yx+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 3.4.2

We will use this lemma (along with Lemma 3.4.1) for the proof that 2 is irrational.

Lemma 3.4.2 Given a rational number, x, x can be written as a fraction mn where m,nZn0 and mn is in lowest terms.

Proof:

Given a rational number, x, x can be written as a fraction ab where a,bZ ,b0 by definition of rational number.

If ab is not in lowest terms, then a and b have a common factor.  Divide out that common factor to get an equivalent fraction, cd.

If cd is not in lowest terms, then c and d have a common factor.  Divide out that common factor to get an equivalent fraction, fg.

If fg is not in lowest terms, then f and g have a common factor.  Divide out that common factor to get an equivalent fraction, jk.

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=mn and mn is in lowest terms.
a rational number can be written as a fraction in lowest terms.

 

 

The 2 is irrational.

Prove that 2 is irrational.

Proof:

Suppose, on the contrary, 2 is rational. Then we can write 2=mn for some positive integers m and n such that m and n do not share any common divisor except 1 (hence mn is in lowest terms) by Lemma 3.4.2. Squaring both sides and cross-multiplying yields 2n2=m2. Since Z are closed under multiplication,  n2 is an integer and thus m2 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 2n2=m2=(2s)2=4s2. Hence, n2=2s2.  Since Z are closed under multiplication,  s2 is an integer and thus n2 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 2 to be rational.

Therefore, 2 must be irrational.

hands-on exercise 3.4.3

Prove that 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 3.4.6

Show that x2+4x+6=0 has no real solution. In symbols, show that xR,(x2+4x+6=0).

Solution

Consider the following proof by contradiction:

Suppose there exists a real number x such that x2+4x+6=0.
Using calculus, it can be shown that the function f(x)=x2+4x+6
has an absolute minimum at x=2. **Need to show those calculus steps.**

Thus, f(x)f(2)=2 for
any x. This contradicts the assumption that there exists an x
such that x2+4x+6=0. Thus, x2+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 x2+4x+62 for all x. This already shows that x2+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.)


This page titled 3.4: Indirect Proofs is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?