Proof by Contradiction, Circular Reasoning?

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_1$); and $w_1+w_2\notin W_2$ (since $w_2\in W_2$ but $w_1\notin W_2$). 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.


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.