Midwest Computability Seminar

XXVII
Part iii


The Midwest Computability Seminar is meeting remotely in the fall of 2021. The recurring Zoom link is:

https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09

Meeting ID: 997 5433 2165

Passcode: midwest


Vittorio Cipriani: slides    Panopto video    YouTube video

David Webb: slides     Panopto video    YouTube video


This session will be held jointly with the Computability Theory and Applications Online Seminar.


DATE: Monday, October 11th, 2021

TIME: 3:30 - 4:30 PM Central Time


We will have two speakers:


SPEAKER: Vittorio Cipriani - University of Udine

TITLE: 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 Π11-CA0. Kihara, Marcone and Pauly already showed that many problems representing principles equivalent to ATR0 lie in different Weihrauch degrees, for Π11-CA0 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 PKTr, 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 PKTr <W PKX, where PKX 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 PKX and wCBX (i.e. same as PKX 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 CBX (i.e. same as wCBX but where the output provides also the cardinality of the scattered part) "almost" splits in two Weihrauch degrees, one having as representative PKX and the other having CBℕℕ.

This is joint work with Alberto Marcone and Manlio Valenti.


SPEAKER: David Webb - University of Hawaiʻi at Mānoa

TITLE: Under what reducibilities are KLR and MLR Medvedev equivalent?

ABSTRACT: Motivated by the observation that one half of a Kolmogorov-Loveland random is Martin-Löf random, we consider the problem of outputting (Martin-Löf) random bits given a pair of oracles, an unknown member of which is itself random. We show that a truth-table reduction can be used to do this, so that KLR and MLR are truth-table Medvedev equivalent. We also investigate whether even stronger reducibilities can be used, obtaining negative results for linear, positive, and bounded truth-table reducibilities.



Past and Future Sessions

Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.