FRESH

Hacker News

Making Sense of Proof by Contradiction [pdf]

45 points by surprisetalk

by sunday_serif

1 subcomments

For me, proof by contradiction only clicked (recently!) once I understood that logical consequence and unsatisfiability are equivalent.
Once I understood that and reframed the contradiction as a statement about unsatisfiability… I could then see directly how the positive result you get is the equivalent logical consequence.
Unfortunately, I feel like this intuition only really helps if you are pretty immersed in formal logic… otherwise it just sounds like jibberish.

by butokai

7 subcomments

This document misses the point in a way that very commonly arises when mathematicians (as opposed to logicians) discuss proof by contradiction. The examples in this document all revolve around assuming a fact, showing that it would lead to an absurd, and thus establishing that that fact can’t be the case: there is no rational equal to sqrt(2), there is no finite listing of all the primes. They are not using proof by contradiction at all, and on the contrary these proof are fully constructive: if one where to give us what they believe is a finite list of all the primes, the proofs gives us a method to construct a new prime.
Proof by contradiction, on the other side, deems that we derive a contradiction from the assumption that a statement does not hold. Then, by contradiction, we may state that is true because it is impossible for it to be false.
This is why it is rejected by the intuitionists and constructivists: there is no way to extract an explicit procedure from such a proof, since it only states that what can’t be false must me true.

by dhosek

1 subcomments

Worth noting, a lot of times, what people think is proof by contradiction is in fact proving the contrapositive (i.e., if you want to prove, “if p then q”, proving “if not q then not p” will also suffice).

by luisgvv

0 subcomment

This reminds me of the first time I was shown this in college.
I loved this method so much that in my first formal logic test I tried to solve all of the problems via this method. It was a fun experience lol

by leephillips

0 subcomment

All difficult conjectures should be proved by reductio ad absurdum arguments. For if the proof is long and complicated enough you are bound to make a mistake somewhere and hence a contradiction will inevitably appear, and so the truth of the original conjecture is established QED.
-- John Barrow

by calf

1 subcomments

It's interesting that even a child can do it, but actually explaining it clearly gets confusing. One problem is that as soon as you use "Suppose A then following steps S we get not A", but a hidden, implied premise is the stipulation that the world you are reasoning about already has certain consistency properties. This premise is what trips people (students like me) up because it is not part of the rules of algebra, geometry, etc.