Book of Proof

Home > Other > Book of Proof > Page 16
Book of Proof Page 16

by Richard Hammack


  ■

  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

 

‹ Prev