Preservation theorems for bounded formulas

Archive for Mathematical Logic 46 (1):9-14 (2007)
  Copy   BIBTEX

Abstract

In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions for a theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV1. We use the mentioned results to obtain some independence results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction on strict $\Pi_2^{b}$ formulas proves decidability of $\Sigma_1^b$ formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves ${\rm LMIN}(\Sigma_{1}^{b})$ , then P=NP

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,635

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

Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Quantifier Elimination for Neocompact Sets.H. Jerome Keisler - 1998 - Journal of Symbolic Logic 63 (4):1442-1472.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
On Two Questions About Feasibly Constructive Arithmetic.Morteza Moniri - 2003 - Mathematical Logic Quarterly 49 (4):425.
The Strength of Sharply Bounded Induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
Admissible Closures of Polynomial Time Computable Arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5-6):643-660.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Two General Results on Intuitionistic Bounded Theories.Fernando Ferreira - 1999 - Mathematical Logic Quarterly 45 (3):399-407.
Algebraic Methods and Bounded Formulas.Domenico Zambella - 1997 - Notre Dame Journal of Formal Logic 38 (1):37-48.

Analytics

Added to PP
2013-11-23

Downloads
38 (#305,067)

6 months
1 (#419,510)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Add more citations

References found in this work

A Shorter Model Theory.Wilfrid Hodges - 1997 - Studia Logica 64 (1):133-134.
Bounded Arithmetic and the Polynomial Hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
Interpreting Classical Theories in Constructive Ones.Jeremy Avigad - 2000 - Journal of Symbolic Logic 65 (4):1785-1812.

View all 10 references / Add more references