Propositional proof systems, the consistency of first order theories and the complexity of computations

Journal of Symbolic Logic 54 (3):1063-1079 (1989)
  Copy   BIBTEX

Abstract

We consider the problem about the length of proofs of the sentences $\operatorname{Con}_S(\underline{n})$ saying that there is no proof of contradiction in S whose length is ≤ n. We show the relation of this problem to some problems about propositional proof systems

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,168

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

Implicit Proofs.Jan Krajíček - 2004 - Journal of Symbolic Logic 69 (2):387 - 397.
Socratic proofs.Andrzej Wiśniewski - 2004 - Journal of Philosophical Logic 33 (3):299-326.
Propositional Proof Systems and Fast Consistency Provers.Joost J. Joosten - 2007 - Notre Dame Journal of Formal Logic 48 (3):381-398.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.

Analytics

Added to PP
2009-01-28

Downloads
23 (#501,637)

6 months
1 (#448,551)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Incompleteness in the finite domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.

View all 17 citations / Add more citations

References found in this work

On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.

Add more references