Short Proofs for Slow Consistency


Abstract
Let Con↾x denote the finite consistency statement “there are no proofs of contradiction in T with ≤x symbols.” For a large class of natural theories T, Pudlák has shown that the lengths of the shortest proofs of Con↾n in the theory T itself are bounded by a polynomial in n. At the same time he conjectures that T does not have polynomial proofs of the finite consistency statements Con)↾n. In contrast, we show that Peano arithmetic has polynomial proofs of Con)↾n, where Con∗ is the slow consistency statement for Peano arithmetic, introduced by S.-D. Friedman, Rathjen, and Weiermann. We also obtain a new proof of the result that the usual consistency statement Con is equivalent to ε0 iterations of slow consistency. Our argument is proof-theoretic, whereas previous investigations of slow consistency relied on nonstandard models of arithmetic.
Keywords polynomial proofs   slow consistency  finite consistency statements
Categories (categorize this paper)
DOI 10.1215/00294527-2019-0031
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


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

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Propositional Proof Systems and Fast Consistency Provers.Joost J. Joosten - 2007 - Notre Dame Journal of Formal Logic 48 (3):381-398.
A Note on Iterated Consistency and Infinite Proofs.Anton Freund - 2019 - Archive for Mathematical Logic 58 (3-4):339-346.
On the Philosophical Significance of Consistency Proofs.Michael D. Resnik - 1974 - Journal of Philosophical Logic 3 (1/2):133 - 147.
Propositional Consistency Proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
Consistency Proof Via Pointwise Induction.Toshiyasu Arai - 1998 - Archive for Mathematical Logic 37 (3):149-165.
Consistency, Models, and Soundness.Matthias Schirn - 2010 - Axiomathes 20 (2-3):153-207.

Analytics

Added to PP index
2019-11-29

Total views
6 ( #998,565 of 2,286,122 )

Recent downloads (6 months)
6 ( #195,941 of 2,286,122 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature