RAMSEY'S THEOREM FOR SINGLETONS AND STRONG COMPUTABLE REDUCIBILITY

作     者：Dzhafarov, Damir D. Patey, Ludovic Solomon, Reed Westrick, Linda Brown 

作者机构：Univ Connecticut Dept Math Storrs CT 06269 USA Univ Paris Diderot Lab PPS Paris France 

出 版 物：《PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY》 (美国数学会会报)

年 卷 期：2017年第145卷第3期

页      面：1343-1355页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：NSF [DMS-1400267] John Templeton Foundation ('Structure and Randomness in the Theory of Computation' project) 

主　　题：RAMSEY theory SINGLETON bounds COMPUTABLE functions SET theory HOMOGENEOUS spaces 

摘      要：We answer a question posed by Hirschfeldt and Jockusch by showing that whenever k l, Ramsey s theorem for singletons and k-colorings, RTkl, is not strongly computably reducible to the stable Ramsey s theorem for l-colorings, SRTl2. Our proof actually establishes the following considerably stronger fact: given k l there is a coloring, c : omega - k such that for every stable coloring d : [omega]2 - l (computable from c or not), there is an infinite homogeneous set H for d that computes no infinite homogeneous set for c. This also answers a separate question of Dzhafarov, as it follows that the cohesive principle, COH, is not strongly computably reducible to the stable Ramsey s theorem for all colorings, SRTinfinity 2. The latter is the strongest partial result to date in the direction of giving a negative answer to the longstanding open question of whether COH is implied by the stable Ramsey s theorem in omega-models of RCA(0).