Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-22T06:38:55.695Z Has data issue: false hasContentIssue false
  • English
  • Français

A new method for establishing conservativity of classical systems over their intuitionistic version

Published online by Cambridge University Press:  01 August 1999

THIERRY COQUAND  and
MARTIN HOFMANN
THIERRY COQUAND
Affiliation:
Chalmers University, Computer Science, S41296 Göteborg, Sweden. E-mail: [email protected]
MARTIN HOFMANN
Affiliation:
Laboratory for Foundations of Computer Science, The King's Buildings, Mayfield Road, Edinburgh EH9 3JZ. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We use a syntactical notion of Kripke models to obtain interpretations of subsystems of arithmetic in their intuitionistic counterparts. This yields, in particular, a new proof of Buss' result that the Skolem functions of Bounded Arithmetic are polynomial time computable.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 9 , Issue 4 , August 1999 , pp. 323 - 333
Copyright
© 1999 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)