Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Logic of Indirect Proofs


Date: 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.

Hope this helps. 

-Doctor Donald,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Logic

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/