41
$\begingroup$

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

$\endgroup$
  • 13
    $\begingroup$ 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. $\endgroup$ – Guest Mar 29 '16 at 22:56
  • 3
    $\begingroup$ @ElliotG you are giving wrong information, CH is independent of ZFC meaning that its relatively consistent and it's negation is too. $\endgroup$ – Jens Renders Mar 29 '16 at 23:11
  • 1
    $\begingroup$ @JensRenders thanks for letting me know $\endgroup$ – Elliot G Mar 29 '16 at 23:14
  • 20
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Mar 30 '16 at 4:35
  • 6
    $\begingroup$ 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/… $\endgroup$ – Thompson Mar 30 '16 at 11:28
50
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ How do you get from inconsistency of P to provable not P in an intuitionistic logic? $\endgroup$ – Taemyr Mar 30 '16 at 14:36
  • 1
    $\begingroup$ Or P is an innate paradox where neither P nor ¬P is true. Say for example, P reads "This sentence is false." $\endgroup$ – Joshua Mar 30 '16 at 15:20
  • 2
    $\begingroup$ @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. $\endgroup$ – chi Mar 30 '16 at 15:45
  • 1
    $\begingroup$ @chi "If the axioms are inconsistent with p, this can be done -- and constructively so." why? $\endgroup$ – Taemyr Mar 30 '16 at 15:59
  • 2
    $\begingroup$ @Taemyr "$p$ is inconsistent with the axioms" means "the axioms and $p$ prove $\bot$". $\endgroup$ – chi Mar 30 '16 at 16:01
35
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Taemyr Mar 30 '16 at 14:48
  • 2
    $\begingroup$ *"independent of the standard set theory axioms (ZFC)". $\endgroup$ – djechlin Mar 30 '16 at 14:53
  • 3
    $\begingroup$ 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 $\endgroup$ – Dan Sheppard Mar 30 '16 at 19:18
  • $\begingroup$ 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. $\endgroup$ – MJD Apr 2 '16 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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