In proof theory, a discipline within mathematical logic, double-negation translation, sometimes called negative translation, is a general approach for embedding classical logic into intuitionistic logic. Typically it is done by translating formulas to formulas that are classically equivalent but intuitionistically inequivalent. Particular instances of double-negation translations include Glivenko's translation for propositional logic, and the GödelâÂÂGentzen translation and Kuroda's translation for first-order logic.
The easiest double-negation translation to describe comes from Glivenko's theorem, proved by Valery Glivenko in 1929. It maps each classical formula àto its double negation ììÃÂ. Glivenko's theorem states:
Glivenko's theorem implies the more general statement:
In particular, a set of propositional formulas is intuitionistically consistent if and only if it is classically satisfiable.
The GödelâÂÂGentzen translation (named after Kurt Gödel and Gerhard Gentzen) associates with each formula àin a first-order language another formula ÃÂ<sup>N</sup>, which is defined inductively:
as above, but furthermore
and otherwise
This translation has the property that ÃÂ<sup>N</sup> is classically equivalent to ÃÂ. Troelstra and Van Dalen give a description, due to Leivant, of formulas that do imply their GödelâÂÂGentzen translation in intuitionistic first-order logic also. There, this is not the case for all formulas. (This is related to the fact that propositions with additional double-negations can be stronger than their simpler variant. E.g., ììàâ ø always implies àâ ø, but the schema in the other direction would imply double-negation elimination.)
Due to constructive equivalences, there are several alternative definitions of the translation. For example, a valid De Morgan's law allows one to rewrite a negated disjunction. One possibility can thus succinctly be described as follows: Prefix "ìì" before every atomic formula, but also to every disjunction and existential quantifier,
Another procedure, known as Kuroda's translation, is to construct a translated àby putting "ìì" before the whole formula and after every universal quantifier. This procedure exactly reduces to the propositional translation whenever àis propositional.
Thirdly, one may instead prefix "ìì" before every subformula of ÃÂ, as done by Kolmogorov. Such a translation is the logical counterpart to the call-by-name continuation-passing style translation of functional programming languages along the lines of the CurryâÂÂHoward correspondence between proofs and programs.
The Gödel-Gentzen- and Kuroda-translated formulas of each àare provably equivalent to one another, and this result holds already in minimal propositional logic. And further, in intuitionistic propositional logic, the Kuroda- and Kolmogorov-translated formulas are equivalent also.
The mere propositional mapping of àto ììàdoes not extend to a sound translation of first-order logic, as the so called double negation shift
is not a theorem of intuitionistic predicate logic. So the negations in ÃÂ<sup>N</sup> have to be placed in a more particular way.
Let T<sup>N</sup> consist of the double-negation translations of the formulas in T.
The fundamental soundness theorem states:
The double-negation translation was used by Gödel (1933) to study the relationship between classical and intuitionistic theories of the natural numbers ("arithmetic"). He obtains the following result:
This result shows that if Heyting arithmetic is consistent then so is Peano arithmetic. This is because a contradictory formula is interpreted as , which is still contradictory. Moreover, the proof of the relationship is entirely constructive, giving a way to transform a proof of in Peano arithmetic into a proof of in Heyting arithmetic.
By combining the double-negation translation with the Friedman translation, it is in fact possible to prove that Peano arithmetic is ÃÂ <sup>0</sup><sub style="margin-left:-0.65em">2</sub>-conservative over Heyting arithmetic.