On the limit existence principles in elementary arithmetic and ∑n0-consequences of theories

Lev D. Beklemishev*, Albert Visser

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

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 ∑n0-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 (usually Π11 or Π20).

Original languageEnglish
Pages (from-to)56-74
Number of pages19
JournalAnnals of Pure and Applied Logic
Volume136
Issue number1-2
DOIs
Publication statusPublished - Oct 2005

Keywords

  • Conservativity
  • Elementary arithmetic
  • Inference rule
  • Interpretability logic
  • Ordinal analysis
  • Parameter-free induction
  • Reflection principles

Fingerprint

Dive into the research topics of 'On the limit existence principles in elementary arithmetic and ∑n0-consequences of theories'. Together they form a unique fingerprint.

Cite this