The first-order part of Weihrauch degrees

Manlio Valenti (University of Udine)

31-Mar-2022, 18:00-19:00 (24 months ago)

Abstract: Given an order $(P,\le)$, a natural strategy to prove that $a \not\le b$ is to present an example of some $c\le a$ such that $c \not\le b$. Of course, choosing such a $c$ can be very challenging.

In the context of TTE and Weihrauch reducibility, (Dzhafarov, Solomon, Yokoyama) introduced the notion of ``first-order part" of a computational problem $f$, capturing the ``strongest computational problem that is Weihrauch-below $f$". Characterizing the first-order part of a given problem can be challenging as well, but it proved to be a very useful tool, especially when comparing principles that are (relatively) high in the Weihrauch hierarchy.

In this talk, we will study the first-order part from a more algebraic perspective, and study its relation with several other operators already defined in the literature. We will then show how the obtained results can be used to easily characterize the first-order part of many known problems.

logic

Audience: researchers in the topic


Online logic seminar

Series comments: Description: Seminar on all areas of logic

Organizer: Wesley Calvert*
*contact for this listing

Export talk to