Gödel-Gentzen negative translation (${\phi }^N$)

For an atomic formula $P$ (including logical equality), put $P^N=\neg \neg P$, and put ${\perp }^N=\perp$. Preserve logical conjunction, logical implication and universal quantification recursively, while settingLogical negation is logical implication to logical falsity, so $(\neg A{)}^N=\neg A^N$. The displayed logical disjunction and existence clauses are intuitionistically equivalent to the usual negative forms $\neg (\neg A^N\wedge \neg B^N)$ and $\neg \forall x\neg A^N$. Every translated first-order formula is stable by stability of a formula under double negation. In classical logic the translation is equivalent to the original first-order formula by mathematical induction and double-negation elimination.

The Gödel-Gentzen negative translation transforms $\Gamma {⊢}_{\mathrm{CL}}A$ into ${\Gamma }^N{⊢}_{\mathrm{IL}}{A}^N$. Induct on a natural deduction derivation. The translated logical conjunction, logical implication and universal rules are ordinary intuitionistic rules. Logical disjunction and existential introduction add double logical negation; their elimination rules first derive the double logical negation of the stable translated conclusion, then use its stability. Classical double-negation elimination translates precisely to stability. If logical equality atoms are double-negated, transport a stable translated conclusion through a logical equality by contradiction and then remove the resulting double logical negation. Original nonlogical axioms must also be translated; the result does not say arbitrary untranslated classical first-order theories are intuitionistically valid.