﻿ Gödel–Gentzen negative translation : definition of Gödel–Gentzen negative translation and synonyms of Gödel–Gentzen negative translation (English)
 »
Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese
Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese

definition - Gödel–Gentzen negative translation

definition of Wikipedia

Gödel–Gentzen negative translation

In proof theory, the Gödel–Gentzen negative translation is a method for embedding classical first-order logic into intuitionistic first-order logic. It is one of a number of double-negation translations that are of importance to the metatheory of intuitionistic logic. It is named after logicians Kurt Gödel and Gerhard Gentzen.

Propositional logic

The easiest double-negation translation to describe comes from Glivenko's theorem. It maps each classical formula φ to its double negation ¬¬φ.

Glivenko's theorem states:

If T is a set of propositional formulas and φ a propositional formula, then T proves φ using classical logic if and only if T proves ¬¬φ using intuitionistic logic.

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

First-order logic

The translation 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

Notice 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.

Note that φ need not imply its negative translation φN in intuitionistic first-order logic. Troelsta and Van Dalen[2] give a description (due to Leivant) of formulas which 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 (described by Kuroda) 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 φ.

Results

The double-negation translation was used by Gödel (1933) to study the relationship between classical and intutionistic 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.

Notes

1. ^ Avigad and Feferman 1998, p. 342; Buss 1998 p. 66
2. ^ Troelsta, 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.
• K. Gödel (1933), "Zur intuitionistischen Arithmetik und Zahlentheorie", Ergebnisse eines mathematische 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 teritium 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. Troelsta (1977), "Aspects of Constructive Mathematics", Handbook of Mathematical Logic", J. Barwise, ed., North-Holland. ISBN 0-7204-2285-X
• A.S. Troelsta and D. van Dalen (1988), Constructivism in Mathematics. An Introduction, volumes 121, 123 of Studies in Logic and the Foundations of Mathematics, North–Holland.

Gödel–Gentzen negative translation

(Redirected from Gödel-Gentzen negative translation)

In proof theory, the Gödel–Gentzen negative translation is a method for embedding classical first-order logic into intuitionistic first-order logic. It is one of a number of double-negation translations that are of importance to the metatheory of intuitionistic logic. It is named after logicians Kurt Gödel and Gerhard Gentzen.

Propositional logic

The easiest double-negation translation to describe comes from Glivenko's theorem. It maps each classical formula φ to its double negation ¬¬φ.

Glivenko's theorem states:

If T is a set of propositional formulas and φ a propositional formula, then T proves φ using classical logic if and only if T proves ¬¬φ using intuitionistic logic.

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

First-order logic

The translation 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

Notice 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.

Note that φ need not imply its negative translation φN in intuitionistic first-order logic. Troelsta and Van Dalen[2] give a description (due to Leivant) of formulas which 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 (described by Kuroda) 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 φ.

Results

The double-negation translation was used by Gödel (1933) to study the relationship between classical and intutionistic 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.

Notes

1. ^ Avigad and Feferman 1998, p. 342; Buss 1998 p. 66
2. ^ Troelsta, 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.
• K. Gödel (1933), "Zur intuitionistischen Arithmetik und Zahlentheorie", Ergebnisse eines mathematische 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 teritium 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. Troelsta (1977), "Aspects of Constructive Mathematics", Handbook of Mathematical Logic", J. Barwise, ed., North-Holland. ISBN 0-7204-2285-X
• A.S. Troelsta and D. van Dalen (1988), Constructivism in Mathematics. An Introduction, volumes 121, 123 of Studies in Logic and the Foundations of Mathematics, North–Holland.

Gödel–Gentzen negative translation

(Redirected from Godel-Gentzen negative translation)

In proof theory, the Gödel–Gentzen negative translation is a method for embedding classical first-order logic into intuitionistic first-order logic. It is one of a number of double-negation translations that are of importance to the metatheory of intuitionistic logic. It is named after logicians Kurt Gödel and Gerhard Gentzen.

Propositional logic

The easiest double-negation translation to describe comes from Glivenko's theorem. It maps each classical formula φ to its double negation ¬¬φ.

Glivenko's theorem states:

If T is a set of propositional formulas and φ a propositional formula, then T proves φ using classical logic if and only if T proves ¬¬φ using intuitionistic logic.

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

First-order logic

The translation 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

Notice 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.

Note that φ need not imply its negative translation φN in intuitionistic first-order logic. Troelsta and Van Dalen[2] give a description (due to Leivant) of formulas which 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 (described by Kuroda) 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 φ.

Results

The double-negation translation was used by Gödel (1933) to study the relationship between classical and intutionistic 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.

Notes

1. ^ Avigad and Feferman 1998, p. 342; Buss 1998 p. 66
2. ^ Troelsta, 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.
• K. Gödel (1933), "Zur intuitionistischen Arithmetik und Zahlentheorie", Ergebnisse eines mathematische 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 teritium 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. Troelsta (1977), "Aspects of Constructive Mathematics", Handbook of Mathematical Logic", J. Barwise, ed., North-Holland. ISBN 0-7204-2285-X
• A.S. Troelsta and D. van Dalen (1988), Constructivism in Mathematics. An Introduction, volumes 121, 123 of Studies in Logic and the Foundations of Mathematics, North–Holland.

sensagent's content

• definitions
• synonyms
• antonyms
• encyclopedia

Dictionary and translator for handheld

New : sensagent is now available on your handheld

sensagent's office

Shortkey or widget. Free.

Windows Shortkey: . Free.

Vista Widget : . Free.

Webmaster Solution

Alexandria

A windows (pop-into) of information (full-content of Sensagent) triggered by double-clicking any word on your webpage. Give contextual explanation and translation from your sites !

Try here  or   get the code

SensagentBox

With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.

WordGame

The English word games are:
○   Anagrams
○   Wildcard, crossword
○   Lettris
○   Boggle.

Lettris

Lettris is a curious tetris-clone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.

boggle

Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !

English dictionary
Main references

Most English definitions are provided by WordNet .
English thesaurus is mainly derived from The Integral Dictionary (TID).
English Encyclopedia is licensed by Wikipedia (GNU).

The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.
The web service Alexandria is granted from Memodata for the Ebay search.
The SensagentBox are offered by sensAgent.

Translation

Change the target language to find translations.
Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.

last searches on the dictionary :

2618 online visitors

computed in 0.047s

I would like to report:
section :
a spelling or a grammatical mistake
an offensive content(racist, pornographic, injurious, etc.)