Proof by ContradictionDate: 04/29/2003 at 07:07:29 From: Ajay Subject: Proof by Contradiction Is there any specific mathematical theory that states that Proof by Contradiction is a valid proof? E.g. sqrt(2) is irrational is normally proved using contradiction. Date: 04/29/2003 at 14:54:44 From: Doctor Achilles Subject: Re: Proof by Contradiction Hi Ajay, Thanks for writing to Dr. Math. The justification comes from basic mathematical logic. A basic proof might go like this: Step 1: Prove that a contradiction must be false. 1a) Definition of contradiction: A contradiction exists any time a proposition "P" is asserted to be true in conjunction with its negation, "not-P." 1b) Definition of conjunction: A conjunction is a connective that joins two propositions. The conjunction of two propositions is true if and only if BOTH propositions are true individually. Therefore, if either individual proposition is false, or if both propositions are false, then the conjunction of the two is false. 1c) Definition of proposition: A proposition is a logical variable that stands for a statement. All propositions are either true or false, never both at the same time and never neither. (This is sometimes called the "law of the excluded middle.") 1d) Definition of negation ("not-"): The negation of a proposition is itself a proposition that necessarily carries the opposite truth value from the original (i.e. it is false if the original is true and true if the original is false). 1e) The proposition "P" is either true or false (follows from 1c). 1f) The proposition "not-P" (the negation of "P") is either false or true; it has the opposite truth value to "P" (follows from 1d). 1g) If "P" is true, then "not-P" is false; if "P" is false, then "not-P" is true (follows from 1f). 1h) Regardless of the truth value of "P", it is certain that either "P" is false or "not-P" is false (follows from 1g). 1i) The conjunction of "P" and "not-P" is necessarily false (follows from 1b and 1h). 1j) A contradiction is false (follows from 1i and 1a). Step 2: Prove that nothing false can be derived from a set of true assumptions. To make this proof complete, you have to prove that every step in a Proof by Contradiction is "truth preserving"; that is: every step is such that if the assumptions and conclusions that have preceded it are true, then the conclusion of that step must be true. An example of how this might work is as follows: Proof that A can be derived from the conjunction of A and B: Assume we have the conjunction of A and B given as true. Because a conjunction can only be true if BOTH of its parts are true, both A and B are true. Thus, A must be true. Therefore, A follows from the conjunction of A and B. I have proven that you can go from the conjunction of two things to either of those things individually. You have to do a similar proof for every step, showing that if what came before is true, then what follows must also be true. This is far too much for me to do right now, but mathematics and logic never use steps which have not been proven to be "truth preserving." Step 3: Put steps 1 and 2 together. In step 1 we showed that a contradiction is false. In step 2 we showed that our conclusions MUST be true if all our assumptions were true. So now let's imagine that we do a proof. The first thing we do when we do a proof is make an assumption. We aren't sure if this assumption is true or not, but we're going to assume it is for a while and see what that gets us. Then we do a series of "truth preserving" manipulations on our assumption and on the subconclusions we reach from it. Then, all of a sudden, we find that we have reach a contradiction. We know that we have concluded something that is false (Step 1 above). We also know that IF our assumption were true, then it would not be possible to conclude something which is false (Step 2 above). Therefore the only possibility is that the assumption was never true to begin with. We can therefore say with certainty that our assumption was false. In other words, we have proven our assumption false. Hope this helps. If you have other questions or you'd like to talk about this some more, please write back. - Doctor Achilles, The Math Forum 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/