A note on $\Delta _1$ induction and $\Sigma _1$ collection

Tom 186 / 2005

Neil Thapen Fundamenta Mathematicae 186 (2005), 79-84 MSC: 03F30, 03H15. DOI: 10.4064/fm186-1-6


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$”.


  • Neil ThapenSt Hilda's College
    University of Oxford
    Oxford OX1 4DY, UK

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek