Are proofs by contradiction really logical?

Let’s say that I prove statement A by showing that the negation of A leads to a contradiction.

My question is this: How does one go from “so there’s a contradiction if we don’t have A” to concluding that “we have A“?

That, to me, seems the exact opposite of logical. It sounds like we say “so, I’ll have a really big problem if this thing isn’t true, so out of convenience, I am just going to act like it’s true”.

Answer

Proof by contradiction, as you stated, is the rule\def\imp{\Rightarrow}\neg A \imp \bot \vdash A” for any statement A, which in English is “If you can derive the statement that \neg A implies a contradiction, then you can derive A“. As pointed out by others, this is not a valid rule in intuitionistic logic. But I shall now show you why you probably have no choice but to agree with the rule (under certain mild conditions).

You see, given any statement A, the law of excluded middle says that “A \lor \neg A” is true, which in English is “Either A or \neg A“. Now is there any reason for this law to hold? If you desire that everything you can derive comes with direct evidence of some sort (such as various constructive logics), then it might not hold, because sometimes we have neither evidence for nor against a statement. However, if you believe that the statements you can make have meaning in the real world, then the law obviously holds because the real world either satisfies a statement or its negation, regardless of whether you can figure out which one.

The same reasoning also shows that a contradiction can never be true, because the real world never satisfies both a statement and its negation at the same time, simply by the meaning of negation. This gives the principle of explosion, which I will come to later.

Now given the law of excluded middle consider the following reasoning. If from \neg A I can derive a contradiction, then \neg A must be impossible, since my other rules are truth-preserving (starting from true statements they derive only true statements). Here we have used the property that a contradiction can never be true. Since \neg A is impossible, and by law of excluded middle we know that either A or \neg A must be true, we have no other choice but to conclude that A must be true.

This explains why proof by contradiction is valid, as long as you accept that for every statement A, exactly one of “A” and “\neg A” is true. The fact that we use logic to reason about the world we live in is precisely why almost all logicians accept classical logic. This is why I said “mild conditions” in my first paragraph.

Back to the principle of explosion, which is the rule “\bot \vdash A” for any statement A. At first glance, this may seem even more unintuitive than the proof by contradiction rule. But on the contrary, people use it without even realizing. For example, if you do not believe that I can levitate, you might say “If you can levitate, I will eat my hat!” Why? Because you know that if the condition is false, then whether the conclusion is true or false is completely irrelevant. They are implicitly assuming the rule that “\bot \imp A” is always true, which is equivalent to the principle of explosion.

We can hence show by a formal deduction that the law of excluded middle and the principle of explosion together give the ability to do proofs by contradiction:

[Suppose from “\neg A” you can derive “Contradiction”.]

A \lor \neg A. [law of excluded middle]

  If A:

    A.

  If \neg A:

    Contradiction.

    Thus A. [principle of explosion]

  Therefore A. [disjunction elimination]

Another possible way to obtain the proof by contradiction rule is if you accept double negation elimination, that is “\neg \neg A \vdash A” for any statement A. This can be justified by exactly the same reasoning as before, because if “A” is true then “\neg A” is false and hence “\neg \neg A” is true, and similarly if “A” is false so is “\neg \neg A“. Below is a formal deduction showing that contradiction elimination and double negation elimination together give the ability to do proofs by contradiction:

[Suppose from “\neg A” you can derive “Contradiction”.]

  If \neg A:

    Contradiction.

  Therefore \neg \neg A. [contradiction elimination / negation introduction]

  Thus A. [double negation elimination]

Attribution
Source : Link , Question Author : Simp , Answer Author : user21820

Leave a Comment