A note on the E1 collection scheme and fragments of bounded arithmetic

&
Mathematical Logic Quarterly 56 (2):126-130 (2010)
  Copy   BIBTEX

Abstract

We show that for each n ≥ 1, if T2n does not prove the weak pigeonhole principle for Σbn functions, then the collection scheme B Σ1 is not finitely axiomatizable over T2n. The same result holds with Sn2 in place of T 2n

Categories

Keywords

Reprint years

DOI

10.1002/malq.200810043

Links

PhilArchive



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

External links

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

Through your library

My notes

Similar books and articles

Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
The weak pigeonhole principle for function classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Abelian groups and quadratic residues in weak arithmetic.Emil Jeřábek - 2010 - Mathematical Logic Quarterly 56 (3):262-278.
On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories.Leszek Aleksander Kołodziejczyk - 2006 - Journal of Symbolic Logic 71 (2):624 - 638.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Witnessing functions in bounded arithmetic and search problems.Mario Chiari & Jan Krajíček - 1998 - Journal of Symbolic Logic 63 (3):1095-1115.
Strict $${\Pi^1_1}$$ -reflection in bounded arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.
Two General Results on Intuitionistic Bounded Theories.Fernando Ferreira - 1999 - Mathematical Logic Quarterly 45 (3):399-407.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
A feasible theory for analysis.Fernando Ferreira - 1994 - Journal of Symbolic Logic 59 (3):1001-1011.
An Independence Result on Weak Second Order Bounded Arithmetic.Satoru Kuroda - 2001 - Mathematical Logic Quarterly 47 (2):183-186.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
A Note on Conservativity Relations among Bounded Arithmetic Theories.Russell Impagliazzo & Jan Krajíček - 2002 - Mathematical Logic Quarterly 48 (3):375-377.

Analytics

Added to PP
2013-12-01

Downloads
40 (#396,692)

6 months
3 (#965,065)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
A model-theoretic characterization of the weak pigeonhole principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.

View all 7 references / Add more references