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".
On
The solution comes from the definition of statement: you may have not hought about it, but it is, by definition, something that must be true or false. Since you get a contradiction assuming $A$ is false, it must necessarily be true. There may be some things that are not statements in real life, but in mathematics we usually deal only with them.
On
A contradiction isn't a “problem”. A contradiction is an impossibility. This isn't a matter of saying “Gee, if I have fewer than 20 dollars in the back I won't be able to go out to dinner and I want to so badly, I'll just assume I have more than 20 dollars.” This is a matter of walking into the bank and saying "I'd like to withdraw 20 dollars" and having a trapdoor under you collapse and a 300 lb security guard jumping on your spleen shouting in you ear “You don't have it!!! You don't have it!!”
You can't just say “Oh, I got a contradiction when I assumed I had 20 dollars... But that doesn't mean I don't have 20 dollars.”
It means precisely that. It is impossible for you to have 20. So you must conclude you don't have 20 dollars.
If you get a contradiction, it just isn't possible for A to be false.
A contradiction, by its definition is an impossibility. So if you assume A isn't true and you get a contradiction. You have proven that it is impossible for A not to be true. If it is impossible for something not to be true what other options are there?
On
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]
On
I found Bourbaki's "Theory Of Sets" helpful in deepening my understanding of the concept of proof when I was an undergraduate. In it "he" introduces a particular formal language, and proceeds to rigorously define the concept of proof. In particular he introduces the logical symbols $\vee$ and $\lnot$. He defines $A \implies B$ to be $\lnot A \vee B$, and introduces a few axioms such as $A \vee B \implies B \vee A, A \implies A \vee B, A \vee A \implies A$, and most importantly, $$\lnot\lnot A \Longleftrightarrow A$$ That is the key axiom for proof by contradiction. (This is not contradicting user21820's statements about the law of the excluded middle - just coming at it from a different direction.)
A proof, according to Bourbaki, is a list of statements such that every statement in the list is
A theorem is any statement that appears in a proof. After introducing this concept, he then develops several common proof techniques, which in his parlance are not actual proofs, but meta-mathematical arguments that actual proofs exist. These include
So in a theory where basis laws of logic hold, if $\lnot\lnot A \Longleftrightarrow A$ also holds, any proof by contradiction can be translated into a normal proof.
Of course, this is only one example of how to develop a theory of proof, and others may prefer different approaches. But it remains to me the clearest demonstration I've encountered.
On
easy to follow but not exacting or rigorous answer...
Yes as long as the contrapositive is constructed in such a way that the answer space is complete and you disprove the contrapositive in the general case.
so picture a venn diagram that where there is clear lint between true and false and all the space is filled with one or the other with no overlaps. Then find a way to contradict false in such generality that you can cross out all of false. Well all you have left is true so accept it.
On
Actually the reductio ad absurdum (RAA) is a little bit controversial. There exists a branch of mathematics that rejects that way of proving things it's called constructive or intutionistic math.
The thing is how you go about contradictions, how you interpret that. That is how you interpret the fact that you have proven both $\phi$ and $\neg\phi$ or perhaps that you've proven $\phi\land\neg\phi$. The standard interpretation is that implication means that the right hand statement is true whenever the left hand statement is, which means that an implication is true if either the right statement is true or the left statement is false (or both). This means that if the left statement is false then the implication holds. One also consider any statement on the form $\phi\land\neg\phi$ to be false.
So with that interpretation we always would have $(\phi\land\neg\phi)\rightarrow\psi$, so if we can from $\neg\psi$ prove both $\phi$ and $\neg\phi$ and thereby $\phi\land\neg\phi$ we would have $\neg\phi\rightarrow(\psi\land\neg\psi)\rightarrow\psi$. And of course you have $\psi\rightarrow\psi$. From this follows that $(\psi\lor\neg\psi)\rightarrow\psi$, and we consider $\psi\lor\neg\psi$ to be true.
Basically RAA is based on the fact that a statement is considered either true or false (even if we are not able to prove it), and how that makes compound statements true or false (by using negation, implication, conjunction, disjunction etc).
On
It's just case analysis with the assumption that one of the cases must be valid. Proof that all cases but one are invalid. The one left over therefore has to be valid. The only thing you can challenge is the assumption doesn't hold.
On
Another way to see it is that a proof by contradiction is a simplification where you "forget", for a while, that $A$ can be true.
An usual scheme of proof by contradiction is the following:
If you want to follow the same pattern but without assuming anything false, you can do:
This approach manipulates only true statements, which is arguably comfortable in a proof, but the cost is that we always take into account that "$A$ can also be true". Then, the bottom line is basically "Either $A$ is true, or nothing".
On
I agree with @user21820 but there is a deeper point. You say:
You see, given any statement A, the law of excluded middle says that "A ∨¬A" is true, which in English is "Either A or ¬A". Now is there any reason for this law to hold?
The deeper point is that if the law was not true, then nothing could be proven, nothing would be true or false. The concept of "proof" starts with the axiom that A is not non-A, to keep it in English, with a hat-tip to Aristotle for this discovery.
If it were possible for A to be, at the same time and in the same respect, non-A, then you could make no statements whatsoever. You could not say "this is a cat" or "this conclusion is correct" or even "I am hungry." Why not? Because a cat could be a non-cat (a dog, a bus or a musical symphony); a feeling of hunger could be a sound, a sunrise or a moment in history; and a conclusion would continuously vary in content and in outcome: nothing would be set, nothing would certain, everything would be an ever changing, primordial mixture of colors, sounds and sensations.
Because we start with the axiom A is not non-A, we can start with simple observations and form an unbroken chain to the abstract heights where proof, certainty and reason are possible. Without this simple starting point, we would never get there. Anyone who tries to deny the axiom A is not non-A has to use it in order to attempt to prove it is not true, which is another well-known fallacy.
On
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".
I think it's worth considering several cases.
On
The best way to get a perspective on the issue - as already seen by many of the replies here - is to pull back from classical logic to something more general and to address the matter in the more general setting. The reason is that classical logic flattens out important distinctions that lend the needed perspective on the matter and clarify what is going on. So, we need to consider a more general setting where those distinctions are not conflated.
In reality, what you're actually asking - in reverse - is what kind of logic permits the rule you cited. When you ask "why", you also need to have something on the playing field where the "why not" is also the case: and that's what makes it necessary to step back. Otherwise, the answer would simply be "the rule is a rule in classical logic, because that's just what classical logic is" and that would be that.
But actually, even a foray into intuitionistic logic isn't enough. To get a better view, still, of the matter, you should also broaden the scope to bi-intuitionist logic. I will show you, first, a comparison of the three and where they fit in terms of the question and see where everything fits together.
There are actually two senses of the word "not" that are in common use; and people do actually make a distinction between the two. The weaker version of "not A" is "A is not true", while the strong one of "not A" is "A is false". The most familiar example is seen in political discourse, where respected adversaries disagree not by saying the other person's point "is false", but only that it is "not true".
In classical logic, no such distinction exists: they're the same.
In intuitionistic logic, only "is false" sense can be formulated: formalizing the "is false" sense of "not A" as ¬A = A⊃⊥. This is expressed in terms of the "only if" connective ⊃ (i.e. A⊃B means "A only if B", or equivalently "if A then B") and the "false" statement ⊥. So, let's call the stronger version of not "refute".
A key property - the defining property in fact - of the conditional is that there is a one-to-one correspondence between inferences C∧A ⊢ B (that is: inferences of B from the conjunction "C and A") and inferences C ⊢ A⊃B (i.e. inferences of the conditional A⊃B from C alone). The two are equivalent.
Applied to the "refute" operator, this expresses a one-to-one correspondence between C∧A ⊢ ⊥ and C ⊢ ¬A ... voilá! There's part of what you're looking for: the positive version of proof by contradiction. If C and A together yield a contradiction then from C alone we may infer the strong "A is false" version of "not A" - that we: we may refute A, from C.
If you use this version of "not", then the best you can achieve from this is to start with the inference C∧¬A ⊢ ⊥ and conclude that C ⊢ ¬¬A. In classical logic, this is good enough, because you have the double-negative rule. But this doesn't really answer your question: it only shifts the question over to the double-negative rule and puts the spotlight on that, instead. And, so you don't get any real insight on the matter other than "it holds in classical logic, but not in intuitionistic logic ... because they're different."
You actually want the negative version of proof by contradiction, that whenever the inference (the context of Other Stuff) and (not A) ⊢ ⊥ holds, then we also have the inference (the context of Other Stuff) ⊢ A. That's what your question is alluding to.
Collecting all the "Other Stuff" into C, this reads as the rule that given the inference C∧(not A) ⊢ ⊥ we should also have the inference C ⊢ A.
Do we? Well, that's where we get into bi-intuitionistic logic; because that's actually a characterization of the other, weaker version of "not"!
Bi-intuitionistic logic is a form of logic that lies between intuitionistic and classical logic. It includes the dual versions of the "not" and "only if" operators; which we will denote here respectively: A⊂B for "A unless B", ⨽B = ⊤⊂B, for the "B is not true" version of "not B". We'll call this the "denial" operator.
Here, the property that characterizes the "unless" connective ⊂ is that there is a one-to-one correspondence between inferences A ⊢ B∨D and A⊂B ⊢ D. That is: if we can infer the disjunction B∨D (i.e. B or D) from A, then by excluding B, we may infer D, alone, i.e. from "A unless B".
When applied to the denial operator, this leads to the rule that if we can infer ⊤ ⊢ B∨D (that is: if we can actually assert that B or D is true), the we can equivalently infer ⨽B ⊢ D: i.e. we can infer D alone from the denial of B. Now you're almost where you need to be.
In bi-intuitionistic logic, a denial may be inferred from a refutation. That is: ¬A ⊢ ⨽A is a valid inference: "is not true" follows from "is false".
The instant you assert the converse as a rule, you have classical logic. Classical logic is equivalent to bi-intuitionistic logic plus the rule ⨽B ⊢ ¬B that equates denial with refutation. And that's where important distinctions start to collapse.
The threshold from intuitionistic or bi-intuitionistic logic to classical logic is actually a watershed. If any of a large number of rules is added to either form of logic, the result is equivalent to classical logic. And every single rule in that watershed is a rule that has had a long controversial history attached to it.
My favorite one is the "continuation rule", which generalizes the equivalence rule for conditionals by attaching a "continuation" (∨D) to the right. It says that the inference C∧A ⊢ B∨D is equivalent to the inference C ⊢ (A⊃B)∨D. If you add that rule to intuitionistic logic, you get classical logic.
In many cases, the watershed rules have reflections expressed in terms of the dual operators that are valid in bi-intuitionistic logic, but don't cross the watershed. So, we can begin to see the distinctions that classical logic flattens out.
First, from the trivial valid inference ¬A ⊢ ¬A, we have ¬A∧A ⊢ ⊥. The "rule of contradiction" applies to the "refute" operator. In contrast, if the same rule is expressed in terms of the denial operator B∧⨽B ⊢ ⊥, then it's actually one of the above-mentioned watershed rules that pushes you into classical logic.
Second, from the trivial valid inference ⨽B ⊢ ⨽B, we have ⊤ ⊢ B∨⨽B. The "excluded third" rule holds for the "denial" operator. But if we try to impose the same rule on the "refute" operator ⊤ ⊢ ¬A∨A, then the result (once again) is another watershed rule and we've landed in classical logic.
Bi-intuitionism plus the rule B∧⨽B ⊢ ⊥ equals classical logic.
Intuitionism plus the rule ⊤ ⊢ ¬A∨A also equals classical logic.
Your version of proof by contradiction rule (where expressed in terms of the "refute" operator) ... as we saw above ... is tantamount to the double-negative rule; and that's one of the watershed rules that pushes you into classical logic.
In contrast, when your version of the proof by contradiction rule is expressed in terms of the "denial" operator, the result is a weaker rule that actually does hold in bi-intuitionistic logic, but can't be expressed in intuitionistic logic, because it is using the extra "denial" and "unless" connectives.
To see this, suppose that taking C and the denial of B together yields a contradiction. That is: suppose we have the inference C∧⨽B ⊢ ⊥. Then, we may switch the order of the conjunction to rewrite this as ⨽B∧C ⊢ ⊥ and then apply the conversion for the "refute" operator to rewrite this equivalently as ⨽B ⊢ ¬C and apply the conversion for the "denial" operator to write this, in turn, equivalently as ⊤ ⊢ B∨¬C.
So, now let's add the supposition of C, itself, and attach it as a conjunction. Then we have C ⊢ C∧⊤ ⊢ C∧(B∨¬C) ⊢ (C∧B)∨(C∧¬C), where we apply distributivity in the last step.
Since we already have the rule of contradiction ¬C∧C ⊢ ⊥, then switching the order of the conjunction, we have the inference C∧¬C ⊢ ⊥. Applying this to the above result, we get C ⊢ (C∧B)∨(C∧¬C) ⊢ (C∧B)∨⊥ ⊢ C∧B ⊢ B.
So, the answer to your question is: Yes. Your rule is logical - but only with the weaker "denial" operator in bi-intuitionistic logic. And the answer to the implied, underlying, question (what logic is the rule valid in) is: bi-intuitionistic logic.
Many of the "watershed" rules that push you from either intuitionism or bi-intuitionism over into classical logic have weaker versions that are written by replacing one version of the "not" operator with the other. So, we can actually segregate the rules by which "not" they work with and draw a very finely-graded distinction between each of the watershed rules.
One further example I will give here is that the double-negative rule holds in one direction A ⊢ ¬¬A for the "refute" operator and in the other direction ⨽⨽B ⊢ B for the "deny" operator. The converse direction only holds for negatives; i.e. ¬¬¬A ⊢ ¬A and ⨽B ⊢ ⨽⨽⨽B are both valid.
(Correspondingly, we may then say that in intuitionistic logic, the "regular" statement - i.e. the statements equivalent to their double-negatives - are one and the same as the "negative" statements; and that classical logic is what results from intuitionistic logic by allowing only negative statements; or more briefly: classical logic is pessimistic).
There is actually an entire hierarchy of statements that may be generated from a single statement C, by repeatedly applying different combinations of ⨽ and ¬ to C; so the word "not" acquires a very nuanced meaning in bi-intuitionistic logic. So, there is plenty of room to draw many distinctions between different nuances of each of the watershed rules, as we just did above.
On
There are 13 answers already, with some getting Dozens of upvotes. I wanted to Pitch in with Some Points, which may or may not help in getting a little more clarity.
(1) Consistency : Implicitly, there are assumptions in logic and mathematics, that the Postulates & Axioms are consistent. When statements break the assumptions, we get inconsistent statements and the whole thing breaks down, meaninglessly. Eg, We can show that 0+0=0, but not show that 0+0=1. If we can show that 0+0=0 AND 0+0=1, then we can extend that to show that 0=1, then 0=(0)+(0)=(0+0)+(0+0)=(1)+(1)=2, eventually all numbers become equal. Totally meaningless. Thus, consistency is a core corner stone of logic and mathematics.
(2) Contradiction : When we show that "Statement A is true" and "Statement A is false", we are claiming that "true is false". Then there is nothing more left in logic. Totally meaningless. Everything becomes true and false. Thus we must avoid contradiction.
(3) Exactly One Possibility out of many : Comparing Integers and rational numbers, we know that either (1) A<B or (2) A=B or (3) A>B. If we can Prove that two of these Possibilities are not correct or are false, then we know that the third and last remaining Possibility must be correct or must be true. Likewise, Statement A can be either (1) true or (2) false ; If we can Prove that One Possibility is not correct, then the other Possibility must be correct.
(4) Zero Possibilities out of many : We must be careful to avoid cases where all Possibilities can be wrong. Due to various reasons, Sentences like "There is exactly one line Parallel to the given line L and Passing through Point P" & "This Statement is false" & "I always tell lies" & "Try that" & "Wow" can neither be true nor false.
(5) Proof By Contradiction : If we take "the negation of A is true" and show that there is some contradiction, then we are showing that things become inconsistent. We thus conclude "Statement A is true". Implicitly, we are assuming "Consistency" & "Either A is true or A is false". When these assumptions are wrong, this Proof is not correct.
I assume you're familiar and comfortable with proofs that don't use proof-by-contradiction. The recipe for these proofs is:
The recipe for a classical logic proof-by-contradiction is:
The above probably won't make you comfortable with proof-by-contradiction (that takes time and thought; see note below) but it should at least show you the process isn't just assuming something we want to assume.
Note: I spent many nights going to sleep worrying about the irrationality of $\sqrt2$ because the only proof I knew - using contradiction - seemed so weird!