Annals of Pure and Applied Logic 136 (3):247-266 (2005)

Abstract
We look for a converse to a result from [N. Thapen, A model-theoretic characterization of the weak pigeonhole principle, Annals of Pure and Applied Logic 118 175–195] that if the weak pigeonhole principle fails in a model K of bounded arithmetic, then there is an end-extension of K interpretable inside K. We show that if a model J of an induction-free theory of arithmetic is interpretable inside K, then either J is isomorphic to an initial segment of K , or K is isomorphic to an initial segment of J and in this case the weak pigeonhole principle fails in K. This result is formulated in terms of a theory of bounded arithmetic with a greatest element. We go on to consider structures defined by oracles, and use the probabilistic witnessing theorem for to give a general criterion for what can be proved about these using the weak pigeonhole principle. We also show that the injective WPHP is not provable in this theory in the relativized case
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2005.04.005
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 64,132
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

Countable Models of Set Theories.Harvey Friedman - 1973 - In A. R. D. Mathias & H. Rogers (eds.), Cambridge Summer School in Mathematical Logic. New York: Springer Verlag. pp. 539--573.
Dual Weak Pigeonhole Principle, Boolean Complexity, and Derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
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

Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Feasibly Constructive Proofs of Succinct Weak Circuit Lower Bounds.Moritz Müller & Ján Pich - 2020 - Annals of Pure and Applied Logic 171 (2):102735.

Add more citations

Similar books and articles

On Interpretations of Bounded Arithmetic and Bounded Set Theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Regularity in Models of Arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Forcing in Finite Structures.Domenico Zambella - 1997 - Mathematical Logic Quarterly 43 (3):401-412.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Infinite Substructure Lattices of Models of Peano Arithmetic.James H. Schmerl - 2010 - Journal of Symbolic Logic 75 (4):1366-1382.
Real Closures of Models of Weak Arithmetic.Emil Jeřábek & Leszek Aleksander Kołodziejczyk - 2013 - Archive for Mathematical Logic 52 (1-2):143-157.
On End‐Extensions of Models of ¬Exp.Fernando Ferreira - 1996 - Mathematical Logic Quarterly 42 (1):1-18.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Algebraic Methods and Bounded Formulas.Domenico Zambella - 1997 - Notre Dame Journal of Formal Logic 38 (1):37-48.

Analytics

Added to PP index
2014-01-16

Total views
10 ( #877,595 of 2,454,810 )

Recent downloads (6 months)
1 ( #449,241 of 2,454,810 )

How can I increase my downloads?

Downloads

My notes