104
Proofs, Induction, and Number Theory
Theorems are often stated in the form “P if and only if Q,” meaning P if Q
and P only if Q, or Q S P and P S Q. To prove such a theorem, you must prove
both an implication and its converse. Again, the truth of one does not imply the
truth of the other.
PrACTiCe 5 Write the converse of each statement in Practice 5 of Chapter 1.
ReMinDeR
“If and only if” requires
two proofs, one in each
direction.
The second part of the proof of Example 9 uses proof by cases, a form of
exhaustive proof. It involves identifying all the possible cases consistent with the
given information and then proving each case separately.
Contradiction
In addition to direct proof and proof by contraposition, you might use the technique of proof by contradiction. (Proof by contradiction is sometimes called
indirect proof, but this term more properly means any argument that is not a direct
proof.) As we did in Chapter 1, we will let 0 stand for any contradiction, that is,
any wff whose truth value is always false. (A ` A′ would be such a wff.) Once
■
eXAMPLe 9
Prove that the product x y is odd if and only if both x and y are odd integers.
We first prove that if x and y are odd, so is xy. A direct proof will work. Suppose
that both x and y are odd. Then x = 2n + 1 and y = 2m + 1, where m and n are integers. Then xy = (2n + 1)(2m + 1) = 4nm + 2m + 2n + 1 = 2(2nm + m + n) + 1.
This has the form 2k + 1, where k is an integer, so xy is odd.
Next we prove that if xy is odd, both x and y must be odd, or
xy odd S x odd and y odd
A direct proof would begin with the hypothesis that xy is odd, which leaves us little
more to say. A proof by contraposition works well because we’ll get more useful
information as hypotheses. So we will prove
(x odd and y odd)′ S (xy odd)′
By De Morgan’s law (A ` B)′ 3 A′ ~ B′, we see that this can be written as
x even or y even S xy even
(1)
The hypothesis “x even or y even” breaks down into three cases. We consider each
case in turn.
1. x even, y odd: Here x = 2m, y = 2n + 1, and then xy = (2m)(2n + 1) =
2(2mn + m), which is even.
2. x odd, y even: This works just like case 1.
3. x even, y even: Then xy is even by Example 5.
This completes the proof of (1) and thus of the theorem.
Proofs, Induction, and Number Theory
Theorems are often stated in the form “P if and only if Q,” meaning P if Q
and P only if Q, or Q S P and P S Q. To prove such a theorem, you must prove
both an implication and its converse. Again, the truth of one does not imply the
truth of the other.
PrACTiCe 5 Write the converse of each statement in Practice 5 of Chapter 1.
ReMinDeR
“If and only if” requires
two proofs, one in each
direction.
The second part of the proof of Example 9 uses proof by cases, a form of
exhaustive proof. It involves identifying all the possible cases consistent with the
given information and then proving each case separately.
Contradiction
In addition to direct proof and proof by contraposition, you might use the technique of proof by contradiction. (Proof by contradiction is sometimes called
indirect proof, but this term more properly means any argument that is not a direct
proof.) As we did in Chapter 1, we will let 0 stand for any contradiction, that is,
any wff whose truth value is always false. (A ` A′ would be such a wff.) Once
■
eXAMPLe 9
Prove that the product x y is odd if and only if both x and y are odd integers.
We first prove that if x and y are odd, so is xy. A direct proof will work. Suppose
that both x and y are odd. Then x = 2n + 1 and y = 2m + 1, where m and n are integers. Then xy = (2n + 1)(2m + 1) = 4nm + 2m + 2n + 1 = 2(2nm + m + n) + 1.
This has the form 2k + 1, where k is an integer, so xy is odd.
Next we prove that if xy is odd, both x and y must be odd, or
xy odd S x odd and y odd
A direct proof would begin with the hypothesis that xy is odd, which leaves us little
more to say. A proof by contraposition works well because we’ll get more useful
information as hypotheses. So we will prove
(x odd and y odd)′ S (xy odd)′
By De Morgan’s law (A ` B)′ 3 A′ ~ B′, we see that this can be written as
x even or y even S xy even
(1)
The hypothesis “x even or y even” breaks down into three cases. We consider each
case in turn.
1. x even, y odd: Here x = 2m, y = 2n + 1, and then xy = (2m)(2n + 1) =
2(2mn + m), which is even.
2. x odd, y even: This works just like case 1.
3. x even, y even: Then xy is even by Example 5.
This completes the proof of (1) and thus of the theorem.