The higher levels of the Weihrauch lattice

Abstract: The classification of mathematical problems in the Weihrauch lattice is a line of research that blossomed in the last few years. Initially this approach dealt mainly with statements which are provable in ACA_0 and showed that usually Weihrauch reducibility is more fine-grained than reverse mathematics.

In the last few years the study of multi-valued functions arising from statements laying at higher levels (such as ATR_0 and Pi^1_1-CA_0) of the reverse mathematics spectrum started as well. The multi-valued functions studied so far include those arising from the perfect tree theorem, comparability of well-orders, determinacy of open and clopen games, König’s duality theorem, various forms of choice, the open and clopen Ramsey theorem and the Cantor-Bendixson theorem.

At this level often a single theorem naturally leads to several multi-valued functions of different Weihrauch degree, depending on how the theorem is "read" from a computability viewpoint. A case in point is the perfect tree theorem: it can be read as the request to produce a perfect subtree of a tree with uncountably many paths, or as the request to list all paths of a tree which does not contain a perfect subtree. Similarly, the clopen Ramsey theorem leads to the multi-valued function that associates to every clopen subset of [N]^N an infinite homogeneous set on either side, and to the multi-valued function producing for each clopen subset which has an infinite homogeneous sets on one side a homogeneous set on that side. Similar functions can be defined similarly starting from the open Ramsey theorem.

In this talk I discuss some of these results, emphasizing recent joint work with my students Vittorio Cipriani and Manlio Valenti.

logic

Audience: researchers in the topic

---

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.

---