Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

On the role of the collection principle for $ \Sigma^0_2$-formulas in second-order reverse mathematics


Authors: C. T. Chong, Steffen Lempp and Yue Yang
Journal: Proc. Amer. Math. Soc. 138 (2010), 1093-1100
MSC (2000): Primary 03F35; Secondary 03H15
Published electronically: October 26, 2009
MathSciNet review: 2566574
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the principle  $ \mathsf{PART}$ from Hirschfeldt and Shore is equivalent to the $ \Sigma^0_2$-Bounding principle  $ B\Sigma^0_2$ over  $ \mathsf{RCA}_0$, answering one of their open questions.

Furthermore, we also fill a gap in a proof of Cholak, Jockusch and Slaman by showing that $ D^2_2$ implies  $ B\Sigma^0_2$ and is thus indeed equivalent to Stable Ramsey's Theorem for Pairs ( $ \mathsf{SRT}^2_2$). This also allows us to conclude that the combinatorial principles $ \mathsf{IPT}^2_2$, $ \mathsf{SPT}^2_2$ and  $ \mathsf{SIPT}^2_2$ defined by Dzhafarov and Hirst all imply  $ B\Sigma^0_2$ and thus that $ \mathsf{SPT}^2_2$ and  $ \mathsf{SIPT}^2_2$ are both equivalent to  $ \mathsf{SRT}^2_2$ as well.

Our proof uses the notion of a bi-tame cut, the existence of which we show to be equivalent, over  $ \mathsf{RCA}_0$, to the failure of  $ B\Sigma^0_2$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03F35, 03H15

Retrieve articles in all journals with MSC (2000): 03F35, 03H15


Additional Information

C. T. Chong
Affiliation: Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543, Singapore
Email: chongct@math.nus.edu.sg

Steffen Lempp
Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706-1388
Email: lempp@math.wisc.edu

Yue Yang
Affiliation: Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543, Singapore
Email: matyangy@math.nus.edu.sg

DOI: http://dx.doi.org/10.1090/S0002-9939-09-10115-6
PII: S 0002-9939(09)10115-6
Keywords: Reverse mathematics, $\Sigma ^0_2$-bounding, linear order, tame cut, bi-tame cut, Ramsey's Theorem
Received by editor(s): June 10, 2009
Received by editor(s) in revised form: June 23, 2009, and July 9, 2009
Published electronically: October 26, 2009
Additional Notes: The main ideas were conceived during the workshop on “Computability, Reverse Mathematics and Combinatorics” at Banff International Research Station in December 2008. The authors wish to thank Banff International Research Station for its hospitality; Richard Shore for useful discussions and for pointing out an error in an earlier version; and Carl Jockusch, Richard Shore, Jeff Hirst and Damir Dzhafarov for mentioning related problems which could be solved by our main result. The research of the first author was supported in part by NUS grant WBS C146-000-025-001. The second author’s research was partially supported by NSF grant DMS–0555381 as well as grant no. 13407 by the John Templeton Foundation entitled “Exploring the Infinite by Finitary Means”. The third author was partially supported by NUS Academic Research grant R 146-000-114-112.
Communicated by: Julia Knight
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.