Section 2.1 Proof Techniques
105
more, suppose you are trying to prove P S Q. By constructing a truth table, we
see that
(P ` Q′ S 0) S (P S Q)
is a tautology, so to prove the theorem P S Q, it is sufficient to prove P ` Q′ S 0.
Therefore, in a proof by contradiction you assume that both the hypothesis and
the negation of the conclusion are true and then try to deduce some contradiction
from these assumptions.
eXAMPLe 10
Let’s use proof by contradiction on the statement, “If a number added to itself
gives itself, then the number is 0.” Let x represent any number. The hypothesis
is x + x = x and the conclusion is x = 0. To do a proof by contradiction, assume
x + x = x and x ∙ 0. Then 2x = x and x ∙ 0. Because x ∙ 0, we can divide
both sides of the equation 2x = x by x and arrive at the contradiction 2 = 1. Hence,
(x + x = x) S (x = 0).
eXAMPLe 11
A well-known proof by contradiction shows that !2 is not a rational number.
Recall that a rational number is one that can be written in the form p/q where p
and q are integers, q ∙ 0, and p and q have no common factors (other than ± 1).
Let us assume that !2 is rational. Then !2 = p/q, and 2 = p
2
/q
2
, or 2q
2
= p
2
.
Then 2 divides p
2
, so—because 2 is itself indivisible—2 must divide p. This means
that 2 is a factor of p; hence 4 is a factor of p
2
, and the equation 2q
2
= p
2
can be
written as 2q
2
= 4x, or q
2
= 2x. We see from this equation that 2 divides q
2
and
hence 2 divides q. At this point, 2 is a factor of q and a factor of p, which contradicts the statement that p and q have no common factors. Therefore !2 is not
rational.
Example 10 notwithstanding, a proof by contradiction most immediately
comes to mind when you want to prove that something is not true. It’s hard to
prove that something is not true; it’s much easier to assume it is true and obtain
a contradiction.
ReMinDeR
To prove that something
is not true, try proof by
contradiction.
The proof of Example 11 involves more than just algebraic manipulations. It
is often necessary to use lots of words in a proof.
Proof by contradiction can be a valuable technique, but it is easy to think we
have done a proof by contradiction when we really haven’t. For example, suppose
we assume P ` Q′ and are able to deduce Q without using the assumption Q′. Then
we assert Q ` Q′ as a contradiction. What really happened here is a direct proof
of P S Q, and the proof should be rewritten in this form. Thus in Example 10,
we could assume x + x = x and x ∙ 0, as before. Then we could argue that from
PrACTiCe 6 Prove by contradiction that the product of odd integers is not even. (We did a direct
proof of an equivalent statement in Example 9.)
■
105
more, suppose you are trying to prove P S Q. By constructing a truth table, we
see that
(P ` Q′ S 0) S (P S Q)
is a tautology, so to prove the theorem P S Q, it is sufficient to prove P ` Q′ S 0.
Therefore, in a proof by contradiction you assume that both the hypothesis and
the negation of the conclusion are true and then try to deduce some contradiction
from these assumptions.
eXAMPLe 10
Let’s use proof by contradiction on the statement, “If a number added to itself
gives itself, then the number is 0.” Let x represent any number. The hypothesis
is x + x = x and the conclusion is x = 0. To do a proof by contradiction, assume
x + x = x and x ∙ 0. Then 2x = x and x ∙ 0. Because x ∙ 0, we can divide
both sides of the equation 2x = x by x and arrive at the contradiction 2 = 1. Hence,
(x + x = x) S (x = 0).
eXAMPLe 11
A well-known proof by contradiction shows that !2 is not a rational number.
Recall that a rational number is one that can be written in the form p/q where p
and q are integers, q ∙ 0, and p and q have no common factors (other than ± 1).
Let us assume that !2 is rational. Then !2 = p/q, and 2 = p
2
/q
2
, or 2q
2
= p
2
.
Then 2 divides p
2
, so—because 2 is itself indivisible—2 must divide p. This means
that 2 is a factor of p; hence 4 is a factor of p
2
, and the equation 2q
2
= p
2
can be
written as 2q
2
= 4x, or q
2
= 2x. We see from this equation that 2 divides q
2
and
hence 2 divides q. At this point, 2 is a factor of q and a factor of p, which contradicts the statement that p and q have no common factors. Therefore !2 is not
rational.
Example 10 notwithstanding, a proof by contradiction most immediately
comes to mind when you want to prove that something is not true. It’s hard to
prove that something is not true; it’s much easier to assume it is true and obtain
a contradiction.
ReMinDeR
To prove that something
is not true, try proof by
contradiction.
The proof of Example 11 involves more than just algebraic manipulations. It
is often necessary to use lots of words in a proof.
Proof by contradiction can be a valuable technique, but it is easy to think we
have done a proof by contradiction when we really haven’t. For example, suppose
we assume P ` Q′ and are able to deduce Q without using the assumption Q′. Then
we assert Q ` Q′ as a contradiction. What really happened here is a direct proof
of P S Q, and the proof should be rewritten in this form. Thus in Example 10,
we could assume x + x = x and x ∙ 0, as before. Then we could argue that from
PrACTiCe 6 Prove by contradiction that the product of odd integers is not even. (We did a direct
proof of an equivalent statement in Example 9.)
■