Hacker News Reader

Comment by laichzeit0 | Hacker News Reader

What’s assumed and not explicitly stated is the law of the excluded middle. That A is true or A is false and those are the only 2 possibilities. If you assume the law of the excluded middle then it’s impossible that “A or not-A” is false. So it’s true. But “A or not-A” is true is equivalent to “A and not-A” is false (just apply DeMorgan). So proof by contradiction is you assuming something B is true and it leading to a “A and not-A” (contradiction) so clearly B must be false.

View on HN

No, the law of the excluded middle is not relevant for a demonstration by "reductio ad absurdum", when it is performed correctly.

If P is a proposition and it is demonstrated that "P implies not P", from this it can be concluded that P cannot be true and this conclusion is valid in any kind of logic, even if the law of the excluded middle is false.

Only in bivalent logic, where the law of the excluded middle is true, from the fact that a proposition is not true it can be concluded that it is false.

This is a separate thing, which has nothing to do with the technique of demonstration by a variant of reductio ad absurdum, where the goal is to prove the implication from P to not P.

We could prove P=>~P if we had earlier in our context another hypothesis Q, which is false.

So proving P=>~P does not imply P is false. It means our context is inconsistent. It could be inconsistent because of P or because of Q?

See, that's the thing. If you are saying Law of Excluded Middle matters for justification of using proof by contradiction, then we are suddenly really talking about the justification or not of classical versus non classical logics. That's kind of the author's point in the last paragraph of his article, that there's a metamathematical thing going on even if the student cannot quite articulate it. The real problem is not LEM's place in propositional logic but the cognitive move of hypothetical reasoning. Even the article leaves the question open ended.

To make this less abstract, note that in your own example you used a proof by contradiction to justify the technique of proof by contradiction. That is inherently problematic.

Reply on news.ycombinator.com