PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

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