On the first-order parts of problems in the Weihrauch degrees
Damir D. Dzhafarov, Reed Solomon, Reed Solomon, Keita Yokoyama, Keita Yokoyama · Computability · 2024
We introduce the notion of the first-order part of a problem in the Weihrauch degrees. Informally, the first-order part of a problem P is the strongest problem with codomaixn ω that is Weihrauch reducible to P. We show that the first-order part is always well-defined, examine some of the basic properties of this notion, and characterize the first-order parts of several well-known problems from the literature.