Asymmetric Interpretations for Bounded Theories

Mathematical Logic Quarterly 42 (1):270-288 (1996)
  Copy   BIBTEX

Abstract

We apply the method of asymmetric interpretation to the basic fragment of bounded arithmetic, endowed with a weak collection schema, and to a system of “feasible analysis”, introduced by Ferreira and based on weak König's lemma, recursive comprehension and NP-notation induction. As a byproduct, we obtain two conservation results

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,139

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

A feasible theory for analysis.Fernando Ferreira - 1994 - Journal of Symbolic Logic 59 (3):1001-1011.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Measure theory and weak König's lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.
Strict $${\Pi^1_1}$$ -reflection in bounded arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.
Dynamic ordinal analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.

Analytics

Added to PP
2013-12-01

Downloads
10 (#1,097,540)

6 months
2 (#1,015,942)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Andrea Cantini
Università degli Studi di Firenze

Citations of this work

Groundwork for weak analysis.António M. Fernandes & Fernando Ferreira - 2002 - Journal of Symbolic Logic 67 (2):557-578.
Interpretability in Robinson's Q.Fernando Ferreira & Gilda Ferreira - 2013 - Bulletin of Symbolic Logic 19 (3):289-317.
Bounded functional interpretation and feasible analysis.Fernando Ferreira & Paulo Oliva - 2007 - Annals of Pure and Applied Logic 145 (2):115-129.
Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Strict $${\Pi^1_1}$$ -reflection in bounded arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.

View all 7 citations / Add more citations

References found in this work

Admissible Sets and Structures.Jon Barwise - 1978 - Studia Logica 37 (3):297-299.

Add more references