Logic Seminar

Damir DzhafarovUniversity of Connecticut
Ramseys theorem for singletons and strong computable reducibility

Wednesday, September 14, 2016 - 4:00pm
Malott 206

Recently, there has been a growing interest in looking at various forms of Ramseys theorem under so-called strong reducibility, where P is said to be strongly computably (sc) reducible to Q if, for each P-instance X, there is a Q-instance Y computable from X, such that every Q-solution to Y computes a P-solution to X. (The different from computable reduction is that the backward reduction is from the P-solution alone, rather than from it join the original P-instance X.) As an early result in this direction, I showed that COH is not sc-reducible to D^2_k for any k. In this talk, I will give a proof, joint with Patey, Solomon, and Westrick, that Ramseys theorem for singletons and k colors (RT^1_k) is not strongly computably reducible to the stable Ramseys theorem for pairs and l colors (SRT^2_l) whenever k > l. This answers a question of Hirschfeldt and Jockusch, and gives as a corollary a considerable improvement over my prior result: namely, it follow that COH is not sc-reducible even to SRT^2_k for any k. The proof of the main theorem is a rather unusual forcing argument, involving a new combinatorial technique called tree labeling. I will aim to give all the details.