4
$\begingroup$

One of my friends 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?

  • 0
    @Rajesh Don't worry about it I have bad days all the time.2011-07-11

1 Answers 1

9

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.