Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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".

share|cite|improve this question
45  
You're a constructivist. – Git Gud Feb 22 at 23:35
27  
In classical logic we adopt the law of the excluded middle en.wikipedia.org/wiki/Law_of_excluded_middle – Zachary Selk Feb 22 at 23:37
23  
Either we have $A$, or we don’t. We prove that not having $A$ is impossible, since it leads to a contradiction. Therefore we must actually have $A$. (There are some people who don’t accept the truth of my first sentence: they don’t accept the law of the excluded middle. I have yet to meet anyone who does not accept it in everyday life, however, and I’ve very little sympathy with the objections raised by those who do have a problem with it in logic or mathematics.) – Brian M. Scott Feb 22 at 23:38
15  
Even constructivists believe $q\implies (p\lor\lnot p)$ leads to $\lnot q$. They just don't believe that $\lnot\lnot q\implies q$. @GitGud – Thomas Andrews Feb 22 at 23:40
11  
@ThomasAndrews I assume you meant $p\land \neg p$. I don't disagree and I stand by my statement. In your notation and using the OP's actual words, $q$ would be the OP's $\neg A$ and the OP is asking how to get $A$, not how to get $\neg \neg A$, hence my comment. – Git Gud Feb 23 at 0:07

12 Answers 12

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]

share|cite|improve this answer
    
To expand on the principle of explosion, it also means that if you allow contradictions to be true, you can "prove" that anything is true. It's perfectly valid to say "either A is true or the moon is made of cheese" if A is true. But if it's possible for A to also be false, then you can use that to prove that the moon is made of cheese. – Milo Price Feb 23 at 16:01
    
@MiloPrice: I think I know what you're trying to say, but then you should not use the word "possible", otherwise if you have "A is true or the moon is cheese" and only "Possibly A is false", you would only get "Possibly the moon is cheese" (in the usual modal logic for necessity and possibility). – user21820 Feb 23 at 17:36
    
Good point. My comment was meant to be read as "possible for (A to also be false [while A is true]), rather than "(possible for A to also be false) [while A is true]", where "possible" refers to the rules of the system of logic rather than states of the world. – Milo Price Feb 23 at 17:39
1  
Everything for which we know one of A and not A to be true, only one of them is true. I am unaware of an observation of the "real world" that actually shows that always A or not A is true: that presumes there is nothing inherently unknowable about the real world, and/or that the real world exists in ways we cannot know about. Are there sub-plank gremlins who move particles following our physical laws and use QM as a joke on us? That is unknowable: stating it is either true or false is ridiculous. It has no impact on any possible observations we can make. – Yakk Feb 24 at 15:14
1  
Let's try a specific statement; say, the Continuum Hypothesis (CH). Are you asserting that CH is definitely either true or false in the "real world"? I am not sure I even know what that means, much less that it is "intuitively clear". And isn't calling something "intuitively clear" basically the same as making it an axiom? In which case, your argument reduces to "if you believe the law of the excluded middle then you should believe the law of the excluded middle"... – Nemo Feb 24 at 19:09

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?

share|cite|improve this answer
    
"If it is impossible for something not to be true what other options are there?" Hm, well, what is the sound of one hand clapping? – Mehrdad Feb 23 at 5:14
3  
@Mehrdad Obligatory Simpsons link – pjs36 Feb 23 at 6:17
3  
I think your example may be precisely the kind of counter-example the OP was thinking of. If you go to the bank and ask to withdraw \$20, and the bank says it's not there, it's actually still possible that you have \$20 and they simply made a mistake. It can and does happen. So the contradiction is solved by learning there was a mistake, but it wasn't a mistake in your assumption of having \$20. Rather, it was a mistake in the bank's ability to count. If assuming A leads to contradiction, ¬A may not be the answer if the mistake was assuming B instead of ¬B. Which may mean A and ¬A contradict – MichaelS Feb 23 at 9:00
    
Nice illustration, but perhaps you should stress one aspect: this is a contradiction with already proven facts. You can well have propositions contradicting one another, but you can only reject one of them after you have proven the other. – MvG Feb 23 at 19:41
3  
I was being general (actually I was being snarky and impatient; I have no idea why people like my answer as it's just emotional). The idea is that a "contradiction" isn't simply "something troubling". It is, in context, a proof that the possibility of the proposition is false is out right impossible. Of course you have to acccept the law of excluded middle but I don't think that was the OPs concern. – fleablood Feb 23 at 22:17

NOTE FOR INTUITIONISTS: Read the OP's question: if you think the OP or any other reader at that level will benefit from what to them will be incomprehensible distinctions, by all means add to the comments on this answer.

I assume you're familiar and comfortable with proofs that don't use proof-by-contradiction. The recipe for these proofs is:

  • Start with some statements (assumptions) $X,Y,Z$ that we take to be true.
  • (Also start with a bunch of typically unstated statements we take to be true, like laws of arithmetic, or previously proved theorems.)
  • Use rules of logic that we deem to be sound: these rules take true statements and let us deduce new true statements.
  • Combine these to get a new statement, $A$. Since we started from true statements, and used rules that make new true statements out of old true statements, we conclude $A$ is true.

The recipe for a classical logic proof-by-contradiction is:

  • Start with some statements (assumptions) $X,Y,Z$ that we take to be true.
  • (Also start with a bunch of typically unstated statements we take to be true, like laws of arithmetic, or previously proved theorems.)
  • Use rules of logic that we deem to be sound: these rules take true statements and let us deduce new true statements.
  • Assume statement $P$ is true.
  • Combine these to get a new statement that we know to be false. If we hadn't included $P$, any deductions from our true statements $X,Y,Z$ would be true. We did include $P$ and deduced a false statement, so we conclude $P$ is false. Edit: More precisely, we conclude $P$ is false in the context of $X,Y,Z$ all being true, or $X \wedge Y \wedge Z$ imply $P$ is false.

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!

share|cite|improve this answer
    
Note that $P$ is a hypothesis like any other. You might as well have concluded from the same arguments that $X$, $Z$, and $P$ imply that $Y$ is false. – Marc van Leeuwen Feb 23 at 5:55
2  
And you shouldn't have lost sleep over the irrationality of $\sqrt2$. That statement just says that $\sqrt2$ cannot possibly be a rational number, and proving that is obtaining a contradiction (from the rationality hypothesis). – Marc van Leeuwen Feb 23 at 5:58
    
@MarcvanLeeuwen: I hadn't notice my imprecision :-). I hope my rewording is clearer :-). – Frentos Feb 23 at 6:23
    
Frentos, @MarcvanLeeuwen is trying to say that the irrationality of $\sqrt{2}$ does not actually involve a true proof by contradiction. In intuitionistic logic contradiction elimination (or negation introduction) is still a valid rule, so if you define "irrational" as "not rational" you can still prove irrationality of $\sqrt{2}$ in intuitionistic logic. Some people even define "$\neg A$" as "$A \rightarrow \bot$" when they rewrite everything is in terms of implication and use only modus ponens. – user21820 Feb 23 at 6:43
    
@user21820: As per my comment and clarified answer (did you read it?), my past loss of sleep was not over the fact of irrationality of $\sqrt2$ per se, but over the subjective weirdness of the particular proof by contradiction of that fact to which I had then been exposed. I've known of constructive proofs of the same fact for years, and in any case no longer have qualms about the nonconstructive proofs. But thanks for your final sentence - that was news to me :-). – Frentos Feb 23 at 7:43

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.

share|cite|improve this answer
4  
Your first statement is true for classical logic but not intuitionistic logic. I accept classical logic, but it's better to be clear about that. My answer explains this in detail. – user21820 Feb 23 at 4:23
    
Thanks, I'll keep it in mind! – Nicolò Feb 23 at 12:32

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 direct application of an axiom (i.e., the axiom with variables replaced by specific expressions), or
  • A statement $B$, which has been preceded in the proof by two other statements $A$ and $A \implies B$.

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

  • Allowing "proofs" that contain applications of previously proven theorems, instead of starting with axioms only. This indicates an actual proof exists, since you can simply precede the abreviated proof with the proofs of each theorem used in it to create a full proof.
  • proof by added hypothesis: You create a new mathematical theory by appending an additional axiom $A$ to the normal axioms. Any proof in the augmented theory can be converted to a proof in the original theory by prepending any statements dependent on $A$ with "$A \implies$ ".
  • proof by contradiction: To prove $A$, as in proof by added hypothesis, you form a new theory by appending a new axiom. In this case, $\lnot A$. In this augmented theory you then produce a contradiction. Bourbaki had already demonstrated at this point that you can prove all statements from a contradiction. In particular, you can prove $A$ in the augmented theory. As with proof by added hypothesis, this means you can prove $\lnot A \implies A$ in the original theory. But $\lnot A \implies A$ is by definition $(\lnot \lnot A) \vee A$, which is equivalent to $A \vee A$ which in turn implies $A$.

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.

share|cite|improve this answer
    
Indeed. Double negation elimination is another way to get to the proof by contradiction, because we simply get $\neg A \imp \bot \vdash \neg \neg A \vdash A$. I forgot to mention it. In fact, the same reasoning I gave to justify the law of excluded middle and the principle of explosion also justifies the equivalence of $\neg \neg A$ and $A$, and that is how I normally explain the meaning of "$\neg$". – user21820 Feb 23 at 6:02

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:

  • Assume $\neg A$
  • Prove $B$
  • Prove $\neg B$
  • This is a contradiction, then $A$ is true.

If you want to follow the same pattern but without assuming anything false, you can do:

  • Start with $A\vee \neg A$ (always true)
  • With the same arguments as before, prove $A\vee (\neg A \wedge B)$
  • With the same arguments as before, prove $A\vee (\neg A \wedge B \wedge \neg B)$
  • Since $B \wedge \neg B$ is false, then you have just proven the following statements: $A\vee (\neg A \wedge$ false $)$, then $A\vee ($ false $)$ and finally $A$.

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".

share|cite|improve this answer

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.

share|cite|improve this answer
    
When you assume ¬A and derive a contradiction (False) it proves A because ¬A ⟹ False == A ∨ False == A, – Wouter Feb 23 at 22:41

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.

  1. If there is a contradiction between two unproven statements, that just means that they can't be true at the same time. You can't use the contradiction to directly prove or disprove either one.
  2. If one of them appears particularly plausible, then that would be a good fit for your “big problem” description. But then what you have to do is conjecture that the plausible thing holds true, and prefix every statement you derive from this with “if the … conjecture holds, then …” or “assuming the … conjecture, …”. Essentially you have proven an implication: the truth of the conjecture implies everything you derive from that.
  3. If your new statement contradicts something already proven, then you can indeed follow that the statement must be false. That's because assuming it to be true would not merely be a “big problem”, but by definition simply impossible, at least in terms of classical logic. Other answers expand on this point.
  4. Of course, theoretically we may one day find that classical logic isn't good at describing reality, and therefore choose to discard such conclusions and start from scratch. On the other hand, logic usually doesn't claim to describe reality, but instead describe formal axiomatic systems which we believe to resemble those in reality.
  5. Another thing worth considering is that someone made a mistake. But it would be wrong to say “I derived something from this proven fact, and now it's wrong.” Instead you'd have to concede that you believed some statement to be proven, when in fact it was not proven. That's because by definition, a proof can only derive true statements. Anything else may look like a proof, but isn't.
share|cite|improve this answer

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).

share|cite|improve this answer

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.

share|cite|improve this answer
    
Well a possible objection from intuitionists is that you're making the fallacy of false dichotomy. You claim that every meaningful statement is either true or false but not both. Intuitionists claim is that some meaningful statements are neither true nor false. If you prove "this is a cat" by intuitionistically acceptable means, whatever that means, then intuitionists would accept that statement as true and not false. So that statement would have a fixed truth value, and is is not justifiable for you to claim that without classical truth values every statement would be indeterminate. – user21820 Feb 25 at 8:01
    
However, your last sentence is still valid in a certain sense, namely that an intuitionist cannot prove intuitionistically that classical logic is false. – user21820 Feb 25 at 8:02

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.

share|cite|improve this answer

I get your point indeed our logic doesn't actually model everyday "reality" as we know it and fortunately it is never used by police or in courts.

Let's do an example: "Simp" has 20€ then he buy a book on logic. Since he doesn't buy a book on logic then he doesn't have 20€.

The reality: "Simp" has 20€ but he was at the store to buy the book and it was sold out, then he ordered the book but couldn't work that out so offered a dinner to Susy with 20€. Went back home and discovered that his mother made him a present: the book he wanted! Wonderful! Now he doesn't have 20€, has the book and never actually bought it. And all of this without counting the fact that "maybe" and just "maybe" he has already this same book in his father's home in Florida.

If Courts would use proof of guilty by contraddiction a lot of innocent people would be in prison. Anyway the main fact is that mathematics is not a model of our everyday reality.

---------Edit--------------

Since many comments focused on details (looking at the finger while it is pointing to the moon) -for some apparently emotional reason- I will try to be a little more general. Indeed my point is that there are a lot of thing in reality that are true and false at the same time. I might have 20€ and not having them at the same time (actually happens in everyday life). A friend of mine could be telling me the truth and laying me at the same time, and so on. In these cases the proof of contraddiction doesn't apply of course.

Should we care doing mathematics? In my opinion no since in mathematics propositions in general are black or white. But if we also want to apply mathematics then we clearly have to ask ourself how much of this approach is adequate to describe reality. A very good essay on this topic was written by a well know mathematician and philosopher Pavel Florensky and he points out that the roots of the principle of contraddiction are empirically based and not applicable in any metaphysical context or reasoning.

share|cite|improve this answer
    
What about: "If Mrs Smith murdered Mr Smith, Mr Smith would be dead. However, Mr Smith showed up yesterday badly hungover but not dead. Since he is not dead, we conclude that she did not murder him. Not Guilty"? – gmatht Feb 25 at 1:03
2  
The problem seems to be the strange premise "if S has 20€ then he buys a book on logic". For example, consider the following argument: `If S has 20€ then she buys cocaine. S had 20€, thus, she bought cocaine. Guilty!"; no argument by contradiction here, just argument from a false premise. This seems to more a case of "garbage in, garbage out" rather than a disconnect between mathematics and reality. – gmatht Feb 25 at 1:13
    
@gmatht The case you proposed is not a "proof of being guilty" by contraddiction but a "proof of being not guilty" by contraddiction. Everybody knows that when you are defensing everything is aloud. – Dac0 Feb 25 at 7:06
    
Alas I am not a lawyer, so I do not know what is allowed when defending a client. But as a logician, I know that argument by contradiction is "logical", at least if we are discussing classical logic. I am also aware of paraconsistant logics where argument by contradiction doesn't hold, but in my everyday reality I don't worry too much about the possibility that statements like "I have 20€" are both true and false simultaneously. – gmatht Feb 25 at 9:50
    
I Edit my post to explain it. My point is exactly that reality is full of thing that are simultaneously true and false – Dac0 Feb 25 at 10:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.