Page 107 - Discrete Mathematics and Its Applications

86 1 / The Foundations: Logic and Proofs

2
2
2
2
squaring both sides of this equation, we obtain n = 4k = 2(2k ), which implies that n is
2
2
2
also even because n = 2t, where t = 2k . We have proved that if n is an integer and n is odd,
then n is odd. Our attempt to find a proof by contraposition succeeded. ▲
Proofs by Contradiction
Suppose we want to prove that a statement p is true. Furthermore, suppose that we can find
a contradiction q such that ¬p → q is true. Because q is false, but ¬p → q is true, we can
conclude that ¬p is false, which means that p is true. How can we find a contradiction q that
might help us prove that p is true in this way?
Because the statement r ∧¬r is a contradiction whenever r is a proposition, we can prove
that p is true if we can show that ¬p → (r ∧¬r) is true for some proposition r. Proofs of this
type are called proofs by contradiction. Because a proof by contradiction does not prove a result
directly, it is another type of indirect proof.We provide three examples of proof by contradiction.
The first is an example of an application of the pigeonhole principle, a combinatorial technique
that we will cover in depth in Section 6.2.
EXAMPLE 9 Show that at least four of any 22 days must fall on the same day of the week.

Solution: Let p be the proposition “At least four of 22 chosen days fall on the same day of the
week.” Suppose that ¬p is true. This means that at most three of the 22 days fall on the same
day of the week. Because there are seven days of the week, this implies that at most 21 days
could have been chosen, as for each of the days of the week, at most three of the chosen days
could fall on that day. This contradicts the premise that we have 22 days under consideration.
That is, if r is the statement that 22 days are chosen, then we have shown that ¬p → (r ∧¬r).
Consequently, we know that p is true. We have proved that at least four of 22 chosen days fall
on the same day of the week. ▲
√
EXAMPLE 10 Prove that 2 is irrational by giving a proof by contradiction.
√
Solution:Letp betheproposition“ 2 isirrational.”Tostartaproofbycontradiction,wesuppose
√
that ¬p is true. Note that ¬p is the statement “It is not the case that 2 is irrational,” which
√
says that 2 is rational. We will show that assuming that ¬p is true leads to a contradiction.
√ √
If 2 is rational, there exist integers a and b with 2 = a/b, where b = 0 and a and b
have no common factors (so that the fraction a/b is in lowest terms.) (Here, we are using the
√
fact that every rational number can be written in lowest terms.) Because 2 = a/b, when both
sides of this equation are squared, it follows that
a 2
2 = .
b 2
Hence,
2
2
2b = a .
2
2
By the definition of an even integer it follows that a is even. We next use the fact that if a is
even, a must also be even, which follows by Exercise 16. Furthermore, because a is even, by
the definition of an even integer, a = 2c for some integer c. Thus,
2
2
2b = 4c .
Dividing both sides of this equation by 2 gives
2 2
b = 2c .
2
By the definition of even, this means that b is even. Again using the fact that if the square of an
integer is even, then the integer itself must be even, we conclude that b must be even as well.