Page 109 - Discrete Mathematics and Its Applications

88 1 / The Foundations: Logic and Proofs

Sometimes a theorem states that several propositions are equivalent. Such a theorem states
that propositions p 1 ,p 2 ,p 3 ,...,p n are equivalent. This can be written as

p 1 ↔ p 2 ↔ ··· ↔ p n ,

which states that all n propositions have the same truth values, and consequently, that for all i
and j with 1 ≤ i ≤ n and 1 ≤ j ≤ n, p i and p j are equivalent. One way to prove these mutually
equivalent is to use the tautology

p 1 ↔ p 2 ↔ ··· ↔ p n ↔ (p 1 → p 2 ) ∧ (p 2 → p 3 ) ∧ ··· ∧ (p n → p 1 ).

This shows that if the n conditional statements p 1 → p 2 , p 2 → p 3 ,...,p n → p 1 can be shown
to be true, then the propositions p 1 ,p 2 ,...,p n are all equivalent.
This is much more efficient than proving that p i → p j for all i = j with 1 ≤ i ≤ n and
2
1 ≤ j ≤ n. (Note that there are n − n such conditional statements.)
When we prove that a group of statements are equivalent, we can establish any chain of
conditional statements we choose as long as it is possible to work through the chain to go from
any one of these statements to any other statement. For example, we can show that p 1 , p 2 , and
p 3 are equivalent by showing that p 1 → p 3 , p 3 → p 2 , and p 2 → p 1 .

EXAMPLE 13 Show that these statements about the integer n are equivalent:
p 1 : n is even.
p 2 : n − 1 is odd.
2
p 3 : n is even.

Solution:We will show that these three statements are equivalent by showing that the conditional
statements p 1 → p 2 , p 2 → p 3 , and p 3 → p 1 are true.
We use a direct proof to show that p 1 → p 2 . Suppose that n is even. Then n = 2k for some
integer k. Consequently, n − 1 = 2k − 1 = 2(k − 1) + 1. This means that n − 1 is odd because
it is of the form 2m + 1, where m is the integer k − 1.
We also use a direct proof to show that p 2 → p 3 . Now suppose n − 1 is odd. Then n −
2 2 2
1 = 2k + 1 for some integer k. Hence, n = 2k + 2 so that n = (2k + 2) = 4k + 8k + 4 =
2
2
2
2(2k + 4k + 2). This means that n is twice the integer 2k + 4k + 2, and hence is even.
To prove p 3 → p 1 , we use a proof by contraposition. That is, we prove that if n is not even,
2
2
then n is not even. This is the same as proving that if n is odd, then n is odd, which we have
already done in Example 1. This completes the proof. ▲
COUNTEREXAMPLES In Section 1.4 we stated that to show that a statement of the form
∀xP (x) is false, we need only find a counterexample, that is, an example x for which P(x)
is false. When presented with a statement of the form ∀xP (x), which we believe to be false or
which has resisted all proof attempts, we look for a counterexample. We illustrate the use of
counterexamples in Example 14.

EXAMPLE 14 Show that the statement “Every positive integer is the sum of the squares of two integers” is
false.

Solution: To show that this statement is false, we look for a counterexample, which is a particular
integer that is not the sum of the squares of two integers. It does not take long to find a counterex-
ample, because 3 cannot be written as the sum of the squares of two integers. To show this is the
2
2
case, note that the only perfect squares not exceeding 3 are 0 = 0 and 1 = 1. Furthermore,
there is no way to get 3 as the sum of two terms each of which is 0 or 1. Consequently, we have
shown that “Every positive integer is the sum of the squares of two integers” is false. ▲