Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sorry if this is a naive question but this question really stuck me when one of my friend who got 100 % in logic told me , "when in doubt use contradiction".

When I do proofs I personally find using contradiction a lot easier. Also, from the fact that a lot of famous theorems are proved using contradiction could it be that proof by contradiction is easier or inherently more powerful than other methods of proof?

Are there any topics that discuss such things?

share|improve this question
2  
See related, possible duplicate: math.stackexchange.com/questions/240/… –  JDH Jul 11 '11 at 2:52
2  
Also related: mathoverflow.net/questions/12342/… –  Qiaochu Yuan Jul 11 '11 at 2:57
    
@Mark: So-called "direct" proofs often have a more constructive character. But the difference is often illusory. For example, the Cantor diagonalization argument, which is often cited as a proof by contradiction of the existence of transcendental numbers, can be turned in a mechanical way into an explicit construction of a transcendental number. –  André Nicolas Jul 11 '11 at 3:19
    
@JDH I understand that in logic proof by contradiction and proof by construction are logically equivalent. But that doesn't explain by so many theorems use contradiction (e.g. is it possible to construct an irrational number? I am not sure). Or why some theorems become alot easier to prove when using contradiction. –  Mark Jul 11 '11 at 3:19
    
@user6312 do you know of a theorem that must use contradiction to prove? –  Mark Jul 11 '11 at 3:21

1 Answer 1

up vote 9 down vote accepted

Finding a proof by contradiction often is easier, because you have more to work with. Suppose that you’re trying to prove an implication $\phi \to \psi$. For a direct proof you have only $\phi$ to work with (plus whatever related facts you may know). Similarly, for a proof of the contrapositive you have only $\lnot\psi$. For a proof by contradiction, however, you have both $\phi$ and $\lnot\psi$ at your disposal. Every direct consequence of $\phi$ is available to you, and so is every direct consequence of $\lnot\psi$.

Not infrequently you still end up with a direct proof of either $\phi \to \psi$ or its contrapositive, or something that can very easily be turned into such a proof, but this doesn’t negate the benefit of having more resources on hand when you start looking for a proof.

That said, I agree with user6312 that some results often presented (and perhaps most easily found) as proofs by contradiction would be more illuminating if presented in some other way. I’d even use the same example, though in a slightly different way: Cantor’s diagonal argument is really just a machine for producing a real number that isn’t in a given countable list of real numbers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.