On the role of the collection principle for -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 Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the principle from Hirschfeldt and Shore is equivalent to the -Bounding principle over , answering one of their open questions.

Furthermore, we also fill a gap in a proof of Cholak, Jockusch and Slaman by showing that implies and is thus indeed equivalent to Stable Ramsey's Theorem for Pairs ( ). This also allows us to conclude that the combinatorial principles , and defined by Dzhafarov and Hirst all imply and thus that and are both equivalent to as well.

Our proof uses the notion of a bi-tame cut, the existence of which we show to be equivalent, over , to the failure of .

**1.**Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman,*On the strength of Ramsey’s theorem for pairs*, J. Symbolic Logic**66**(2001), no. 1, 1–55. MR**1825173**, 10.2307/2694910**2.**C. T. Chong,*An 𝛼-finite injury method of the unbounded type*, J. Symbolic Logic**41**(1976), no. 1, 1–17. MR**0476456****3.**C. T. Chong and Yue Yang,*Σ₂ induction and infinite injury priority arguments. II. Tame Σ₂ coding and the jump operator*, Ann. Pure Appl. Logic**87**(1997), no. 2, 103–116. Logic Colloquium ’95 Haifa. MR**1490049**, 10.1016/0168-0072(96)00028-0**4.**P. Erdös and R. Rado,*A partition calculus in set theory*, Bull. Amer. Math. Soc.**62**(1956), 427–489. MR**0081864**, 10.1090/S0002-9904-1956-10036-0**5.**Damir D. Dzhafarov and Jeffry L. Hirst,*The polarized Ramsey’s theorem*, Arch. Math. Logic**48**(2009), no. 2, 141–157. MR**2487221**, 10.1007/s00153-008-0108-0**6.**Petr Hájek and Pavel Pudlák,*Metamathematics of first-order arithmetic*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998. Second printing. MR**1748522****7.**Denis R. Hirschfeldt and Richard A. Shore,*Combinatorial principles weaker than Ramsey’s theorem for pairs*, J. Symbolic Logic**72**(2007), no. 1, 171–206. MR**2298478**, 10.2178/jsl/1174668391**8.**Hirst, Jeffry L.,*Combinatorics in subsystems of second order arithmetic*, Ph.D. Dissertation, Pennsylvania State University, 1987.**9.**Manuel Lerman,*On suborderings of the 𝛼-recursively enumerable 𝛼-degrees*, Ann. Math. Logic**4**(1972), 369–392. MR**0327493****10.**Stephen G. Simpson,*Subsystems of second order arithmetic*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR**1723993****11.**Theodore A. Slaman,*Σ_{𝑛}-bounding and Δ_{𝑛}-induction*, Proc. Amer. Math. Soc.**132**(2004), no. 8, 2449–2456 (electronic). MR**2052424**, 10.1090/S0002-9939-04-07294-6

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:
https://doi.org/10.1090/S0002-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.