Connecticut CT Logic Seminar

Joins in the strong Weihrauch degrees

Damir Dzhafarov (University of Connecticut)

Monday, November 5, 2018 4:45 pm
MONT 214 (Storrs)

Weihrauch reducibility is a tool for comparing the difficulty of various mathematical problems that has been widely applied in computable analysis, and more recently, also in computable combinatorics. In many ways, it is a refinement both of effective mathematics and reverse mathematics, and over the past few years it has seen a surge of interest. Many open problems remain about the basic algebraic structure of the Weihrauch degrees. We answer a question of Brattka and Pauly by showing that the so-called strong Weihrauch degrees, which are a natural and well-studied subclass of the Weihrauch degrees, form a lattice. Previously, these were known only to form a lower semi-lattice. Moreover, this lattice turns out to be non-distributive, which makes it different from most other degree structures studied in the literature. I will present a general introduction to this problem and explain the proof.