Take the 2-minute tour ×
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.

Suppose we wish to prove $P$ implies $Q$. We assume $P$. Proof by contradiction begins by assuming not $Q$, and from these two assumptions, a "contradiction" is derived. Now, sometimes that contradiction is that $Q$ is true. I can't help but to feel the argument is circular, yet I can't make precise what it is that bothers me. We're saying not $Q$ implies $Q$, hence $Q$ must be true to begin with. Why are proofs by contradiction of these kind rigorous?

share|improve this question
    
One can look at this without using contradiction, since –  Patrick Feb 26 '12 at 20:56
    
Please ignore the comment above, I accidentally hit "enter" before it was finished. –  Patrick Feb 26 '12 at 21:04

4 Answers 4

up vote 31 down vote accepted

The following is a tautology: $$(R\to \neg R) \to \neg R.$$ That is, if from a premise we can prove the premise is false, then the premise is false.

If from $P$ and $\neg Q$ we can prove $Q$, then from $P$ we can prove $\neg Q\to Q$; replacing $R$ with $\neg Q$ in the tautology above, we obtain $$(\neg Q\to \neg(\neg Q))\to \neg\neg Q.$$

In non-intuitionistic logic, classical logic, the Law of the Excluded Middle tells us that $\neg\neg Q\leftrightarrow Q$ is a tautology. By substituting and using Modus Ponens, we then have that from $P$ we can deduce $ Q$. Since from $P$ we can deduce $Q$, we conclude that $P\to Q$ holds.

That is:

$$\begin{align*} 1.&&P,\neg Q&\vdash Q&\text{(what we are assuming we can prove)}\\ 2.&&P&\vdash \neg Q\to Q &\text{(Deduction Theorem)}\\ 3.&&P&\vdash ((\neg Q\to \neg\neg Q)\to \neg\neg Q) &\text{(Tautology)}\\ 4.&&P&\vdash \neg\neg Q\leftrightarrow Q &\text{(Tautology)}\\ 5.&&P&\vdash (\neg Q\to Q)\to Q &\text{(by substitution of 4 in 3)}\\ 6.&&P&\vdash Q &\text{(Modus ponens, 2,5)}\\ 7.&&&\vdash P\to Q &\text{(Deduction Theorem)} \end{align*}$$

That said:

It is very common to find what I call "fake proofs by contradiction." Proofs in which we wish to prove $P\to Q$; we assume both $P$ and $\neg Q$. Then without using the assumption $\neg Q$, we proceed to use the assumption $P$ to establish $Q$. Then the author says "But this contradicts $\neg Q$, a contradiction; therefore, $Q$."

That is bad form and a badly written proof. The proof can be done directly by simply removing the line that says "Assume $\neg Q$", and removing the line that says "But this contradicts $\neg Q$, a contradiction." That is, what we have is a direct proof, that has been turned into a proof by contradiction by adding an extra assumption at the beginning (which is never used) and an extra line at the end (which only notes that the new extra line at the beginning contradicts our earlier conclusion).

For example:

Theorem. If $V$ is a vector space, and $W_1$ and $W_2$ are proper subspaces of $V$, then $V\neq W_1\cup W_2$.

Fake proof by contradiction. Assume to the contrary that $V=W_1\cup W_2$.

If $W_1\subseteq W_2$, then $W_1\cup W_2=W_2\neq V$, because we are assuming $W_1$ and $W_2$ are proper subspaces. So we may assume that $W_1\not\subseteq W_2$. Symmetrically, if $W_2\subseteq W_1$, then $W_1\cup W_2=W_1\neq V$, so we may assume $W_2\not\subseteq W_1$.

Let $w_1\in W_1-W_2$, and $w_2\in W_2-W_1$. Then $w_1+w_2\notin W_1$ (since $w_1\in W_1$ but $w_2\notin W_2$); and $w_1+w_2\notin W_2$ (since $w_2\in W_2$ but $w_1\notin W_1$). Hence $w_1+w_2\notin W_1\cup W_2$. Thus, $w_1+w_2\in V-(W_1\cup W_2)$, so $V\neq W_1\cup W_2$.

But this contradicts our assumption that $V=W_1\cup W_2$. Therefore, this assumption is false, and so we conclude that $V\neq W_1\cup W_2$. $\Box$

Now notice that if we delete the first lines ("Assume to the contrary...") and the last two lines ("But this contradicts our asumption that..."), we have a perfectly fine direct proof of what we were trying to prove! The extra lines do nothing but obscure the proof and possibly create confusion. So it's better to take them out.

Perhaps that is the kind of thing you observed, since you specifically mention a "proof by contradiction" in which the contradiction is arrived at by showing that $P$ and $\neg Q$ imply $Q$?

These are valid proofs, they just include stuff that is not needed.

Note that you are not assuming $Q$, you are assuming $\neg Q$; since you are not assuming what you want to prove, you are not engaging in circular reasoning.

share|improve this answer
    
I'd say "classical" rather than "non-intuitionistic". There are logics even weaker than intuitionistic logic which don't have the law of excluded middle. –  Zhen Lin Feb 24 '12 at 7:29
1  
Excellent answer +1 –  magma Feb 24 '12 at 11:44
    
+1 for the excellent answer, especially the paragraph on "fake proof-by-contradiction". These really are annoying! –  M Turgeon Feb 24 '12 at 14:52
    
@ZhenLin: Good point; I crossed that out. –  Arturo Magidin Feb 24 '12 at 15:46
2  
A quick way to see that $\sim Q$ is not essential in any argument of that form is: $(P\wedge \sim Q) \to Q \equiv \sim(P\wedge \sim Q) \vee Q \equiv \sim P \vee Q \vee Q \equiv \sim P \vee Q \equiv P \to Q$. –  Patrick Feb 26 '12 at 21:10

No, we prove that Q implies not Q. Then Q is contradictory, so we must have not Q. In logical symbols, we show $Q\implies \lnot Q$. If you do a truth table you will find Q must be false.

share|improve this answer

In my experience, that scenario usually means that the initial assumption of $\sim Q$ wasn't used in an essential way in the proof. Do you have an example of a proof in which $(P\wedge \sim Q) \to Q$?

share|improve this answer

I think I can see your problem. Ignoring $P$ (which is not really relevant for the confusion), we're proving $Q$ by the following technique:

Assume $\neg Q$. Then (bla bla bla bla) and therefore $Q$. But this contradicts our assumption that $\neg Q$, so we conclude $Q$.

On the face of it, this does indeed look circular -- it seems as if we're allowed never to justify our assumption of $\neg Q$ simply because it happens to contradict our eventual conclusion, in the sense that the conclusion and the assumption can't both be true at the same time.

Indeed, that is not a sound reasoning principle in general:

Assume $0=1$. Then, multiplying both sides by $2$ we get $0=2$. But this contradicts $0=1$ (because $1\ne 2$, so $0$ cannot equal both of them at the same time), so we don't need to justify our assumption that $0=1$. Thus, we have proved that $0=2$.

Luckily this is not really what happens in a proof by contradiction. One way to look at a general scheme is

Assume $\neg Q$. Then (bla bla bla bla) and therefore $R$. But $\neg Q$ and $R$ contradict each other (because bla bla bla), so we conclude $Q$.

The important point is that it is $Q$ rather than $R$ that is being concluded. The first argument above is then just an instance of this when $R=Q$ -- in which case it is so easy to see that $\neg Q$ and $R$ cannot both be true that it deserves no argument at all.

A different way of looking at the argument is to consider it an abbreviated form of this:

We know at least that either $Q$ or $\neg Q$ is true. Proceed by case analysis:

  1. Assume $Q$. Then clearly $Q$ is true.

  2. Assume $\neg Q$. Then (bla bla bla) and therefore $Q$.

Since both branches of the case analysis reached the same conclusion $Q$ (and there must always be one of the branches that holds), we can confidently conclude that $Q$ is always true.

share|improve this answer
1  
Alternatively, we take $\lnot Q \to Q$ and conclude $\lnot Q \to \bot$, hence $\lnot \lnot Q$; but $\lnot \lnot Q \to Q$ in classical logic. –  Zhen Lin Feb 24 '12 at 14:46
    
@ZhenLin: Sure, but my impression is that the OP is not aiming to construct derivations in formal logic, but merely to understand how the informal proof techniques used in ordinary mathematics work. (That is, the style of argument that formal logic is a mathematical model of). –  Henning Makholm Feb 24 '12 at 14:50

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.