Partially definable forcing and bounded arithmetic

&
Archive for Mathematical Logic 54 (1):1-33 (2015)
  Copy   BIBTEX

Abstract

We describe a method of forcing against weak theories of arithmetic and its applications in propositional proof complexity.

Categories

Keywords

Reprint years

DOI

10.1007/s00153-014-0398-3

Links

PhilArchive



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

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

Generalized quantifier and a bounded arithmetic theory for LOGCFL.Satoru Kuroda - 2007 - Archive for Mathematical Logic 46 (5-6):489-516.
A note on sharply bounded arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.
Models of replacement schemes.Eugenio Chinchilla - 2005 - Archive for Mathematical Logic 44 (7):851-867.
Radin forcing and its iterations.John Krueger - 2007 - Archive for Mathematical Logic 46 (3-4):223-252.
Erratum: “Forcing and antifoundation”. [REVIEW]Athanassios Tzouvaras - 2005 - Archive for Mathematical Logic 44 (5):663-663.
A saturation property of structures obtained by forcing with a compact family of random variables.Jan Krajíček - 2013 - Archive for Mathematical Logic 52 (1-2):19-28.
Overspill and fragments of arithmetic.C. Dimitracopoulos - 1989 - Archive for Mathematical Logic 28 (3):173-179.
Provably recursive functions of constructive and relatively constructive theories.Morteza Moniri - 2010 - Archive for Mathematical Logic 49 (3):291-300.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Weak theories of linear algebra.Neil Thapen & Michael Soltys - 2005 - Archive for Mathematical Logic 44 (2):195-208.

Analytics

Added to PP
2014-08-29

Downloads
12 (#1,115,280)

6 months
34 (#104,348)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

[Omnibus Review].Kenneth Kunen - 1969 - Journal of Symbolic Logic 34 (3):515-516.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.

View all 22 references / Add more references