Binary models generated by their tally part

Archive for Mathematical Logic 33 (4):283-289 (1994)
  Copy   BIBTEX

Abstract

We introduce a class of models of the bounded arithmetic theoryPV n . These models, which are generated by their tally part, have a curious feature: they have end-extensions or satisfyB∑ n b only in case they are closed under exponentiation. As an application, we show that if then the polynomial hierarchy does not collapse

Categories

Keywords

Reprint years

DOI

10.1007/bf01270627

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,891

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

On End‐Extensions of Models of ¬exp.Fernando Ferreira - 1996 - Mathematical Logic Quarterly 42 (1):1-18.
A note on a theorem of Kanovei.Roman Kossak - 2004 - Archive for Mathematical Logic 43 (4):565-569.
Subsets of models of arithmetic.Roman Kossak & Jeffrey B. Paris - 1992 - Archive for Mathematical Logic 32 (1):65-73.
A note on end extensions.Ch Cornaros & C. Dimitracopoulos - 2000 - Archive for Mathematical Logic 39 (6):459-463.
End extensions of models of linearly bounded arithmetic.Domenico Zambella - 1997 - Annals of Pure and Applied Logic 88 (2-3):263-277.
Duality and canonical extensions of bounded distributive lattices with operators, and applications to the semantics of non-classical logics I.Viorica Sofronie-Stokkermans - 2000 - Studia Logica 64 (1):93-132.
Partial collapses of the complexity hierarchy in models for fragments of bounded arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2007 - Annals of Pure and Applied Logic 145 (1):91-95.
The algebraic structure of the isomorphic types of tally, polynomial time computable sets.Yongge Wang - 2002 - Archive for Mathematical Logic 41 (3):215-244.
Short Proofs for Slow Consistency.Anton Freund & Fedor Pakhomov - 2020 - Notre Dame Journal of Formal Logic 61 (1):31-49.
The theories of Baldwin–Shi hypergraphs and their atomic models.Danul K. Gunatilleka - 2021 - Archive for Mathematical Logic 60 (7):879-908.

Analytics

Added to PP
2013-11-23

Downloads
49 (#316,148)

6 months
9 (#437,668)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

On End‐Extensions of Models of ¬exp.Fernando Ferreira - 1996 - Mathematical Logic Quarterly 42 (1):1-18.

Add more citations

References found in this work

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.

Add more references