19
$\begingroup$

I stumbled across article titled "Proof of negation and proof by contradiction" in which the author differentiates proof by contradiction and proof by negation and denounces an abuse of language that is "bad for mental hygiene". I get that it is probably a hyperbole but I am genuinely curious about what's so horrible in using those two interchangeably and I struggle to see any difference at all.

  • to prove $\neg\phi$ assume $\phi$ and derive absurdity (proof by negation)

and

  • to prove $\phi$ suppose $\neg\phi$ and derive absurdity (proof by contradiction)

More specifically the author claims that:

The difference in placement of negations is not easily appreciated by classical mathematicians because their brains automagically cancel out double negations, just like good students automatically cancel out double negation signs.

Could you provide an example where the "difference in placement of negations" can be appreciated and make a difference?

The author later use two cases: the irrationality of $\sqrt{2}$ and the statement "a continuous map [0,1) on $\mathbb{R}$ is bounded" but I can't see the difference. If I massage the semantics of the proof a little bit I obtain two valid proofs as well using negation/contradiction.

Can we turn this proof into one that does not use contradiction (but still uses Bolzano-Weierstrass)?

Why would we want to do that if both proof methods are equivalent?

I feel that the crux of the article is the following sentence:

A classical mathematician will quickly remark that we can get either of the two principles from the other by plugging in ¬ϕ and cancelling the double negation in ¬¬ϕ to get back to ϕ. Yes indeed, but the cancellation of double negation is precisely the reasoning principle we are trying to get. These really are different.

I have done some research and it seems that $\neg\neg\phi$ is the issue here. To quote Wikipedia\Double_Negation on that:

this principle is considered to be a law of thought in classical logic,2 but it is disallowed by intuitionistic logic

I should probably precise that my maths background is pretty limited so far as I am finishing my first year in college. This is bugging me and I would really appreciate if someone could explain it to me. Layman terms would be great but feel free to dive deeper as well. That will be homework for the summer (and interesting for more advanced readers)!

Are proofs by contradiction and proofs of negation equivalent? If not, in which situation do differences matters and what makes them different?

$\endgroup$
18
$\begingroup$

Proof of negation and proof by contradiction are equivalent in classical logic. However there are not equivalent in constructive logic.

One would usually define $\neg \phi$ as $\phi \rightarrow \perp$, where $\perp$ stands for contradiction / absurdity / falsum. Then the proof of negation is nothing more than an instance of "implication introduction":

If $B$ follows from $A$, then $A\rightarrow B$. So in particular: If $\perp$ follows from $\phi$, then $\phi \rightarrow \perp$ ($\neg \phi$).

The following rule is of course just a special case:

If $\perp$ follows from $\neg \phi$, then $\neg \neg \phi$.

But the rule $\neg \neg \phi \rightarrow \phi$ is not valid in constructive logic in general. It is equivalent to the law of excluded middle ($\phi\vee \neg \phi$). If you add this rule to your logic, you get classical logic.

$\endgroup$
6
$\begingroup$

Intuitionistic refusal of double negation is particularly relevant in the context of "existence proofs"; see :

Classical logic contains the principle of indirect proof: If $¬A$ leads to a contradiction, $A$ can be inferred. Axiomatically expressed, this principle is contained in the law of double negation, $¬¬A → A$. The law of excluded middle, $A \lor ¬A$, is a somewhat stronger way of expressing the same principle.

Under the constructive interpretation, the law of excluded middle is not an empty "tautology," but expresses the decidability of proposition $A$. Similarly, a direct proof of an existential proposition $∃xA$ consists of a proof of $A$ for some ["witness"] $a$. Classically, we can prove existence indirectly by assuming that there is no $x$ such that $A$, then deriving a contradiction, and concluding that such an $x$ exists. Here the classical law of double negation is used for deriving $∃xA$ from $¬¬∃xA$.

Thus, it is correct to say that, from a constructivist point of view, tertium non datur [i.e. excluded middle] does not apply in general.

Its application to existence proofs impies that the existence of a witness of $A$ is undecided/unproven until we are not able to "show it".

$\endgroup$
  • $\begingroup$ As I understand it, constructive interpretation of logic requires mathematicians to find a concrete value $x = x_0$ to prove a statement $\exists x A(x)$ whereas classical logic allow us to use this approach and also using a more "indirect" one where we assume that there is no x such A and then derive absurdity. I am curious as to what logic are we using "by default" that is when I am asked to prove that "d is the gcd of a and b" for example. Can I choose whatever "logic system" I want? If a statement is proved using constructive logic is it universally true? 1/2 $\endgroup$ – Erwan Aaron Apr 30 '15 at 11:50
  • $\begingroup$ in both logic systems (constructive and classical). I believe it should be the case but it reminds me of solving quadratic equations. The truth of a statement "a 2nd degree polynomial has roots" can depends of whethere or not we are working $\mathbb{R}$ or $\mathbb{C}$. I wonder if that's also the case in logic. I am also curious as to why the author consider that it is "bad mental hygiene" to use PbC and PoN interchangeably. When does it become a problem? 2/2 $\endgroup$ – Erwan Aaron Apr 30 '15 at 11:56
  • 1
    $\begingroup$ @ErwanAaron - from a "classic" point of view, any intuitionistically valid proof is also classically valid; thus, a constructive existence proof (i.e. proved "by witness") is obviously valid also for a "classically minded" mathematician. Not vice versa ... $\endgroup$ – Mauro ALLEGRANZA Apr 30 '15 at 12:06
  • $\begingroup$ I am not familiar with intuitionistic logic and we are digressing (not sure if allowed by the rules) but I would like to know what is the "point" of intuitionistic logic if it is "weaker" than classical logic. Is there cases where classical logic fails and intuitionistic logic becomes a workaround? Thank you for the valuable input! $\endgroup$ – Erwan Aaron Apr 30 '15 at 13:51
  • 1
    $\begingroup$ @ErwarnAaron You can also take a look at this: mathoverflow.net/questions/25363/… $\endgroup$ – Stefan Perko Apr 30 '15 at 20:02
3
$\begingroup$

The proof of irrationality of $\sqrt{2}$: a number is either rational or not rational. The situation of being rational has to be ruled out so being not rational remains. That is called a proof by negation by the author. A proof by contradiction would end into 'rational and not rational'. A subtle difference. I take the 2nd example of the author and rewrite it a bit: Accept f is not unbounded Then there is a sequence $(x_n)$ in $[0,1]$ such that the sequence $f(x_n)$ is increasing and unbounded (this uses Countable Choice, by the way). By Bolzano-Weierstras there is a convergent subsequence $(y_n)$ of $(x_n)$ such that, as f is continuous, the sequence $f(y_n)$ is convergent and thus bounded. In fact there are two different strategies: using 'tertium non datur' and 'contradiction'. Both are closely linked.

$\endgroup$

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.