Combinatorial principles between \mathrm{R}\mathrm{R}{\mathrm{T}}_{\mathrm{2}}^{\mathrm{2}} and \mathrm{R}{\mathrm{T}}_{\mathrm{2}}^{\mathrm{2}}

Abstract

We study the strength of some combinatorial principles weaker than Ramsey theorem for pairs over RCA₀. First, we prove that Rainbow Ramsey theorem for pairs does not imply Thin Set theorem for pairs. Furthermore, we get some other related results on reverse mathematics using the same method. For instance, Rainbow Ramsey theorem for pairs is strictly weaker than Erdös-Moser theorem under RCA₀.

Keywords

Reverse mathematics / thin set / free set / Erdös-Moser theorem / Rainbow Ramsey theorem

References

[1] Bovykin A, Weiermann A. The strength of infinitary Ramseyan principles can be accessed by their densities. Ann Pure Appl Logic (to appear) , 2005

[2] Cholak P A, Giusto M, Hirst J L, Jockush C G Jr. Free sets and reverse mathematics. In: Reverse Mathematics 2001. Lect Notes Log, Vol 21. La Jolla: Assoc Symbol Logic, 2005, 104−119

[3] Csima B, Mileti J. The strength of the rainbow Ramsey theorem. J Symbolic Logic, 2009, 74(4): 1310−1324

[4] Liu Jiayi. R T 2 2 does not imply WKL₀.J Symbolic Logic, 2012, 77(2): 609−620

[5] Nies A. Computability and Randomness. Oxford Logic Guides. Oxford: Oxford University Press, 2010

[6] Simpson S G. Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic. Berlin: Springer-Verlag, 1999

[7] Soare R I. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Heidelberg: Springer-Verlag, 1987

[8] Wang Wei. Cohesive sets and rainbows. Ann Pure Appl Logic, 2014, 165(2): 389−408

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg