"First-order parts" of Weihrauch degrees

Keita Yokoyama, Japan Advanced Institute of Science and Technology. Part of the Logic Seminar Series.

The Weihrauch degree of a binary relation on Baire space measures the power of uniform computation of a problem defined on Baire space.  In the recent studies of Weihrauch degrees, it is seen that its structure resembles the structure of second-order arithmetic in the sense of reverse mathematics.  In this study, we will introduce the "first-order part" of a Weihrauch degree by focusing on numerical consequences and try to measure the first-order strength of degrees.  Then we see that the first-order parts of degrees of arithmetical problems form a hierarchy corresponding to Kirby-Paris hierarchy of first-order arithmetic, and those can be classified with their first-order strength.

This is a joint work with Damir Dzhafarov and Reed Solomon.