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

Mathematical Logic Quarterly 56 (2):126-130 (2010)
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
Keywords collection principle  Bounded arithmetic  weak pigeonhole principle
Categories (categorize this paper)
DOI 10.1002/malq.200810043
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 35,865
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

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.

Add more references

Citations of this work BETA

No citations found.

Add more citations

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


Added to PP index

Total downloads
13 ( #441,745 of 2,293,801 )

Recent downloads (6 months)
1 ( #410,358 of 2,293,801 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature