A model-theoretic characterization of the weak pigeonhole principle

Annals of Pure and Applied Logic 118 (1-2):175-195 (2002)
  Copy   BIBTEX

Abstract

We bring together some facts about the weak pigeonhole principle from bounded arithmetic, complexity theory, cryptography and abstract model theory. We characterize the models of arithmetic in which WPHP fails as those which are determined by an initial segment and prove a conditional separation result in bounded arithmetic, that PV + lies strictly between PV and S21 in strength, assuming that the cryptosystem RSA is secure

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,100

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

The weak pigeonhole principle for function classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
Pigeonhole and Choice Principles.Wolfgang Degen - 2000 - Mathematical Logic Quarterly 46 (3):313-334.
Isols and the pigeonhole principle.J. C. E. Dekker & E. Ellentuck - 1989 - Journal of Symbolic Logic 54 (3):833-846.
Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
On the Indecomposability of $\omega^{n}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.

Analytics

Added to PP
2014-01-16

Downloads
17 (#871,044)

6 months
5 (#644,465)

Historical graph of downloads
How can I increase my downloads?

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.
Classification theory over a predicate. I.Anand Pillay & Saharon Shelah - 1985 - Notre Dame Journal of Formal Logic 26 (4):361-376.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.

View all 6 references / Add more references