Premium
A note on the Σ 1 collection scheme and fragments of bounded arithmetic
Author(s) -
Adamowicz Zofia,
Kołodziejczyk Leszek Aleksander
Publication year - 2010
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200810043
Subject(s) - pigeonhole principle , mathematics , scheme (mathematics) , arithmetic , bounded function , arithmetic function , discrete mathematics , combinatorics , mathematical analysis
We show that for each n ≥ 1, if T 2 n does not prove the weak pigeonhole principle for Σ b n functions, then the collection scheme B Σ 1 is not finitely axiomatizable over T 2 n . The same result holds with S n 2 in place of T 2 n (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom