For more information about this meeting, contact Stephen Simpson, Jan Reimann.

Title: | Strong reductions between combinatorial problems |

Seminar: | Logic Seminar |

Speaker: | Damir Dzhafarov, University of Connecticut |

Abstract: |

I will discuss recent investigations of various reducibility notions between Pi^1_2 principles of second-order arithmetic, the most familiar of which is implication over the subsystem RCA_0. In many cases, such an implication is actually due to a considerably stronger reduction holding, such as a uniform (a.k.a. Weihrauch) reduction. (Here, we say a principle P is uniformly reducible to a principle Q if there are fixed reduction procedures Phi and Gamma such that for every instance A of P, Phi(A) is an instance of Q, and for every solution S to Phi(A), Gamma(A + S) is a solution to A.) As an example, nearly all the implications between principles lying below Ramsey's theorem for pairs are uniform reductions. In general, the study of when such stronger implications hold and when they do not gives a finer way of calibrating the relative strength of mathematical propositions. In addition, this analysis sheds light on several open questions from reverse mathematics, including that of whether the stable form of Ramsey's theorem for pairs (SRT^2_2) implies the cohesive principle (COH) in \omega (standard) models of RCA_0. |

### Room Reservation Information

Room Number: | MB315 |

Date: | 11 / 12 / 2013 |

Time: | 02:30pm - 03:45pm |