On the role of the collection principle for formulas in secondorder reverse mathematics
Authors:
C. T. Chong, Steffen Lempp and Yue Yang
Journal:
Proc. Amer. Math. Soc. 138 (2010), 10931100
MSC (2000):
Primary 03F35; Secondary 03H15
Published electronically:
October 26, 2009
MathSciNet review:
2566574
Fulltext PDF
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 bitame 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 (2002c:03094), http://dx.doi.org/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 (57 #16019)
 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
(99m:03082), http://dx.doi.org/10.1016/01680072(96)000280
 4.
P.
Erdös and R.
Rado, A partition calculus in set
theory, Bull. Amer. Math. Soc. 62 (1956), 427–489. MR 0081864
(18,458a), http://dx.doi.org/10.1090/S000299041956100360
 5.
Damir
D. Dzhafarov and Jeffry
L. Hirst, The polarized Ramsey’s theorem, Arch. Math.
Logic 48 (2009), no. 2, 141–157. MR 2487221
(2009m:03013), http://dx.doi.org/10.1007/s0015300801080
 6.
Petr
Hájek and Pavel
Pudlák, Metamathematics of firstorder arithmetic,
Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1998. Second
printing. MR
1748522 (2000m:03003)
 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
(2007m:03115), http://dx.doi.org/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
(48 #5835)
 10.
Stephen
G. Simpson, Subsystems of second order arithmetic,
Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1999. MR 1723993
(2001i:03126)
 11.
Theodore
A. Slaman, Σ_{𝑛}bounding and
Δ_{𝑛}induction, Proc. Amer.
Math. Soc. 132 (2004), no. 8, 2449–2456 (electronic). MR 2052424
(2005b:03140), http://dx.doi.org/10.1090/S0002993904072946
 1.
 Cholak, Peter A., Carl G. Jockusch Jr. and Theodore A. Slaman, On the strength of Ramsey's theorem for pairs, J. Symbolic Logic 66 (2001), 155. MR 1825173 (2002c:03094)
 2.
 Chong, C. T., An finite injury method of the unbounded type, J. Symbolic Logic 41 (1976), 117. MR 0476456 (57:16019)
 3.
 Chong, C. T. and Yue Yang, induction and infinite injury priority arguments. II. Tame coding and the jump operator, Ann. Pure Appl. Logic 87 (1997), 103116. MR 1490049 (99m:03082)
 4.
 Erdős, Paul and Richard Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427489. MR 0081864 (18:458a)
 5.
 Dzhafarov, Damir D. and Jeffry L. Hirst, The polarized Ramsey's theorem, Arch. Math. Logic 48 (2009), 141157. MR 2487221
 6.
 Hájek, Petr and Pavel Pudlák, Metamathematics of firstorder arithmetic, Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1993 (second printing, 1998). MR 1748522 (2000m:03003)
 7.
 Hirschfeldt, Denis R. and Richard A. Shore, Combinatorial principles weaker than Ramsey's theorem for pairs, J. Symbolic Logic 72 (2007), 171206. MR 2298478 (2007m:03115)
 8.
 Hirst, Jeffry L., Combinatorics in subsystems of second order arithmetic, Ph.D. Dissertation, Pennsylvania State University, 1987.
 9.
 Lerman, Manuel, On suborderings of the recursively enumerable degrees, Ann. Math. Logic 4 (1972), 369392. MR 0327493 (48:5835)
 10.
 Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1999. MR 1723993 (2001i:03126)
 11.
 Slaman, Theodore A., bounding and induction, Proc. Amer. Math. Soc. 132 (2004), 24492456. MR 2052424 (2005b:03140)
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 537061388
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/S0002993909101156
PII:
S 00029939(09)101156
Keywords:
Reverse mathematics,
$\Sigma ^0_2$bounding,
linear order,
tame cut,
bitame 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 C146000025001. 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 146000114112.
Communicated by:
Julia Knight
Article copyright:
© Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
