Computing descending sequences in linear orderings

Jun Le Goh (University of Wisconsin)

11-Aug-2020, 14:00-15:00 (4 years ago)

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

Export talk to