A note on $\Delta _1$ induction and $\Sigma _1$ collection
Volume 186 / 2005
Fundamenta Mathematicae 186 (2005), 79-84
MSC: 03F30, 03H15.
DOI: 10.4064/fm186-1-6
Abstract
Slaman recently proved that $\Sigma _n$ collection is provable from $\Delta _n$ induction plus exponentiation, partially answering a question of Paris. We give a new version of this proof for the case $n=1$, which only requires the following very weak form of exponentiation: “$x^y$ exists for some $y$ sufficiently large that $x$ is smaller than some primitive recursive function of $y$”.
