A note on the Sigma(1) collection scheme and fragments of bounded arithmetic

作者：Adamowicz Zofia; Kolodziejczyk Leszek Aleksander^*

来源：Mathematical Logic Quarterly, 2010, 56(2): 126-130.

DOI：10.1002/malq.200810043

• Bounded arithmetic
• collection principle
• weak pigeonhole principle

We show that for each n >= 1, if T-2(n) does not prove the weak pigeonhole principle for Sigma(b)(n) functions, then the collection scheme B Sigma(1) is not finitely axiomatizable over T-2(n). The same result holds with S-2(n) in place of T-2(n).

• 出版日期2010-4