Double-negation translation

From Wikipedia, the free encyclopedia

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 by translating formulas to formulas which are classically equivalent but intuitionistically inequivalent. Particular instances of double-negation translation include Glivenko's translation for propositional logic, and the Gödel–Gentzen translation and Kuroda's translation for first-order logic.

Propositional 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:

If φ is a propositional formula, then φ is a classical tautology if and only if ¬¬φ is an intuitionistic tautology.

Glivenko's theorem implies the more general statement:

If T is a set of propositional formulas, T* a set consisting of the double negated formulas of T, and φ a propositional formula, then T ⊢ φ in classical logic if and only if T* ⊢ ¬¬φ in intuitionistic logic.

In particular, a set of propositional formulas is intuitionistically consistent if and only if it is classically satisfiable.

First-order logic

The Gödel–Gentzen translation (named after Kurt Gödel and Gerhard Gentzen) associates with each formula φ in a first-order language another formula φN, which is defined inductively:

  • If φ is atomic, then φN is ¬¬φ
  • (φ ∧ θ)N is φN ∧ θN
  • (φ ∨ θ)N is ¬(¬φN ∧ ¬θN)
  • (φ → θ)N is φN → θN
  • (¬φ)N is ¬φN
  • (∀x φ)N is ∀x φN
  • (∃x φ)N is ¬∀x ¬φN

This translation has the property that φN is classically equivalent to φ. The fundamental soundness theorem states:[1]

If T is a set of axioms and φ a formula, then T proves φ using classical logic if and only if TN proves φN using intuitionistic logic.

Here TN consists of the double-negation translations of the formulas in T.

A sentence φ may not imply its negative translation φN in intuitionistic first-order logic. Troelstra and Van Dalen[2] give a description (due to Leivant) of formulas that do imply their Gödel–Gentzen translation.

Variants

There are several alternative definitions of the negative translation. They are all provably equivalent in intuitionistic logic, but may be easier to apply in particular contexts.

One possibility is to change the clauses for disjunction and existential quantifier to

  • (φ ∨ θ)N is ¬¬(φN ∨ θN)
  • (∃x φ)N is ¬¬∃x φN

Then the translation can be succinctly described as: prefix ¬¬ to every atomic formula, disjunction, and existential quantifier.

Another possibility (known as Kuroda's translation) is to construct φN from φ by putting ¬¬ before the whole formula and after every universal quantifier. Notice that this reduces to the simple ¬¬φ translation if φ is propositional.

It is also possible to define φN by prefixing ¬¬ 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.

Results

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:

If a formula φ is provable from the axioms of Peano arithmetic then φN is provable from the axioms of intuitionistic Heyting arithmetic.

This result shows that if Heyting arithmetic is consistent then so is Peano arithmetic. This is because a contradictory formula θ ∧ ¬θ is interpreted as θN ∧ ¬θN, 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 θN ∧ ¬θN in Heyting arithmetic. (By combining the double-negation translation with the Friedman translation, it is in fact possible to prove that Peano arithmetic is Π02-conservative over Heyting arithmetic.)

The propositional mapping of φ to ¬¬φ does not extend to a sound translation of first-order logic, because x ¬¬φ(x) → ¬¬∀x φ(x) is not a theorem of intuitionistic predicate logic. This explains why φN has to be defined in a more complicated way in the first-order case.

See also

Notes

  1. ^ Avigad and Feferman 1998, p. 342; Buss 1998 p. 66
  2. ^ Troelstra, van Dalen 1988, Ch. 2, Sec. 3

References

  • J. Avigad and S. Feferman (1998), "Gödel's Functional ("Dialectica") Interpretation", Handbook of Proof Theory'', S. Buss, ed., Elsevier. ISBN 0-444-89840-9
  • S. Buss (1998), "Introduction to Proof Theory", Handbook of Proof Theory, S. Buss, ed., Elsevier. ISBN 0-444-89840-9
  • G. Gentzen (1936), "Die Widerspruchfreiheit der reinen Zahlentheorie", Mathematische Annalen, v. 112, pp. 493–565 (German). Reprinted in English translation as "The consistency of arithmetic" in The collected papers of Gerhard Gentzen, M. E. Szabo, ed.
  • V. Glivenko (1929), Sur quelques points de la logique de M. Brouwer, Bull. Soc. Math. Belg. 15, 183-188
  • K. Gödel (1933), "Zur intuitionistischen Arithmetik und Zahlentheorie", Ergebnisse eines mathematischen Kolloquiums, v. 4, pp. 34–38 (German). Reprinted in English translation as "On intuitionistic arithmetic and number theory" in The Undecidable, M. Davis, ed., pp. 75–81.
  • A. N. Kolmogorov (1925), "O principe tertium non datur" (Russian). Reprinted in English translation as "On the principle of the excluded middle" in From Frege to Gödel, van Heijenoort, ed., pp. 414–447.
  • A. S. Troelstra (1977), "Aspects of Constructive Mathematics", Handbook of Mathematical Logic", J. Barwise, ed., North-Holland. ISBN 0-7204-2285-X
  • A. S. Troelstra and D. van Dalen (1988), Constructivism in Mathematics. An Introduction, volumes 121, 123 of Studies in Logic and the Foundations of Mathematics, North–Holland.

External links

  • "Intuitionistic logic", Stanford Encyclopedia of Philosophy.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Double-negation_translation&oldid=808493471"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Double-negation_translation
This page is based on the copyrighted Wikipedia article "Double-negation translation"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA