Cappable CEA sets and Ramsey’s theorem. (English) Zbl 1280.03041

Kach, Asher M.; Lerman, Manuel; Solomon, Reed

Arai, Toshiyasu (ed.) et al., Proceedings of the 11th Asian logic conference in honor of Professor Chong Chitat on his 60th birthday, National University of Singapore, Singapore, June 22–27, 2009. Hackensack, NJ: World Scientific (ISBN 978-981-4360-53-1/hbk; 978-981-4360-54-8/ebook). 114-127 (2012).

The authors begin a search for degree-theoretic properties that might be used to separate Ramsey’s theorem for pairs from its stable version in the sense of reverse mathematics. They obtain the following result.
Theorem. There is a computable stable coloring of pairs that does not have a homogeneous set computable from a \(c\)-cappable 2-CEA set.
For the entire collection see [Zbl 1253.03002].

Reviewer: Vadim Puzarenko (Novosibirsk)

MSC:

03C57	Computable structure theory, computable model theory
03D45	Theory of numerations, effectively presented structures
03C55	Set-theoretic model theory
03D25	Recursively (computably) enumerable sets and degrees
03B30	Foundations of classical theories (including reverse mathematics)

Keywords:

reverse mathematics; Turing degrees; Ramsey’s theorem for pairs; computable stable coloring of pairs