Computing descending sequences in linear orderings
Jun Le Goh (University of Wisconsin)
Abstract: Let DS be the problem of computing a descending sequence in a given ill-founded linear ordering. We investigate the uniform computational content of DS from the point of view of Weihrauch reducibility, in particular its relationship with the analogous problem of computing a path in a given ill-founded tree (known as choice on Baire space).
First, we show that DS is strictly Weihrauch reducible to choice on Baire space. Our techniques characterize the problems which have codomain N and are Weihrauch reducible to DS, thereby identifying the so-called first-order part of DS.
Second, we use the technique of inseparable $\Pi^1_1$ sets (first used by Angles d'Auriac, Kihara in this context) to study the strengthening of DS whose inputs are $\Sigma^1_1$-codes for ill-founded linear orderings. We prove that this strengthening is still strictly Weihrauch reducible to choice on Baire space.
This is joint work with Arno Pauly 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.
Organizers: | Damir Dzhafarov*, Vasco Brattka*, Ekaterina Fokina*, Ludovic Patey*, Takayuki Kihara, Noam Greenberg, Arno Pauly, Linda Brown Westrick |
*contact for this listing |