Book of Proof
Page 16
■
Contrapositive proof seems to be the best approach in the next example,
since it will eliminate the symbols - and 6≡.
Mathematical Writing
107
Proposition
Suppose a, b ∈ Z and n ∈ N. If 12a 6≡ 12b (mod n), then n - 12.
Proof. (Contrapositive) Suppose n | 12, so there is an integer c for which
12 = nc. Now reason as follows.
12
= nc
12(a − b) = nc(a − b)
12a − 12b = n(ca − cb)
Since ca − cb ∈ Z, the equation 12a − 12b = n(ca − cb) implies n | (12a − 12b).
This in turn means 12a ≡ 12b (mod n).
■
5.3 Mathematical Writing
Now that we have begun writing proofs, it is a good time to contemplate the
craft of writing. Unlike logic and mathematics, where there is a clear-cut
distinction between what is right or wrong, the difference between good
and bad writing is sometimes a matter of opinion. But there are some
standard guidelines that will make your writing clearer. Some of these
are listed below.
1. Begin each sentence with a word, not a mathematical symbol.
The reason is that sentences begin with capital letters, but mathematical
symbols are case sensitive. Because x and X can have entirely different
meanings, putting such symbols at the beginning of a sentence can lead
to ambiguity. Here are some examples of bad usage (marked with ×)
and good usage (marked with X).
A is a subset of B.
×
The set A is a subset of B.
X
x is an integer, so 2x + 5 is an integer.
×
Because x is an integer, 2x + 5 is an integer.
X
x2 − x + 2 = 0 has two solutions.
×
X 2 − x + 2 = 0 has two solutions.
× (and silly too)
The equation x2 − x + 2 = 0 has two solutions.
X
2. End each sentence with a period, even when the sentence ends
with a mathematical symbol or expression.
∞ 1
1
X
Y
Euler proved that
=
×
ks
k=1
p∈P 1 − 1
ps
∞ 1
1
X
Y
Euler proved that
=
.
X
ks
k=1
p∈P 1 − 1
ps
108
Contrapositive Proof
Mathematical statements (equations, etc.) are like English phrases that
happen to contain special symbols, so use normal punctuation.
3. Separate mathematical symbols and expressions with words.
Not doing this can cause confusion by making distinct expressions
appear to merge into one. Compare the clarity of the following examples.
Because x2 − 1 = 0, x = 1 or x = −1.
×
Because x2 − 1 = 0, it follows that x = 1 or x = −1.
X
Unlike A ∪ B, A ∩ B equals ;.
×
Unlike A ∪ B, the set A ∩ B equals ;.
X
4. Avoid misuse of symbols. Symbols such as =, ≤, ⊆, ∈, etc., are not
words. While it is appropriate to use them in mathematical expressions,
they are out of place in other contexts.
Since the two sets are =, one is a subset of the other.
×
Since the two sets are equal, one is a subset of the other.
X
The empty set is a ⊆ of every set.
×
The empty set is a subset of every set.
X
Since a is odd and x odd ⇒ x2 odd, a2 is odd.
×
Since a is odd and any odd number squared is odd, then a2 is odd.X
5. Avoid using unnecessary symbols. Mathematics is confusing enough
without them. Don’t muddy the water even more.
No set X has negative cardinality.
×
No set has negative cardinality.
X
6. Use the first person plural. In mathematical writing, it is common
to use the words “we” and “us” rather than “I,” “you” or “me.” It is as if
the reader and writer are having a conversation, with the writer guiding
the reader through the details of the proof.
7. Use the active voice. This is just a suggestion, but the active voice
makes your writing more lively.
The value x = 3 is obtained through the division of both sides by 5.×
Dividing both sides by 5, we get the value x = 3.
X
8. Explain each new symbol. In writing a proof, you must explain the
meaning of every new symbol you introduce. Failure to do this can lead
to ambiguity, misunderstanding and mistakes. For example, consider
the following two possibilities for a sentence in a proof, where a and b
have been introduced on a previous line.
Mathematical Writing
109
Since a | b, it follows that b = ac.
×
Since a | b, it follows that b = ac for some integer c.
X
If you use the first form, then a reader who has been carefully following
your proof may momentarily scan backwards looking for where the c
entered into the picture, not realizing at first that it came from the
definition of divides.
9. Watch out for “it.” The pronoun “it” can cause confusion when it is
unclear what it refers to. If there is any possibility of confusion, you
should avoid the word “it.” Here is an example:
Since X ⊆ Y , and 0 < |X |, we see that it is not empty.
×
Is “it” X or Y ? Either one would make sense, but which do we mean?
Since X ⊆ Y , and 0 < |X |, we see that Y is not empty.
X
10. Since, because, as, for, so. In proofs, it is common to use these
words as conjunctions joining two statements, and meaning that one
statement is true and as a consequence the other true. The following
statements all mean that P is true (or assumed to be true) and as a
consequence Q is true also.
Q since P
Q because P
Q, as P
Q, for P
P, so Q
Since P, Q
Because P, Q
as P, Q
Notice that the meaning of these constructions is different from that of
“If P , then Q ,” for they are asserting not only that P implies Q, but also
that P is true. Exercise care in using them. It must be the case that P
and Q are both statements and that Q really does follow from P.
x ∈ N, so Z
×
x ∈ N, so x ∈ Z
X
11. Thus, hence, therefore consequently. These adverbs precede a
statement that follows logically from previous sentences or clauses. Be
sure that a statement follows them.
Therefore 2k + 1.
×
Therefore a = 2k + 1.
X
12. Clarity is the gold standard of mathematical writing. If you
believe breaking a rule makes your writing clearer, then break the rule.
Your mathematical writing will evolve with practice useage. One of the
best ways to develop a
good mathematical writing style is to read other
people’s proofs. Adopt what works and avoid what doesn’t.
110
Contrapositive Proof
Exercises for Chapter 5
A. Use the method of contrapositive proof to prove the following statements. (In
each case you should also think about how a direct proof would work. You will
find in most cases that contrapositive is easier.)
1. Suppose n ∈ Z. If n2 is even, then n is even.
2. Suppose n ∈ Z. If n2 is odd, then n is odd.
3. Suppose a, b ∈ Z. If a2(b2 − 2b) is odd, then a and b are odd.
4. Suppose a, b, c ∈ Z. If a does not divide bc, then a does not divide b.
5. Suppose x ∈ R. If x2 + 5x < 0 then x < 0.
6. Suppose x ∈ R. If x3 − x > 0 then x > −1.
7. Suppose a, b ∈ Z. If both ab and a + b are even, then both a and b are even.
8. Suppose x ∈ R. If x5 − 4x4 + 3x3 − x2 + 3x − 4 ≥ 0, then x ≥ 0.
9. Suppose n ∈ Z. If 3 - n2, then 3 - n.
10. Suppose x, y, z ∈ Z and x 6= 0. If x - yz, then x - y and x - z.
11. Suppose x, y ∈ Z. If x2(y + 3) is even, then x is even or y is odd.
12. Suppose a ∈ Z. If a2 is not divisible by 4, then a is odd.
13. Suppose x ∈ R. If x5 + 7x3 + 5x ≥ x4 + x2 + 8, then x ≥ 0.
B. Prove the following statements using either direct or contrapositive proof.
Sometimes one approach will be much easier than the other.
14. If a, b ∈ Z and a and b have the same parity, then 3a + 7 and 7b − 4 do not.
15. Suppose x ∈ Z. If x3 − 1 is even, then x is odd.
16. Suppose x ∈ Z. If x + y is even, then x and y have the same parity.
17. If n is odd, then 8 | (n2 − 1).
18. For any a, b ∈ Z, it follows that (a + b)3 ≡ a3 + b3 (mod 3).
19. Let a, b ∈ Z and n ∈ N. If a ≡ b (mod n) and a ≡ c (mod n), then c ≡ b (mod n).
20. If a ∈ Z and a ≡ 1 (mod 5), then a2 ≡ 1 (mod 5).
21. Let a, b ∈ Z and n ∈ N. If a ≡ b (mod n), then a3 ≡ b3 (mod n)
22. Let a ∈ Z, n ∈ N. If a has remainder r when divided by n, then a ≡ r (mod n).
23. Let a, b, c ∈ Z and n ∈ N. If a ≡ b (mod n), then ca ≡ cb (mod n).
24. If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n).
25. If n ∈ N and 2n − 1 is prime, then n is prime.
26. If n = 2k − 1 for k ∈ N, then every entry in Row n of Pascal’s Triangle is odd.
27.
¡ a ¢
If a ≡ 0 (mod 4) or a ≡ 1 (mod 4), then 2 is even.
28. If n ∈ Z, then 4 - (n2 − 3).
29. If integers a and b are not both zero, then gcd(a, b) = gcd(a − b, b).
30. If a ≡ b (mod n), then gcd(a, n) = gcd(b, n).
31. Suppose the division algorithm applied to a and b yields a = qb + r. Then
gcd(a, b) = gcd(r, b).
CHAPTER
6
Proof by Contradiction
e now explore a third method of proof: proof by contradiction.
W This method is not limited to proving just conditional statements—
it can be used to prove any kind of statement whatsoever. The basic idea
is to assume that the statement we want to prove is false, and then show
that this assumption leads to nonsense. We are then led to conclude that
we were wrong to assume the statement was false, so the statement must
be true. As an example, consider the following proposition and its proof.
Proposition
If a, b ∈ Z, then a2 − 4b 6= 2.
Proof. Suppose this proposition is false.
This conditional statement being false means there exist numbers a and b
for which a, b ∈ Z is true, but a2 − 4b 6= 2 is false.
In other words, there exist integers a, b ∈ Z for which a2 − 4b = 2.
From this equation we get a2 = 4b + 2 = 2(2b + 1), so a2 is even.
Because a2 is even, it follows that a is even, so a = 2c for some integer c.
Now plug a = 2c back into the boxed equation to get (2c)2 − 4b = 2,
so 4c2 − 4b = 2. Dividing by 2, we get 2c2 − 2b = 1.
Therefore 1 = 2(c2 − b), and because c2 − b ∈ Z, it follows that 1 is even.
We know 1 is not even, so something went wrong.
But all the logic after the first line of the proof is correct, so it must be
that the first line was incorrect. In other words, we were wrong to assume
the proposition was false. Thus the proposition is true.
■
You may be a bit suspicious of this line of reasoning, but in the next
section we will see that it is logically sound. For now, notice that at
the end of the proof we deduced that 1 is even, which conflicts with our
knowledge that 1 is odd. In essence, we have obtained the statement
(1 is odd)∧ ∼ (1 is odd), which has the form C∧ ∼ C. Notice that no matter
what statement C is, and whether or not it is true, the statement C∧ ∼ C
is false.
A statement—like this one—that cannot be true is called a
contradiction. Contradictions play a key role in our new technique.
112
Proof by Contradiction
6.1 Proving Statements with Contradiction
Let’s now see why the proof on the previous page is logically valid. In
that proof we needed to show that a statement P : (a, b ∈ Z) ⇒ (a2 − 4b 6= 2)
was true. The proof began with the assumption that P was false, that is
that ∼ P was true, and from this we deduced C∧ ∼ C. In other words we
proved that ∼ P being true forces C∧ ∼ C to be true, and this means that
we proved that the conditional statement (∼ P) ⇒ (C ∧ ∼ C) is true. To see
that this is the same as proving P is true, look at the following truth table
for (∼ P) ⇒ (C ∧ ∼ C). Notice that the columns for P and (∼ P) ⇒ (C ∧ ∼ C)
are exactly the same, so P is logically equivalent to (∼ P) ⇒ (C ∧ ∼ C).
P
C
∼ P
C ∧ ∼ C
(∼ P) ⇒ (C ∧ ∼ C)
T
T
F
F
T
T
F
F
F
T
F
T
T
F
F
F
F
T
F
F
Therefore to prove a statement P, it suffices to instead prove the conditional
statement (∼ P) ⇒ (C ∧ ∼ C). This can be done with direct proof: Assume
∼ P and deduce C ∧ ∼ C. Here is the outline:
Outline for Proof by Contradiction
Proposition
P.
Proof. Suppose ∼ P.
...
Therefore C ∧ ∼ C.
■
One slightly unsettling feature of this method is that we may not know
at the beginning of the proof what the statement C is going to be. In
doing the scratch work for the proof, you assume that ∼ P is true, then
deduce new statements until you have deduced some statement C and its
negation ∼ C.
If this method seems confusing, look at it this way. In the first line of
the proof we suppose ∼ P is true, that is we assume P is false. But if P is
really true then this contradicts our assumption that P is false. But we
haven’t yet proved P to be true, so the contradiction is not obvious. We
use logic and reason
ing to transform the non-obvious contradiction ∼ P to
an obvious contradiction C∧ ∼ C.
Proving Statements with Contradiction
113
The idea of proof by contradiction is quite ancient, and goes back at
least as far as the Pythagoreans, who used it to prove that certain numbers
p
are irrational. Our next example follows their logic to prove that
2 is
irrational. Recall that a number is rational if it equals a fraction of two
integers, and it is irrational if it cannot be expressed as a fraction of two
integers. Here is the exact definition.
Definition 6.1
A real number x is rational if x = ab for some a, b ∈ Z.
Also, x is irrational if it is not rational, that is if x 6= ab for every a, b ∈ Z.
p
We are now ready to use contradiction to prove that
2 is irrational.
According to the outline, the first line of the proof should be “Suppose that
p
it is not true that
2 is irrational.” But it is helpful (though not mandatory)
to tip our reader off to the fact that we are using proof by contradiction.
One standard way of doing this is to make the first line “Suppose for the
p
sake of contradiction that it is not true that
2 is irrational. "
p
Proposition
The number
2 is irrational.
p
Proof. Suppose for the sake of contradiction that it is not true that
2 is
p
irrational. Then
2 is rational, so there are integers a and b for which
p
a
2 = .
(6.1)
b
Let this fraction be fully reduced; in particular, this means that a and b are
not both even. (If they were both even, the fraction could be further reduced
by factoring 2’s from the numerator and denominator and canceling.)
Squaring both sides of Equation 6.1 gives 2 = a2
b2 , and therefore
a2 = 2b2.
(6.2)
From this it follows that a2 is even. But we proved earlier (Exercise 1
on page 110) that a2 being even implies a is even. Thus, as we know
that a and b are not both even, it follows that b is odd. Now, since a is
even there is an integer c for which a = 2c. Plugging this value for a into
Equation (6.2), we get (2c)2 = 2b2, so 4c2 = 2b2, and hence b2 = 2c2. This
means b2 is even, so b is even also. But previously we deduced that b is
odd. Thus we have the contradiction b is even and b is odd.
■
To appreciate the power of proof by contradiction, imagine trying to
p
prove that