Logic of Indirect ProofsDate: 10/16/96 at 16:49:23
From: MRS JOANNE M CARNRIKE
Subject: Logic of Indirect Proofs
Dr. Math,
I'm having troubles with logic proofs. My teacher explained the
concept of indirect proofs, but I still don't it. Can you please
explain it to me?
Thanks,
Jessica Carnrike
Date: 10/18/96 at 18:6:59
From: Doctor Donald
Subject: Re: Logic of Indirect Proofs
Most statements we try to prove have the form P=>Q, or "If P then Q",
in words. For example, consider the statement
"If x^2 = 2, then x is not a rational number."
If we wished to give a DIRECT proof of this fact, we would start by
assuming that we had some x in our hands, such that when we squared
it we got 2, and then we would try to prove, by deducing other
properties of x, that x could not possibly be rational.
The difficulty here is that it is not clear how to proceed with
deducing useful properties of x, starting from the assumption that
x^2 = 2. It is easier to deduce things when we have more to go on.
Of course, from x^2 = 2 we can deduce various things, for example
the fact that x is not 17. For 17^2 = 289, and 289 is not 2,
hence x is not 17. This is a long way from our goal of showing
that x is not rational.
An INDIRECT proof could take a couple of forms here. One is to give a
DIRECT proof of the contrapositive of P=>Q, namely ~Q=>~P. Here, the
contrapositive is the statement
"If x is rational, then x^2 does not equal 2."
You have probably learned that the contrapositive of a statement is
logically equivalent to the original statement. In any case, it is
pretty clear just from what the words mean that my second statement
says the same thing as the first one.
Why is the contrapositive here a better thing to deal with? Mainly
because it says, "assume x is rational, and try to conclude
something." If x is rational, we know that x can be written as a
quotient of integers,
x = p/q, where p and q are both integers
and we can assume that the fraction p/q is in lowest terms.
So x^2 = p^2/q^2, and we could try to think why p^2/q^2 could not
possibly be 2. This is better, but not great.
Another form an INDIRECT proof can take is "proof by contradiction."
Here we assume that the hypothesis is true and the conclusion is false
(something which could NEVER happen if the theorem is true), and then
try to deduce something nonsensical from all these assumptions. If
assumptions lead to a nonsensical conclusion, the assumptions cannot
have been true. Let's see how this works in the present example:
To prove P=>Q, assume both P and ~Q. Here, assume both that x^2 = 2
and ALSO x is rational, i.e., x = p/q for integers p, q in LOWEST
TERMS. We now have two or three assumptions about x, and hence more
stuff to reason with. Here goes:
p^2/q^2 = 2 by assumption, so p^2 = 2 q^2, using algebra. This means
that p^2 is an even integer. But then what can we say about p?
Could p be odd? No, because an odd integer times an odd integer is
odd, but p times p is even. So p is even. This means that p = 2k
say, for some integer k. Hence p^2 = (2k)^2 = 4k^2 using algebra
again.
Now we have 4 k^2 = 2 q^2, or 2 k^2 = q^2, cancelling a 2. Uh-oh,
if we go through the same process again, we are going to conclude that
q is even. This is not good, because we assumed that p/q was in
lowest terms, and now we have concluded that p and q are both even!
A fraction with even numerator and even denominator is NOT in lowest
terms, we could cancel a 2!
This is a nonsensical conclusion because it directly contradicts one
of our assumptions. So we conclude that not all of our assumptions
could have been true. Since we know that every rational number can be
put in lowest terms, the problem must be with assuming both x^2 = 2
and x is rational. So either x^2 isn't 2, or x isn't rational.
Therefore if x^2 IS 2, x can't be rational.
The indirect proof by contradiction was easier to build because we had
so many things we could assume about x. The more you can assume, in
general, the more you can deduce. In a proof by contradiction, we
always assume the hypotheses of the original statement AND the denial
of the conclusion, and hope that we have assumed so much that we can
deduce nonsense.
