Semi-honest subrecursive degrees and the collection rule in arithmetic

By a result of L.D. Beklemishev, the hierarchy of nested applications of the Σ 1 -collection rule over any Π 2 -axiomatizable base theory extending Elementary Arithmetic collapses to its first level. We prove that this result cannot in general be extended to base theories of arbitrary quantifier com...

Full description

Saved in:
Bibliographic Details
Published in:Archive for mathematical logic 2024-02, Vol.63 (1-2), p.163-180
Main Authors: Cordón-Franco, Andrés, Lara-Martín, F. Félix
Format: Article
Language:English
Subjects:
Algebra
Arithmetic
Collection
Mathematical Logic and Foundations
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:By a result of L.D. Beklemishev, the hierarchy of nested applications of the Σ 1 -collection rule over any Π 2 -axiomatizable base theory extending Elementary Arithmetic collapses to its first level. We prove that this result cannot in general be extended to base theories of arbitrary quantifier complexity. In fact, given any recursively enumerable set of true Π 2 -sentences, S , we construct a sound ( Σ 2 ∨ Π 2 ) -axiomatized theory T extending S such that the hierarchy of nested applications of the Σ 1 -collection rule over T is proper. Our construction uses some results on subrecursive degree theory obtained by L. Kristiansen.
ISSN:0933-5846
1432-0665
DOI:10.1007/s00153-023-00889-z