Editing Proof by contradiction (section)

== Proof by contradiction in intuitionistic logic ==

In [[intuitionistic logic]] proof by contradiction is not generally valid, although some particular instances can be derived. In contrast, proof of negation and principle of noncontradiction are both intuitionistically valid.<ref>{{Citation |last=Moschovakis |first=Joan |title=Intuitionistic Logic |date=2024 |work=The Stanford Encyclopedia of Philosophy |editor-last=Zalta |editor-first=Edward N. |url=https://plato.stanford.edu/archives/sum2024/entries/logic-intuitionistic/ |access-date=2025-04-05 |edition=Summer 2024 |publisher=Metaphysics Research Lab, Stanford University |editor2-last=Nodelman |editor2-first=Uri}}</ref>

[[Brouwer–Heyting–Kolmogorov interpretation]] of proof by contradiction gives the following intuitionistic validity condition: {{clarify span|if there is no method for establishing that a proposition is false, then there is a method for establishing that the proposition is true.|reason=This condition is particularly dubious, as discussed in the next paragraph. Moreover, I couldn't find the condition in the 'Brouwer–Heyting–Kolmogorov interpretation' article.|date=May 2024}}

If we take "method" to mean [[algorithm]], then the condition is not acceptable, as it would allow us to solve the [[Halting problem]]. To see how, consider the statement ''H(M)'' stating "[[Turing machine]] ''M'' halts or does not halt". Its negation ''¬H(M)'' states that "''M'' neither halts nor does not halt", which is false by the [[law of noncontradiction]] (which is intuitionistically valid). If proof by contradiction were intuitionistically valid, we would obtain an algorithm for deciding whether an arbitrary Turing machine ''M'' halts, thereby violating the (intuitionistically valid) proof of non-solvability of the [[Halting problem]].

A proposition ''P'' which satisfies <math>\lnot\lnot P \Rightarrow P</math> is known as a ''¬¬-stable proposition''. Thus in intuitionistic logic proof by contradiction is not universally valid, but can only be applied to the ¬¬-stable propositions. An instance of such a proposition is a decidable one, i.e., satisfying <math>P \lor \lnot P</math>. Indeed, the above proof that the law of excluded middle implies proof by contradiction can be repurposed to show that a decidable proposition is ¬¬-stable. A typical  example of a decidable proposition is a statement that can be checked by direct computation, such as "<math>n</math> is prime" or "<math>a</math> divides <math>b</math>".