From CS2800 wiki
(Redirected from Proof by contradiction)

You can think of "proof by contradiction" as a way of using "not [math]P [/math]". If you are able to prove both [math]P [/math] and "not [math]P [/math]", then you must have made contradictory assumptions at some point; this means you can go back to your most recent assumption and conclude that it was invalid. This is useful to rule out cases when doing case analysis.

It is often a good way to start a proof: assume that what you are trying to prove is false, and then find a contradiction. At that point, you know your assumption was incorrect, so the original claim must be true.

This style of proof usually starts "Assume for the sake of contradiction, that [math]P [/math] is false..." and usually ends "...this is a contradiction, and [math]P [/math] must have been true in the first place." It is a useful approach when the claim you are trying to prove already has a logical negation in it, for example if you are trying to prove that something is not injective or not countable. You assume that it is injective or countable, and then you have a fact that you can work with.