On the limit existence principles in elementary arithmetic and Σ n 0 -consequences of theories

Annals of Pure and Applied Logic 136 (1-2):56-74 (2005)
  Copy   BIBTEX

Abstract

We study the arithmetical schema asserting that every eventually decreasing elementary recursive function has a limit. Some other related principles are also formulated. We establish their relationship with restricted parameter-free induction schemata. We also prove that the same principle, formulated as an inference rule, provides an axiomatization of the Σ2-consequences of IΣ1.Using these results we show that ILM is the logic of Π1-conservativity of any reasonable extension of parameter-free Π1-induction schema. This result, however, cannot be much improved: by adapting a theorem of D. Zambella and G. Mints we show that the logic of Π1-conservativity of primitive recursive arithmetic properly extends ILM.In the third part of the paper we give an ordinal classification of -consequences of the standard fragments of Peano arithmetic in terms of reflection principles. This is interesting in view of the general program of ordinal analysis of theories, which in the most standard cases classifies Π-classes of sentences

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 98,418

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

Proof-theoretic analysis by iterated reflection.Lev D. Beklemishev - 2003 - Archive for Mathematical Logic 42 (6):515-552.
On the induction schema for decidable predicates.Lev D. Beklemishev - 2003 - Journal of Symbolic Logic 68 (1):17-34.
Fragments of Heyting arithmetic.Wolfgang Burr - 2000 - Journal of Symbolic Logic 65 (3):1223-1240.
A note on Σ 1 -maximal models.A. Cordón—Franco & F. F. Lara—Martín - 2007 - Journal of Symbolic Logic 72 (3):1072-1078.
A Simple Proof of Parsons' Theorem.Fernando Ferreira - 2005 - Notre Dame Journal of Formal Logic 46 (1):83-91.
The logic of π1-conservativity.Petr Hajek & Franco Montagna - 1990 - Archive for Mathematical Logic 30 (2):113-123.

Analytics

Added to PP
2014-01-16

Downloads
31 (#595,253)

6 months
8 (#461,911)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Citations of this work

Axiomatization of provable n-provability.Evgeny Kolmakov & Lev Beklemishev - 2019 - Journal of Symbolic Logic 84 (2):849-869.
The Arithmetics of a Theory.Albert Visser - 2015 - Notre Dame Journal of Formal Logic 56 (1):81-119.
Transductions in arithmetic.Albert Visser - 2016 - Annals of Pure and Applied Logic 167 (3):211-234.
Marginalia on a theorem of Woodin.Rasmus Blanck & Ali Enayat - 2017 - Journal of Symbolic Logic 82 (1):359-374.

View all 7 citations / Add more citations

References found in this work

Systems of logic based on ordinals..Alan Turing - 1939 - London,: Printed by C.F. Hodgson & son.
Transfinite recursive progressions of axiomatic theories.Solomon Feferman - 1962 - Journal of Symbolic Logic 27 (3):259-316.
The interpretability logic of peano arithmetic.Alessandro Berarducci - 1990 - Journal of Symbolic Logic 55 (3):1059-1089.
Proof-theoretic analysis by iterated reflection.Lev D. Beklemishev - 2003 - Archive for Mathematical Logic 42 (6):515-552.
On parameter free induction schemas.R. Kaye, J. Paris & C. Dimitracopoulos - 1988 - Journal of Symbolic Logic 53 (4):1082-1097.

View all 10 references / Add more references