40
$\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$
6
  • 14
    $\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
    Commented Mar 29, 2016 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
    Commented Mar 29, 2016 at 23:11
  • 1
    $\begingroup$ @JensRenders thanks for letting me know $\endgroup$
    – pancini
    Commented Mar 29, 2016 at 23:14
  • 21
    $\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
    Commented Mar 30, 2016 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
    Commented Mar 30, 2016 at 11:28

2 Answers 2

Reset to default
52
$\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$
6
  • 2
    $\begingroup$ How do you get from inconsistency of P to provable not P in an intuitionistic logic? $\endgroup$
    – Taemyr
    Commented Mar 30, 2016 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
    Commented Mar 30, 2016 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
    Commented Mar 30, 2016 at 15:45
  • 1
    $\begingroup$ @chi "If the axioms are inconsistent with p, this can be done -- and constructively so." why? $\endgroup$
    – Taemyr
    Commented Mar 30, 2016 at 15:59
  • 2
    $\begingroup$ @Taemyr "$p$ is inconsistent with the axioms" means "the axioms and $p$ prove $\bot$". $\endgroup$
    – chi
    Commented Mar 30, 2016 at 16:01
38
$\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
  • 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
    Commented Mar 30, 2016 at 14:48
  • 2
    $\begingroup$ *"independent of the standard set theory axioms (ZFC)". $\endgroup$
    – djechlin
    Commented Mar 30, 2016 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
    Commented Mar 30, 2016 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
    Commented Apr 2, 2016 at 15:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .