Cantor-Bendixson Theorem in the Weihrauch lattice

Abstract: In this talk we will study the Cantor-Bendixson theorem using the framework of Weihrauch reducibility. (Variations of) this theorem falls into the highest of the big-five axiom systems of reverse mathematics, namely \Pi_1^1-CA_0 . Kihara, Marcone and Pauly already showed that many problems representing principles equivalent to ATR_0 lie in different Weihrauch degrees, for \Pi_1^1-CA_0 we actually have a natural candidate, namely the one mapping a countable sequence of trees to the characteristic function of the set of indices corresponding to well-founded trees. This principle was firstly considered by Hirst, that also showed its Weihrauch equivalence with PK_Tr, the function that takes as input a tree and outputs its perfect kernel for trees. Even if in reverse mathematics it is actually equivalent to consider trees or closed sets, we will show that PK_Tr <_W PK_X, where PK_X takes as input a closed set of a computable Polish space X and outputs its perfect kernel. The equivalence between these two shows up if we switch to arithmetical Weihrauch reducibility.

We will continue in this direction showing (non) reductions between problems related to the Cantor-Bendixson theorem with particular attention paid to classify them for every computable Polish space X. This leads us to the result that, while PK_X and wCB_X (i.e. same as PK_X but where the output also provides a listing of the elements in the scattered part) are equivalent for any space X that we consider, the problem CB_X (i.e. same as wCB_X but where the output provides also the cardinality of the scattered part) "almost" splits in two Weihrauch degrees, one having as representative PK_X and the other having CB_\Baire.

This is joint work with Alberto Marcone 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.