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. Hope this helps. -Doctor Donald, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/