Jun Le Goh (University of Wisconsin)

August 11, 2020 @ 4:00 am – 5:00 am

Title: Computing descending sequences in linear orderings
by Jun Le Goh (University of Wisconsin) as part of Computability theory and applications

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.