2 is irrational without it. Where would we begin? What would
be our initial assumption? There are no clear answers to these questions.
114
Proof by Contradiction
p
Proof by contradiction gives us a starting point: Assume
2 is rational,
and work from there.
In the above proof we got the contradiction (b is even) ∧ ∼(b is even)
which has the form C∧ ∼ C.
In general, your contradiction need not
necessarily be of this form. Any statement that is clearly false is sufficient.
For example 2 6= 2 would be a fine contradiction, as would be 4 | 2, provided
that you could deduce them.
Here is another ancient example, dating back at least as far as Euclid:
Proposition
There are infinitely many prime numbers.
Proof. For the sake of contradiction, suppose there are only finitely many
prime numbers. Then we can list all the prime numbers as p1, p2, p3, . . . pn,
where p1 = 2, p2 = 3, p3 = 5, p4 = 7 and so on. Thus pn is the nth and largest
prime number. Now consider the number a = (p1 p2 p3 · · · pn) + 1, that is, a is
the product of all prime numbers, plus 1. Now a, like any natural number
greater than 1, has at least one prime divisor, and that means pk | a for at
least one of our n prime numbers pk. Thus there is an integer c for which
a = cpk, which is to say
(p1 p2 p3 ··· pk−1 pk pk+1 ··· pn) + 1 = cpk.
Dividing both sides of this by pk gives us
1
(p1 p2 p3 ··· pk−1 pk+1 ··· pn) +
= c,
pk
so
1 = c−(p1p2p3··· pk
p
−1 pk+1 · · · pn).
k
The expression on the right is an integer, while the expression on the left
is not an integer. This is a contradiction.
■
Proof by contradiction often works well in proving statements of the
form ∀x, P(x).
The reason is that the proof set-up involves assuming
∼ ∀x, P(x), which as we know from Section 2.10 is equivalent to ∃ x,∼ P(x).
This gives us a specific x for which ∼ P(x) is true, and often that is enough
to produce a contradiction. Here is an example:
Proposition
For every real number x ∈ [0, π/2], we have sin x + cos x ≥ 1.
Proof. Suppose for the sake of contradiction that this is not true.
Then there exists an x ∈ [0, π/2] for which sin x + cos x < 1.
Proving Conditional Statements by Contradiction
115
Since x ∈ [0, π/2], neither sin x nor cos x is negative, so 0 ≤ sin x + cos x < 1.
Thus 02 ≤ (sin x + cos x)2 < 12, which gives 02 ≤ sin2 x + 2 sin x cos x + cos2 x < 12.
As sin2 x + cos2 x = 1, this becomes 0 ≤ 1 + 2 sin x cos x < 1, so 1 + 2 sin x cos x < 1.
Subtracting 1 from both sides gives 2 sin x cos x < 0.
But this contradicts the fact that neither sin x nor cos x is negative.
■
6.2 Proving Conditional Statements by Contradiction
Since the previous two chapters dealt exclusively with proving conditional
statements, we now formalize the procedure in which contradiction is used
to prove a conditional statement. Suppose we want to prove a proposition
of the following form.
Proposition
If P, then Q.
Thus we need to prove that P ⇒ Q is a true statement.
Proof by
contradiction begins with the assumption that ∼ (P ⇒ Q) is true, that is,
that P ⇒ Q is false. But we know that P ⇒ Q being false means that it is
possible that P can be true while Q is false. Thus the first step in the
proof is to assume P and ∼ Q. Here is an outline:
Outline for Proving a Conditional
Statement with Contradiction
Proposition
If P, then Q.
Proof. Suppose P and ∼ Q.
...
Therefore C ∧ ∼ C.
■
To illustrate this new technique, we revisit a familiar result: If a2 is
even, then a is even. According to the outline, the first line of the proof
should be “For the sake of contradiction, suppose a2 is even and a is not
even.”
Proposition
Suppose a ∈ Z. If a2 is even, then a is even.
Proof. For the sake of contradiction, suppose a2 is even and a is not even.
Then a2 is even, and a is odd.
Since a is odd, there is an integer c for which a = 2c + 1.
Then a2 = (2c + 1)2 = 4c2 + 4c + 1 = 2(2c2 + 2c) + 1, so a2 is odd.
Thus a2 is even and a2 is not even, a contradiction.
■
116
Proof by Contradiction
Here is another example.
Proposition
If a, b ∈ Z and a ≥ 2, then a - b or a - (b + 1).
Proof. Suppose for the sake of contradiction there exist a, b ∈ Z with a ≥ 2,
and for which it is not true that a - b or a - (b + 1).
By DeMorgan’s law, we have a | b and a | (b + 1).
The definition of divisibility says there are c, d ∈ Z with b = ac and b+1 = ad.
Subtracting one equation from the other gives ad − ac = 1, so a(d − c) = 1.
Since a is positive, d−c is also positive (otherwise a(d−c) would be negative).
Then d − c is a positive integer and a(d − c) = 1, so a = 1/(d − c) < 2.
Thus we have a ≥ 2 and a < 2, a contradiction.
■
6.3 Combining Techniques
Often, especially in more complex proofs, several proof techniques are
combined within a single proof. For example, in proving a conditional
statement P ⇒ Q, we might begin with direct proof and thus assume P to
be true with the aim of ultimately showing Q is true. But the truth of Q
might hinge on the truth of some other statement R which—together with
P—would imply Q. We would then need to prove R, and we would use
whichever proof technique seems most appropriate. This can lead to “proofs
inside of proofs.” Consider the following example. The overall approach is
direct, but inside the direct proof is a separate proof by contradiction.
Proposition
Every non-zero rational number can be expressed as a
product of two irrational numbers.
Proof. This proposition can be reworded as follows: If r is a non-zero
rational number, then r is a product of two irrational numbers. In what
follows, we prove this with direct proof.
Suppose r is a non-zero rational number. Then r = ab for integers a
and b. Also, r can be written as a product of two numbers as follows:
p
r
r = 2 · p .
2
p
p
We know
2 is irrational, so to complete the proof we must show r/ 2 is
also irrational.
p
To show this, assume for the sake of contradiction that r/ 2 is rational.
This means
r
c
p =
2
d
Some Words of Advice
117
for integers c and d, so
p
d
2 = r .
c
But we know r = a/b, which combines with the above equation to give
p
d
a
d
ad
2 = r
=
=
.
c
b c
bc
p
This means
2 is rational, which is a contradiction because we know it is
p
irrational. Therefore r/ 2 is irrational.
p
p
Consequently r =
2 · r/ 2 is a product of two irrational numbers.
■
For another example of a proof-within-a-proof, try Exercise 5 at the
end of this chapter (or see its solution). Exercise 5 asks you to prove that
p3 is irrational. This turns out to be slightly trickier than proving that
p2 is irrational.
6.4 Some Words of Advice
Despite the power of proof by contradiction, it’s best to use it only when the
direct and contrapositive approaches do not seem to work. The reason for
this is that a proof by contradiction can often have hidden in it a simpler
contrapositive proof, and if this is the case it’s better to go with the simpler
approach. Consider the following example.
Proposition
Suppose a ∈ Z. If a2 − 2a + 7 is even, then a is odd.
Proof. To the contrary, suppose a2 − 2a + 7 is even and a is not odd.
That is, suppose a2 − 2a + 7 is even and a is even.
Since a is even, there is an integer c for which a = 2c.
Then a2 − 2a + 7 = (2c)2 − 2(2c) + 7 = 2(2c2 − 2c + 3) + 1, so a2 − 2a + 7 is odd.
Thus a2 − 2a + 7 is both even and odd, a contradiction.
■
Though there is nothing really wrong with this proof, notice that part
of it assumes a is not odd and deduces that a2 − 2a + 7 is not even. That is
the contrapositive approach! Thus it would be more efficient to proceed as
follows, using contrapositive proof.
Proposition
Suppose a ∈ Z. If a2 − 2a + 7 is even, then a is odd.
Proof. (Contrapositive) Suppose a is not odd.
Then a is even, so there is an integer c for which a = 2c.
Then a2 − 2a + 7 = (2c)2 − 2(2c) + 7 = 2(2c2 − 2c + 3) + 1, so a2 − 2a + 7 is odd.
Thus a2 − 2a + 7 is not even.
■
118
Proof by Contradiction
Exercises for Chapter 6
A. Use the method of proof by contradiction to prove the following statements.
(In each case, you should also think about how a direct or contrapositive proof
would work. You will find in most cases that proof by contradiction is easier.)
1. Suppose n ∈ Z. If n is odd, then n2 is odd.
2. Suppose n ∈ Z. If n2 is odd, then n is odd.
p
3.
3
Prove that
2 is irrational.
p
4. Prove that
6 is irrational.
p
5. Prove that
3 is irrational.
6. If a, b ∈ Z, then a2 − 4b − 2 6= 0.
7. If a, b ∈ Z, then a2 − 4b − 3 6= 0.
8. Suppose a, b, c ∈ Z. If a2 + b2 = c2, then a or b is even.
9. Suppose a, b ∈ R. If a is rational and ab is irrational, then b is irrational.
10. There exist no integers a and b for which 21a + 30b = 1.
11. There exist no integers a and b for which 18a + 6b = 1.
12. For every positive x ∈ Q, there is a positive y ∈ Q for which y < x.
13. For every x ∈ [ π/2, π], sin x − cos x ≥ 1.
14. If A and B are sets, then A ∩ (B − A) = ;.
15. If b ∈ Z and b - k for every k ∈ N, then b = 0.
p
16. If a and b are positive real numbers, then a + b ≥ 2 ab.
17. For every n ∈ Z, 4 - (n2 + 2).
18. Suppose a, b ∈ Z. If 4 | (a2 + b2), then a and b are not both odd.
B. Prove the following statements using any method from Chapters 4, 5 or 6.
19. The product of any five consecutive integers is divisible by 120. (For
example, the product of 3,4,5,6 and 7 is 2520, and 2520 = 120 · 21.)
20. We say that a point P = (x, y) in R2 is rational if both x and y are rational.
More precisely, P is rational if P = (x, y) ∈ Q2. An equation F(x, y) = 0 is said
to have a rational point if there exists x0, y0 ∈ Q such that F(x0, y0) = 0. For
example, the curve x2 + y2 − 1 = 0 has rational point (x0, y0) = (1, 0). Show that
the curve x2 + y2 − 3 = 0 has no rational points.
21. Exercise 20 (above) involved showing that there are no rational points on
p
the curve x2 + y2 − 3 = 0. Use this fact to show that
3 is irrational.
22. Explain why x2 + y2 − 3 = 0 not having any rational solutions (Exercise 20)
implies x2 + y2 − 3k = 0 has no rational solutions for k an odd, positive integer.
p
23. Use the above result to prove that
3k is irrational for all odd, positive k.
24. The number log2 3 is irrational.
Part III
More on Proof
CHAPTER
7
Proving Non-Conditional Statements
he last three chapters introduced three major proof techniques: direct,
Tcontrapositive and contradiction. These three techniques are used to
prove statements of the form “If P , then Q .” As we know, most theorems
and propositions have this conditional form, or they can be reworded to
have this form. Thus the three main techniques are quite important. But
some theorems and propositions cannot be put into conditional form. For
example, some theorems have form “ P if and only if Q .” Such theorems
are biconditional statements, not conditional statements. In this chapter
we examine ways to prove them. In addition to learning how to prove
if-and-only-if theorems, we will also look at two other types of theorems.
7.1 If-and-Only-If Proof
Some propositions have the form
P if and only if Q.
We know from Section 2.4 that this statement asserts that both of the
following conditional statements are true:
If P, then Q.
If Q, then P.
So to prove “ P if and only if Q ,” we must prove two conditional statements.
Recall from Section 2.4 that Q ⇒ P is called the converse of P ⇒ Q. Thus
we need to prove both P ⇒ Q and its converse. Since these are both condi-
tional statements we may prove them with either direct, contrapositive or
contradiction proof. Here is an outline:
Outline for If-and-Only-If Proof
Proposition
P if and only if Q.
Proof.
[Prove P ⇒ Q using direct, contrapositive or contradiction proof.]
[Prove Q ⇒ P using direct, contrapositive or contradiction proof.]
122
Proving Non-Conditional Statements
Let’s start with a very simple example. You already know that an
integer n is odd if and only if n2 is odd, but let’s prove it anyway, just
to illustrate the outline. In this example we prove (n is odd)⇒(n2 is odd)
using direct proof and (n2 is odd)⇒(n is odd) using contrapositive proof.
Proposition
The integer n is odd if and only if n2 is odd.
Proof. First we show that n being odd implies that n2 is odd. Suppose n
is odd. Then, by definition of an odd number, n = 2a + 1 for some integer a.
Thus n2 = (2a + 1)2 = 4a2 + 4a + 1 = 2(2a2 + 2a) + 1. This expre
sses n2 as twice
an integer, plus 1, so n2 is odd.
Conversely, we need to prove that n2 being odd implies that n is odd.
We use contrapositive proof. Suppose n is not odd. Then n is even, so
n = 2a for some integer a (by definition of an even number). Thus n2 =
(2a)2 = 2(2a2), so n2 is even because it’s twice an integer. Thus n2 is not
odd. We’ve now proved that if n is not odd, then n2 is not odd, and this is
a contrapositive proof that if n2 is odd then n is odd.
■
In proving “P if and only if Q,” you should begin a new paragraph
when starting the proof of Q ⇒ P. Since this is the converse of P ⇒ Q, it’s
a good idea to begin the paragraph with the word “Conversely” (as we did
above) to remind the reader that you’ve finished the first part of the proof
and are moving on to the second. Likewise, it’s a good idea to remind the
reader of exactly what statement that paragraph is proving.
The next example uses direct proof in both parts of the proof.
Proposition
Suppose a and b are integers. Then a ≡ b (mod 6) if and
only if a ≡ b (mod 2) and a ≡ b (mod 3).
Proof. First we prove that if a ≡ b (mod 6), then a ≡ b (mod 2) and a ≡ b
(mod 3). Suppose a ≡ b (mod 6). This means 6 | (a− b), so there is an integer
n for which
a − b = 6n.
From this we get a − b = 2(3n), which implies 2 | (a − b), so a ≡ b (mod 2). But
we also get a − b = 3(2n), which implies 3 | (a − b), so a ≡ b (mod 3). Therefore
a ≡ b (mod 2) and a ≡ b (mod 3).
Conversely, suppose a ≡ b (mod 2) and a ≡ b (mod 3). Since a ≡ b (mod 2)
we get 2 | (a− b), so there is an integer k for which a− b = 2k. Therefore a− b
is even. Also, from a ≡ b (mod 3) we get 3 | (a − b), so there is an integer `
for which
a − b = 3 `.
Equivalent Statements
123
But since we know a − b is even, it follows that ` must be even also, for
if it were odd then a − b = 3 ` would be odd (because a − b would be the
product of two odd integers). Hence ` = 2m for some integer m. Thus
a − b = 3 ` = 3 · 2m = 6m. This means 6 | (a − b), so a ≡ b (mod 6).
■
Since if-and-only-if proofs simply combine methods with which we are
already familiar, we will not do any further examples in this section.
However, it is of utmost importance that you practice your skill on some
of this chapter’s exercises.
7.2 Equivalent Statements
In other courses you will sometimes encounter a certain kind of theorem
that is neither a conditional nor a biconditional statement. Instead, it
Book of Proof Page 17
