# Can proof by contradiction 'fail'?

I am familiar with the mechanism of proof by contradiction: we want to prove $P$, so we assume $¬P$ and prove that this is false; hence $P$ must be true.

I have the following devil's advocate question, which might seem to be more philosophy than mathematics, but I would prefer answers from a mathematician's point of view:

When we prove that $¬P$ is "false", what we are really showing is that it is inconsistent with our underlying set of axioms. Could there ever be a case were, for some $P$ and some set of axioms, $P$ and $¬P$ are both inconsistent with those axioms (or both consistent, for that matter)?

• An example where both $P$ and $¬P$ are consistent is where $P$ is the parallel postulate. If you take $P$ you get Euclidean geometry and if you take $¬P$ you get non-Euclidean geometries. – Guest Mar 29 '16 at 22:56
• @ElliotG you are giving wrong information, CH is independent of ZFC meaning that its relatively consistent and it's negation is too. – Jens Renders Mar 29 '16 at 23:11
• @JensRenders thanks for letting me know – Elliot G Mar 29 '16 at 23:14
• In practice, the real problem with proof by contradiction is that if you make a single mistake in your proof, you think you're done. This is probably the source of many (most?) incorrect proofs on the internet of the Riemann hypothesis, FLT, etc. – Qiaochu Yuan Mar 30 '16 at 4:35
• You have described "proof by contradiction" incorrectly. You don't assume 'not P' and "prove that this is false". What happens is that you assume 'not P' and arrive at a contradiction, i.e. you deduce a statement of the form ('Q' and 'not Q'). Being able to prove that 'not P' is false is (it seems) just being able to prove P so what you describe is a 'fake' contradiction. Gowers has a nice discussion about unnecessary attempts at proof by contradiction: gowers.wordpress.com/2010/03/28/… – Thompson Mar 30 '16 at 11:28

## 3 Answers

The situation you ask about, where $P$ is inconsistent with our axioms and $\neg P$ is also inconsistent with our axioms, would mean that the axioms themselves are inconsistent. Specifically, the inconsistency of $P$ with the axioms would mean that $\neg P$ is provable from those axioms. If, in addition, $\neg P$ is inconsistent with the axioms, then the axioms themselves are inconsistent --- they imply $\neg P$ and then they contradict that. (I have phrased this answer so that it remains correct even if the underlying logic of the axiom system is intuitionistic rather than classical.)

• How do you get from inconsistency of P to provable not P in an intuitionistic logic? – Taemyr Mar 30 '16 at 14:36
• Or P is an innate paradox where neither P nor ¬P is true. Say for example, P reads "This sentence is false." – Joshua Mar 30 '16 at 15:20
• @Taemyr $\lnot p \equiv p \rightarrow\bot$, so proving $\lnot p$ requires to assume $p$ and find a contradiction $\bot$. If the axioms are inconsistent with $p$, this can be done -- and constructively so. – chi Mar 30 '16 at 15:45
• @chi "If the axioms are inconsistent with p, this can be done -- and constructively so." why? – Taemyr Mar 30 '16 at 15:59
• @Taemyr "$p$ is inconsistent with the axioms" means "the axioms and $p$ prove $\bot$". – chi Mar 30 '16 at 16:01

It is possible for both $P$ and $\neg P$ to be consistent with a set of axioms. If this is the case, then $P$ is called independent. There are a few things known to be independent, such as the Continuum Hypothesis being independent of ZFC.

It is also possible for both $P$ and $\neg P$ to be inconsistent with a set of axioms. In this case the axioms are considered inconsistent. Inconsistent axioms result in systems which don't work in a way that is useful for engaging in mathematics.

Proof by contradiction depends on the law of the excluded middle. Constructivist mathematics, which uses intuitionistic logic, rejects the use of the law of the excluded middle, and this results in a different type of mathematics. However, this doesn't protect them from the problems resulting from inconsistent axioms.

There are logical systems called paraconsistent logic which can withstand inconsistent axioms. However, they are more difficult to work with than standard logic and are not as widely studied.

• The real problem isn't that paraconsistent logics are more difficult to work with. The problem is that they can not be as strong as classical logics. – Taemyr Mar 30 '16 at 14:48
• *"independent of the standard set theory axioms (ZFC)". – djechlin Mar 30 '16 at 14:53
• You have to be careful even with paraconsistent logics leading to contradictions with things like Curry's paradoxes even without negation with certain kinds of implication. Interestingly, a Belnap-type logic whose sentences lack constant t and f can be provably paradox-free (induction over grammar) by adding the assertions t and !f and making (!t or f) mean provably inconsistent in the embeded logic. Then you embed a classical logic into a paraconsistent one, though you can only ussually prove the form "X or the inconsistent axioms", ie X or !t or f. But nobody cares about this. Woe is me, etc – Dan Sheppard Mar 30 '16 at 19:18
• Lots of things are known to be independent. For example, each of the five Peano axioms is independent of the other four. Independence is not exceptional. – MJD Apr 2 '16 at 15:52

Other people have mentioned the possibility that $P$ and $\neg P$ could both be consistent with the axioms, in which case $P$ is independent of the axioms, and you can't derive a contradiction from either assumption.

I might also add that in intuitionistic logic, it isn't just true that proof by contradiction might fail, it's that it cannot possibly succeed. The problem described above is actually a fundamental limitation in mathematical logic. Gödel's incompleteness theorem tells us that every set of axioms powerful enough to define arithmetic on natural numbers will have this problem, so every definable system of logic will have an infinite number of statements that are neither true nor false within that system. Because of this, there is a problem in the very premise of proof by contradiction, which is the claim that, "if it's not false, then it must be true!"

Intuitionistic logic addressed this problem by stepping back from the assumption of classical logic that every statement is either true or false, because that appears to be demonstrably wrong! Instead we say that a statement $P$ is true if and only if it is a logical consequence of our axioms and inference rules. The only way to prove a statement is true is to constructively provide evidence for it, because that's what truth means! Falsehood also has a different meaning than in classical logic. Saying a statement is false, $\neg P$, is equivalent to saying $P \rightarrow \bot$, where $\bot$ (pronounced "bottom") can be thought of as evidence that every statement is true. So $\neg P$ is another way of saying that evidence for $P$ would cause the principle of explosion to kick in.

Proof by contradiction works by asserting $P \lor \neg P$, which I would translate to, "either I can provide evidence for $P$, or I can prove that $P$ implies everything is true." When phrased this way, the law of the excluded middle suddenly seems way less intuitive. Furthermore, you may notice that in this view of logic $\neg (\neg P)$ is not equivalent to $P$, but a statement that $(P \rightarrow \bot) \rightarrow \bot$! This is important, because now I can prove that $P \rightarrow \neg (\neg P)$, but I cannot prove that $\neg (\neg P) \rightarrow P$, which is the final step in every proof by contradiction. $((P \rightarrow \bot) \rightarrow \bot) \rightarrow P$ simply does not follow, so we consider it to be invalid and say we need more constructive evidence to support $P$.

In short, intuitionists are real. We walk among you. And we are here to tell you that proof by contradiction will always fail. Cheers!

• This misrepresents Gödel's theorem which states that no set of axioms capable of representing arithmetic on the set of natural numbers is both complete and consistent. This does not at all mean that there are statements that are neither true nor false but that there are statements that are true yet cannot be proved (or in the case of an inconsistent system that all statements can be proved). – Hugh Meyers Mar 30 '16 at 7:09
• Strictly speaking that's true. I should say the statement is neither true nor false within the logic. When something is independent of your axioms you can only say it's true by appealing to some outside logic. When you no longer have any outside logic to rely on, I think calling independent statements "neither true nor false" is appropriate. In what sense is the statement true (or false) if it cannot be proved? – kebertx Mar 30 '16 at 7:40
• Very hard to deal with in comments! From the wikipedia article you link to, see the context to the statement: "In this sense G is not only unprovable but true, and provability-within-the-system-T is not the same as truth." The thing about the Gödel sentence is that it makes a statement about a system from within the system. There are lots of systems that are complete and consistent. It is only when systems are powerful enough to be self-expressive that Gödelization kicks in. But this requires more space and, ideally, beer. Would that we had both! – Hugh Meyers Mar 30 '16 at 9:02
• @larkey "This statement is false" is a statement, but I think most people would agree it's neither true nor false. Gödel's diagonal lemma basically shows us that there's no way to "iron out" the self referential statements from a system that can describe the natural numbers. Even with a recursively enumerable infinite set of axioms, the logic will always be incomplete. – kebertx Mar 30 '16 at 18:17
• @kebertx While Gödel shows that sufficiently powerful systems need to have some self-referential power, this does not mean that statements of the form "this statement is false" exists. Gödel shows that it's possible to code "this statement is unprovable in S" - but we can see this as a statement that's either true or false - we just can't prove which. – Taemyr Mar 30 '16 at 19:49